For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Solution of the All-Pairs Shortest Paths Problem on the Cell Broadband Engine Processor
Kazuya MATSUMOTO Stanislav G. SEDUKHIN
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2009/06/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computation and Computational Models
all-pairs shortest paths problem, Floyd-Warshall algorithm, Cell/B.E. processor, performance evaluation,
Full Text: PDF(332.3KB)
>>Buy this Article
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.