The search functionality is under construction.

The search functionality is under construction.

The All-Pairs Shortest Paths (APSP) problem is a graph problem which can be solved by a three-nested loop program. The Cell Broadband Engine (Cell/B.E.) is a heterogeneous multi-core processor that offers the high single precision floating-point performance. In this paper, a solution of the APSP problem on the Cell/B.E. is presented. To maximize the performance of the Cell/B.E., a blocked algorithm for the APSP problem is used. The blocked algorithm enables reuse of data in registers and utilizes the memory hierarchy. We also describe several optimization techniques for effective implementation of the APSP problem on the Cell/B.E. The Cell/B.E. achieves the performance of 8.45 Gflop/s for the APSP problem by using one SPE and 50.6 Gflop/s by using six SPEs.

- Publication
- IEICE TRANSACTIONS on Information Vol.E92-D No.6 pp.1225-1231

- Publication Date
- 2009/06/01

- Publicized

- Online ISSN
- 1745-1361

- DOI
- 10.1587/transinf.E92.D.1225

- Type of Manuscript
- PAPER

- Category
- Computation and Computational Models

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Kazuya MATSUMOTO, Stanislav G. SEDUKHIN, "A Solution of the All-Pairs Shortest Paths Problem on the Cell Broadband Engine Processor" in IEICE TRANSACTIONS on Information,
vol. E92-D, no. 6, pp. 1225-1231, June 2009, doi: 10.1587/transinf.E92.D.1225.

Abstract: The All-Pairs Shortest Paths (APSP) problem is a graph problem which can be solved by a three-nested loop program. The Cell Broadband Engine (Cell/B.E.) is a heterogeneous multi-core processor that offers the high single precision floating-point performance. In this paper, a solution of the APSP problem on the Cell/B.E. is presented. To maximize the performance of the Cell/B.E., a blocked algorithm for the APSP problem is used. The blocked algorithm enables reuse of data in registers and utilizes the memory hierarchy. We also describe several optimization techniques for effective implementation of the APSP problem on the Cell/B.E. The Cell/B.E. achieves the performance of 8.45 Gflop/s for the APSP problem by using one SPE and 50.6 Gflop/s by using six SPEs.

URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E92.D.1225/_p

Copy

@ARTICLE{e92-d_6_1225,

author={Kazuya MATSUMOTO, Stanislav G. SEDUKHIN, },

journal={IEICE TRANSACTIONS on Information},

title={A Solution of the All-Pairs Shortest Paths Problem on the Cell Broadband Engine Processor},

year={2009},

volume={E92-D},

number={6},

pages={1225-1231},

abstract={The All-Pairs Shortest Paths (APSP) problem is a graph problem which can be solved by a three-nested loop program. The Cell Broadband Engine (Cell/B.E.) is a heterogeneous multi-core processor that offers the high single precision floating-point performance. In this paper, a solution of the APSP problem on the Cell/B.E. is presented. To maximize the performance of the Cell/B.E., a blocked algorithm for the APSP problem is used. The blocked algorithm enables reuse of data in registers and utilizes the memory hierarchy. We also describe several optimization techniques for effective implementation of the APSP problem on the Cell/B.E. The Cell/B.E. achieves the performance of 8.45 Gflop/s for the APSP problem by using one SPE and 50.6 Gflop/s by using six SPEs.},

keywords={},

doi={10.1587/transinf.E92.D.1225},

ISSN={1745-1361},

month={June},}

Copy

TY - JOUR

TI - A Solution of the All-Pairs Shortest Paths Problem on the Cell Broadband Engine Processor

T2 - IEICE TRANSACTIONS on Information

SP - 1225

EP - 1231

AU - Kazuya MATSUMOTO

AU - Stanislav G. SEDUKHIN

PY - 2009

DO - 10.1587/transinf.E92.D.1225

JO - IEICE TRANSACTIONS on Information

SN - 1745-1361

VL - E92-D

IS - 6

JA - IEICE TRANSACTIONS on Information

Y1 - June 2009

AB - The All-Pairs Shortest Paths (APSP) problem is a graph problem which can be solved by a three-nested loop program. The Cell Broadband Engine (Cell/B.E.) is a heterogeneous multi-core processor that offers the high single precision floating-point performance. In this paper, a solution of the APSP problem on the Cell/B.E. is presented. To maximize the performance of the Cell/B.E., a blocked algorithm for the APSP problem is used. The blocked algorithm enables reuse of data in registers and utilizes the memory hierarchy. We also describe several optimization techniques for effective implementation of the APSP problem on the Cell/B.E. The Cell/B.E. achieves the performance of 8.45 Gflop/s for the APSP problem by using one SPE and 50.6 Gflop/s by using six SPEs.

ER -