Ring Pipelined Algorithm for the Algebraic Path Problem on the CELL Broadband Engine

The algebraic path problem (APP) unifies a number of related combinatorial or numerical problems into one that can be resolved by a generic algorithmic schema. In this paper, we propose a linear SPMD model based on the Warshall-Floyd procedure coupled with a systematic shift-toroïdal. Our scheduling requires a number of processors that equals the size of the input matrix. With a fewer number of processors, we exploit the modularity revealed by our linear array to achieve the task using a locally parallel and globally sequential} (LPGS) partitioning. Whatever the case, we just need each processor to have a local memory large enough to house one (probably block) column of the matrix. Considering these two characteristics clearly justify an implementation on the CELL Broadband engine, because of the efficient SPE to SPE communication bandwidth and the absolute power of each SPE. We report our experimentations on a QS22 CELL blade on various input configurations and exhibit the efficiency and scalability of our implementation. We show that, with a highly optimized Warshall-Floyd kernel, we could get close to 80 GFLOPS in simple precision with 8 SPEs which represents 80% of the peak performance for the APP on the CELL.