Scheduling under resource constraints using dis-equations

ABSTRACT

Scheduling is an important step in high-level synthesis (HLS). In our tool, we perform scheduling in two steps: coarse-grain scheduling, in which we take into account the whole control structure of the program including imperfect loop nests, and fine-grain scheduling, where we refine each logical step using a detailed description of the available resources. This paper focuses on the second step. Tasks are modeled as reservation tables (or templates) and we express resource constraints using dis-equations (i.e., negations of equations). We give an exact algorithm based on a branch-and-bound method, coupled with variants of Dijkstra's algorithm, which we compare with a greedy heuristic. Both algorithms are tested on pieces of scientific applications to demonstrate their suitability for HLS tools.

REFERENCES

• 1: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 2: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 3: F. Donnet. Synthèse de haut niveau contrôlée par l'utilisateur. PhD thesis, Université Paris VI, Jan. 2004.
• 4: Paul Feautrier, Some efficient solutions to the affine scheduling problem: I. One-dimensional time, International Journal of Parallel Programming, v.21 n.5, p.313-348, Oct. 1992 [doi>10.1007/BF01407835]
• 5: Daniel D. Gajski, Principles of digital design, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 6: Catherine H. Gebotys , Mohamed I. Elmasry, Simultaneous scheduling and allocation for cost constrained optimal architectural synthesis, Proceedings of the 28th conference on ACM/IEEE design automation, p.2-7, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127609]
• 7: Sumit Gupta , Nikil Dutt , Rajesh Gupta , Alex Nicolau, SPARK: A High-Lev l Synthesis Framework For Applying Parallelizing Compiler Transformations, Proceedings of the 16th International Conference on VLSI Design, p.461, January 04-08, 2003
• 8: D. Kästner and M. Langenbach. Integer linear programming vs. graph-based methods in code generation. Technical Report A/01/98, Universität des Saarlandes, Feb. 1998.
• 9: Krzysztof Kuchcinski, Constraints-driven scheduling and resource assignment, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.8 n.3, p.355-383, July 2003 [doi>10.1145/785411.785416]
• 10: Tai Ly , David Knapp , Ron Miller , Don MacMillen, Scheduling using behavioral templates, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.101-106, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217514]
• 11: I. Radivojević and F. Brewer. A new symbolic technique for control-dependent scheduling. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 15(1):45--57, Jan. 1996.
• 12: B. R. Rau. Iterative modulo scheduling. International Journal of Parallel Programming, 24(1):3--64, 1996.
• 13: J. Šilc. Scheduling strategies in high-level synthesis. Informatica (Slovenia), 18(1), 1994.
• 14: Robert A. Walker , Samit Chaudhuri, Introduction to the Scheduling Problem, IEEE Design & Test, v.12 n.2, p.60-69, June 1995 [doi>10.1109/54.386007]