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

Kazuya MATSUMOTO  Stanislav G. SEDUKHIN  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E92-D   No.6   pp.1225-1231
Publication Date: 2009/06/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computation and Computational Models
Keyword: 
all-pairs shortest paths problem,  Floyd-Warshall algorithm,  Cell/B.E. processor,  performance evaluation,  

Full Text: PDF(332.3KB)
>>Buy this Article


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.