A model for systolic parallelization of multiple loop programs

The model presented here for systolic parallelization of programs with multiple loops aims at compilation of sequential programs for parallel computer architectures which support fine-grained communication. Regular loop nests in programs can be subjected to space-time loop transformations as has been examined in the area of systolic parallelization. The aim of this work is to show how this kind of parallelized regular loop nests interact and can be combined to a prallel solution for the whole program. For this purpose the interface of loop nests using or producing array variable elements regularly is examined and the necessary reorganization work between loop nests described. The qualitative analysis describes access patterns of array variables, their position patterns in the parallelized loop nest, and communication patterns to transport data elements between parallelized loops. A program containing two convolution calculations is used as an example. While this report focuses on qualitative description a mathematical refinement of the model will be presented in a subsequent report. (orig.)Available from TIB Hannover: RR 6673(29) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekSIGLEDEGerman