Transformation of Systolic Algorithms for Interleaving Partitions

A systematic method to m q systolizable proMems onto multicomputers is presented in this paper. A systoliz-able 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 require-ments are reduced and thus the performance can be increased. The proposed scheme requires a classirica-tion of dependences, and it is based in the interleaved execution of several partitions of the Systolic Algo-rithm. The code to be executed in a processing dement of the muhicomputer system is obtained through ap-plication of the proposed systematic transformations to the original sequential code. By appcYng this method to the APP we illustrate their main features, and several performance measures for a torus of transputers sys-tem are presented, considering the various algorithms which are unified by the APP. 1