"Scheduling of Uniform Multi-Dimensional Systems under Resource Constraints"

(by N. L. Passos and E. H.-M. Sha) in the IEEE Transactions on VLSI Systems, December 1998, Volume 6, Number 4, pp. 719-730.



   Multi-dimensional systems are widely used to model scientific applications such as image processing, geophysical signal processing and fluid dynamics. Such systems, usually, contain repetitive groups of operations represented by nested loops. The optimization of such loops, considering processing resource constraints, is required in order to improve their computational time. Most of the existing static scheduling mechanisms, used in the high level synthesis of VLSI architectures, do not consider the parallelism inherent to the multi-dimensional characteristics of the problem. This paper explores the basic properties of MD loop pipelining and presents two novel techniques, called multi-dimensional rotation scheduling and push-up scheduling, able to achieve the shortest possible schedule length. These new techniques transform a multi-dimensional data flow graph representing the problem, while assigning the loop operations to a schedule table. The multi-dimensional rotation scheduling is an iterative "heuristic" method, depending upon an user input, while the {\it push-up scheduling} algorithm is able to compute the new schedule in polynomial time. The optimal resulting schedule length and the efficiency of the algorithms are demonstrated by a series of practical experiments.


[ Published listings ] [ Top ]