Transformation of systolic algorithms for interleaving partitions

A systematic method to map systolic problems onto multicomputers is presented. A systolic problem is a problem for which it is possible to design a systolic algorithm. This method selects and transforms the systolic algorithm into a parallel algorithm with high granularity. The communications requirements are reduced and the performance can be increased. The proposed scheme requires a classification of dependences and it is based on the interleaved execution of several partitions of the systolic algorithm. The code to be executed in a processing element of the multicomputer system is obtained through application of the proposed systematic transformations to the original sequential code. By applying this method to algebraic path problem (APP), the authors illustrate the main features, and several performance measures for a torus of transputers system are presented, considering the various algorithms which are unified by the APP