next up previous
Next: Bibliography Up: Compile-Time Minimisation of Load Previous: Banded SYR2K

Conclusion

This paper presented a partitioning scheme for loop nests in which, upon partitioning into equal partitions along the index of the outermost loop, each partition has a computational load which can be expressed in terms of a polynomial expression; these loop nests, termed canonical, are composed of loops for which the upper bound is always greater than or equal to the lower bound. It has also been shown how to apply index set splitting to transform non-canonical loop nests in a way that the above criterion is satisfied. Although minimising load imbalance has been the primary target of the scheme, it seems that by partitioning into groups having consecutive iterations (as opposed to a cyclic partitioning scheme [11]), as well as into as equal as possible partitions along the index of the outermost loop (as opposed to balanced chunk scheduling [9,10]), our approach appears to be more efficient in practice.



Rizos Sakellariou 2000-07-31