MAPPING UNIFORM LOOP NESTS ONTO DISTRIBUTED-MEMORY ARCHITECTURES

This paper deals with scheduling, mapping and partitioning techniques for uniform loop nests. Target machines are SPMD distributed memory pa rallel computers. We use affine-by-statement scheduling and affine-by- variable mapping to synthesize a virtual grid architecture from the or iginal loop nest. The virtual grid architecture is then partitioned in to a physical processor grid. The key to the mapping strategy is the c ommunication graph, which enables us to derive optimal mappings, i.e. where the number of communications is proved to be minimal. The partit ioning technique extends the methods developed for systolic array desi gn methodologies to loop nests with several statements.