Compile-time techniques for parallel execution of loops on distributed memory multiprocessors
Ponnuswamy Sadayappan, Jagannathan Ramanujam · 1990
Communication in message passing machines could arise from the need to synchronize and from the non-locality of data. We focus on distribution of arrays accessed in the execution of nested loops. In current day machines, interprocessor communication is more time-consuming than instruction execution. If insufficient attention is paid to the data allocation problem, then so much time may be spent in interprocessor communication that much of the benefit of parallelism is lost. It is therefore worthwhile for a compiler to analyze patterns of data usage to determine allocation, in order to minimize interprocessor communication. We formulate the problem of determining if communication-free array partitions (decompositions) exist and presented machine-independent sufficient conditions for the same. In addition, where communication-free decomposition is not possible, we present heuristics for minimizing communication. For the class of tightly nested loops with regular loop-carried dependences, we present a method for aggregating a number of loop iterations into where the execute atomically. We study the effect of clustering communication and the ensuing loss or parallelism on performance and propose a method for aggregating a number of loop iterations into tiles where the execute atomically--a processor executing the iteration belonging to a tile receives all the data it needs before executing any one of the iterations in the tile, executes all the iterations in the tile and then sends the data needed by other processors. It is important that dividing up the loops into does not lead to deadlocks in parallel execution. In addition, the assignment of to processors should be such that inter-processor communication is minimized and the computation is load-balanced through time. We present an approach to determine the shape and size of for execution of nested loops on distributed memory machines; in addition, we present a method to allocate and schedule on the processing nodes of a distributed memory machine and to determine the tile size that minimizes the execution time under our model. We then develop techniques for determining a set of tiling planes that minimize the total inter-processor communication volume among processors. The proposed approach is applicable in the context of data parallel algorithms, which are abundant in scientific computation, signal and image processing. (Abstract shortened with permission of author.)