Mapping Nested Loop Algorithms into Grid-Connected Systolic Arrays without Data Collisions in the Data Links
PeiZong Lee · 1996
Systolic arrays, which are made out of simple processing elements connected by data links, have made significant improvements in speeding up computation in comparison to conventional computers. Although systolic arrays belong to distributed memory parallel devices, they adopt systolic communications instead of message passing communications for sending data between neighboring processing elements. Therefore, it is important to provide necessary and sufficient conditions to avoid data collisions in the data links for a correct algorithm design. In this paper, we present necessary and sufficient conditions for mapping the class of shift-invariant uniform-dependence algorithms structured as nested loops into grid-connected systolic arrays of arbitrary dimensions. The proposed conditions, which are based on the ZERO-ONE-INFINITE property of tokens' behavior that describes how many times tokens are used and generated during the computation, can allow us to generate all feasible solutions. I...