Optimum and heuristic data path scheduling under resource constraints

ABSTRACT

This paper presents an integer linear programming model for the scheduling problem in high level synthesis under resource constraints. Extensive consideration is given to the following applications: Multi-cycle operations with non-pipelined function units, pipelined function units; Mutually exclusive operations; Functional pipelining; Loop folding; Scheduling under bus constraint. Using this model, we are able to solve all the benchmarks in the literature optimally in a few seconds. Besides the model, a new technique, called Zone Scheduling (ZS), is proposed to solve large size problems. ZS partitions the distribution graph into several zones and solves sequentially the problems contained. A novel feature of this technique is that it schedules more than one control step at a time, allowing us to take a more global view of a scheduling problem.

REFERENCES

• 1: D.D. Gajski, N.D. Duu: and BaM. Pangde, "Silicon Compilation (Tutorial)", Proceedings of the: IEEE 1986 Custom Integrated Circuits Conference, R.och~ster NY, pp. 102-110, May 1986.
• 2: P. G. Paulin , J. P. Knight, Force-directed scheduling in automatic data path synthesis, Proceedings of the 24th ACM/IEEE conference on Design automation, p.195-202, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37918]
• 3: B.M. Pangrle and D.D. Gajski, "State Synthesis and Connectivity Binding for Microarchitvcture Compilafior~' Proc. of lCCAD-86, pp. 210-213, November 1986.
• 4: E.F. Girczyc, "Automatic Generation of Microsequenced Data Path to Realize ADA Circuit Description", Ph.D. Thesis Carleton Univ., 1984.
• 5: H. Park and A.C. Parker, "Sehwa: A Software Package for Synthesis of Pipelines t~om Behavioral Spe~fications", IEEE T-CAD, pp. 356-370, March 1988.
• 6: Charles Y. Hitchcock, III , Donald E. Thomas, A method of automatic data path synthesis, Proceedings of the 20th conference on Design automation, p.484-489, June 27-29, 1983, Miami Beach, Florida, United States
• 7: P. G. Paulin , J. P. Knight, Scheduling and binding algorithms for high-level synthesis, Proceedings of the 26th ACM/IEEE conference on Design automation, p.1-6, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74383]
• 8: Louis Hafer , Alice C. Parker, A formal method for the specification, analysis, and design of register-transfer level digital logic, Proceedings of the 18th conference on Design automation, p.846-853, June 29-July 01, 1981, Nashville, Tennessee, United States
• 9: H. DeMan, I. Rabaey, P. Six and L. Claese~ "Cathedral-II: A Silicon Compiler for Digital Signal Processing", IEEE Design and Test, pp. 13-25, December 1986.
• 10: B.S. Haroun, and M.I. Elmasry, "Arctdtvctural Synthesis for DSP Silicon Compiler", IEEE T-CAD, pp. 431-447, April 1989.
• 11: Jiahn-Hung Lee. Yu-Chin Hsu and Youn-Long Lin. "A New Integer Linear Programming Formulation for the Scheduling Problem in Data Path Synthesis", Prec. of 1CCAD-89, November 1989.
• 12: G. Goossens , J. Vandewlle , H. De Man, Loop optimization in register-transfer scheduling for DSP-systems, Proceedings of the 26th ACM/IEEE conference on Design automation, p.826-831, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74384]
• 13: E.M. Girczyc, "Loop Winging - a Data Flow Approach to Functional Pipelining", Proceedings of the IEEE ISCAS, pp 382-385, May 1987.
• 14: F. Rose, C. Leiserson, and J. Saxe, "Optimizing Synthesis Circuitry by Retiming", Proc. CalTech Conf. on VLSI, pp. 41-67, Computer Sci. Press, 1983.
• 15: "LINDO: Linear INteractive and DiscTete Optimizer for Linear, integer, and Quadratic programming problems." LINDO Systems, Inc.
• 16: S. Y. Kung , Thomas Kailath , Harper J. Whitehouse, VLSI and Modern Signal Processing, Prentice Hall Professional Technical Reference, 1984
• 17: Ki Soo Hwang, Albert E. Casavant, ChingoTand Chang and Manuel A,d'Abreu, "Scheduling and Hardware Sharing in Pipelincd Data Paths", IEEE Proc. Int. Conf. CAD pp. 24-27, November 1989.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming; Linear programming

General Terms:
Design, Experimentation, Performance