Compile-time minimisation of load imbalance in loop nests

Parallelising compilers typically need some performance estimation capability in order to evaluate the trade-offs between different transformations. Such a capability requires sophisticated techniques for analysing the program and providing quantitative estimates to the compiler's internal cost model. Making use of techniques for symbolic evaluation of the number of iterations in a loop, this paper describes a novel compile-time scheme for partitioning loop nests in such a way that load imbalance is minimised. The scheme is based on a property of the class of canonical loop nests, namely that, upon partitioning into essentially equal-sized partitions along the index of the outermost loop, these can be combined in such a way as to achieve a balanced distribution of the computational load in the loop nest as-a-whole. A technique for handling non-canonical loop nests is also presented; essentially, this makes it possible to create a load-balanced partition for any loop nest which consists of loops whose bounds are linear functions of the loop indices. Experimental results on a virtual shared memory parallel computer demonstrate that the proposed scheme can achieve better performance than other compile-time schemes.