A FAMILY OF EFFICIENT REGULAT ARRAYS FOR ALGEBRAIC PATH PROBLEM

Abstract

It has been shown that the method of decomposing a dependence graph into multiple phases with appropriate m-phase schedule function is useful for designing faster regular arrays for matrix multiplication and transitive closure. In this paper, we will further apply this method to design several parallel algorithms for Algebraic Path Problem and derive N x N 2-D regular arrays with execution time [9N/2] - 2 (cylindrical array and orthogonal one) and 4N - 2 (spherical one).