A SYSTOLIC APPROACH TO LOOP PARTITIONING AND MAPPING INTO FIXED SIZE DISTRIBUTED MEMORY ARCHITECTURES
I. Drositis, Nectarios Koziris, Nikolaos Papaspyrou, Panayotis Tsanakas · 2000
This paper presents a new method for the problem of mapping of nested FOR-loops with uniform dependencies, into mesh-connected parallel architectures. This method is based on loop mapping for systolic arrays. The virtual array of cells is derived from the index space, by applying a linear transformation. This array is divided (cut) into a fixed number of clusters, equal to the number of available real processors. The basic idea of our method is that the cutting is performed along properly selected boundary directions, so as to minimize inter-cluster communication and equilibrate the number of virtual cells for every cluster. Each cluster is then assigned to a different processor, which performs in a roughly independent manner, as the communication requirements are now minimized. This mapping cuts down overall communication delays, while using a fixed number of processors from a (n-1)-dimensional mesh-connected distributed architecture