Skip to Main content Skip to Navigation
Conference papers

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

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

http://hal.in2p3.fr/in2p3-00564725
Contributor : Sabine Starita <>
Submitted on : Wednesday, February 9, 2011 - 5:35:02 PM
Last modification on : Wednesday, October 14, 2020 - 3:41:34 AM

Identifiers

Collections

IN2P3 | LAL | CNRS

Citation

Claude Tadonki. Ring Pipelined Algorithm for the Algebraic Path Problem on the CELL Broadband Engine. 22nd International Symposium on Computer Architecture and High Performance Computing Workshops (SBAC-PADW 2010), Oct 2010, Petropolis, Brazil. pp.1-6, ⟨10.1109/SBAC-PADW.2010.7⟩. ⟨in2p3-00564725⟩

Share

Metrics

Record views

99