Static scheduling of uniform nested loops

Abstract

Efficient scheduling of nested loops is an important problem in highly parallel systems. Most of previous research has been on the transformations of iteration space instead of the loop body. The authors introduce a methodology to transform a loop body into a new one with a better schedule. They model nested loops as multidimensional data-flow graphs, and give a novel mathematical framework for uniform nested loops by using the techniques of retiming and unfolding. Integer linear inequality systems are derived to optimize the execution rate of an iteration. The special case of their framework gives the best-known algorithm for scheduling of one-level loops.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>