A Solution of the All-Pairs Shortest Paths Problem on the Cell Broadband Engine Processor
Summary :
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
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
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 -
English
