Adaptive Cyclic Scheduling of Nested Loops

Abstract — The parallelization of computa-tional intensive programs can lead to dramatic performance improvements. Usually these pro-grams contain repetitive iterations, the major-ity in the form of nested DO(FOR) loops. The iterations within a loop nest fall into two types: independent iterations and precedence con-strained iterations. Furthermore, the precedence constraints can be uniform (constant) or non-uniform throughout the execution of the pro-gram. The index space of a uniform dependence loop, due to the existence of dependence vectors, ‡ This work was partially supported by the PROTAGO-RAS project of NTUA. is partitioned into subspaces of points that can be executed at a certain time instance. The geomet-ric representations of these sets form polygonal shapes called wavefronts or hyperplanes, with special attributes and characteristics. In this pa-per we tackle the uniform precedence constraints case, and we present a novel scheduling tech-nique for perfectly nested loops. Our technique is suitable for the two most common network architectures: homogeneous and heterogeneous systems, regardless of their underlying intercon-nection network. The presented method exploits the geometric properties of the index space in order to arrive at an efficient geometric decom-position. This approach significantly reduces the communication cost, which in most cases is the main drawback of the parallel performance