Partitioning and mapping nested loops on message-passing multiprocessors

Abstract

Loops are considered the main source of parallelism in sequential algorithms. When a nested loop is scheduled for execution on a distributed-memory multiprocessor, the total execution time is composed of two parts - the computation time and the communication time. In this work the problem of scheduling perfectly nested loops with constant loop-carried dependencies onto distributed-memory multiprocessors has been studied. The scheduling problem was divided into three steps: the partitioning step, the clustering step and the mapping step. A unified method for partitioning and clustering nested loops is introduced. In the partitioning phase, the n-dimensional iteration space of the nested loop is reduced first by projection into an (n-1)-dimensional space, then the projected iteration space is partitioned into groups which are computation balanced independent of the target multiprocessor architecture. In the second phase, the groups are clustered for mapping onto the multiprocessor system, such that communication is as low as possible and that the processors are load balanced.