Parallel algorithms, Programming paradigms, Generic algorithms, Tuple multiplication, Matrix multiplication, All-pairs shortest paths
This paper illustrates the benefits of developing generic algorithms for parallel programming paradigms which can be adapted to different applications. We consider a combinatorial problem called tuple multiplication. This paradigm includes matrix multiplication and the all-pairs shortest paths problem as special cases. We develop a generic pipeline for tuple multiplication. From the generic algorithm we derive pipelines for matrix multiplication and shortest paths computation by making substitutions of data types and functions. The performance of the matrix multiplication pipeline is analyzed and measured on a Computing Surface.
Hansen, Per Brinch, "A Generic Multiplication Pipeline" (1991). Electrical Engineering and Computer Science Technical Reports. 111.