Scheduling and binding algorithms for high-level synthesis

ABSTRACT

New algorithms for high-level synthesis are presented. The first performs scheduling under hardware resource constraints and improves on commonly used list scheduling techniques by making use of a global priority function. A new design-space exploration technique, which combines this algorithm with an existing one based on time constraints, is also presented. A second algorithm is used for register and bus allocation to satisfy two criteria: the minimization of interconnect costs as well as the final register (bus) cost. A clique partitioning approach is used where the clique graph is pruned using interconnect affinities between register (bus) pairs. Examples from current literature were chosen to illustrate the algorithms and to compare them with four existing systems.

REFERENCES

• Brew87: F. D. Brewer , D. D. Gajski, Knowledge based control in micro-architecture design, Proceedings of the 24th ACM/IEEE conference on Design automation, p.203-209, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37919]
• Camp87: R. Camposano, "Structural Synthesis i~n the Yorktown Si Compiler", VLSI '87, Aug. 1987, p. 29.
• Clou87: R. Cloutier, Private Communication, Nov. 1987.
• Davi81: S. Davidson et al, "Some Experiments in Local Microcode Compaction for Horizontal Machines", IEEE Trans. on Computers, C-30, 7, Jul. 1981, pp. 460-477.
• DeBo88: E. Detjiens, G. Borriello (Chairs), "Workshop on High-Level Synthesis", Orc~Ls Island, Jan. 1988.
• DeMa86: H. De Man et al, "Ca~thedral-II : A Silicon Compiler for Digital Signal Proces,~ing", IEEE Design & Test Magazine, December 1986, pp. 13-25.
• Fuhr88: T. Fuhrman, "High-Level Synthesis Desig:n of a Real-Time Control Chip at GM-Delco", ACM/IEEE High- Lew'l Synthesis Workshop, Jan. 1988.
• Gebo87: C.H. Gebotys, M.I. Elmasry, "A VLSI Methodology with Testability Constraints", Proc. of Canadian Conference on VLSI, Winnipeg, Oct. 198"7.
• Gebo88: Catherine H. Gebotys , Mohamed I. Elmasry, VLSI design synthesis with testability, Proceedings of the 25th ACM/IEEE conference on Design automation, p.16-21, June 12-15, 1988, Atlantic City, New Jersey, United States
• GiKn84: E.F. Girczyc and J.P. Knight, "An ADA to Standard Cell Hardware Compiler Based on Graph Grammars and Scheduling", Proc. of ICCD, Oct. 1984, pp. 726-731.
• Kram88: H. Kramer et al, "Data Path and Control Synthesis in the CADDY System", Proc. of Intl.Workshop on Silicon Compilers, Grenoble, France, May 1988.
• Kurd87: F. J. Kurdahi , A. C. Parker, REAL: a program for REgister ALlocation, Proceedings of the 24th ACM/IEEE conference on Design automation, p.210-215, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37920]
• KuWK85: S. Y. Kung , Thomas Kailath , Harper J. Whitehouse, VLSI and Modern Signal Processing, Prentice Hall Professional Technical Reference, 1984
• McFa87: M.C. McF:arland, "Reevaluating the Design Space for Register-Transfer Hardware Synthesis", Proc. of ICCAD, Nov. 1987, pp.262-265.
• McPC88: Michael C. McFarland , Alice C. Parker , Raul Camposano, Tutorial on high-level synthesis, Proceedings of the 25th ACM/IEEE conference on Design automation, p.330-336, June 12-15, 1988, Atlantic City, New Jersey, United States
• Midw88: J. Midwinter, "improving Interconnect for the Behavioral Synthesis of ASICs", M.Sc. Thesis, Carleton University, April 1988.
• PaGa86: B.M. Pangrle, D.D. Gajski, "State Synthesis and Connectivity Binding for Microarchitecture Compilation", Proc. of ICCAD, Nov. 1986, pp. 210-213.
• Pang88: Barry M. Pangre, Splicer: a heuristic approach to connectivity binding, Proceedings of the 25th ACM/IEEE conference on Design automation, p.536-541, June 12-15, 1988, Atlantic City, New Jersey, United States
• Paul86: P. G. Paulin , J. P. Knight , E. F. Girczyc, HAL: a multi-paradigm approach to automatic data path synthesis, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.263-270, July 1986, Las Vegas, Nevada, United States
• Paul87: 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]
• Paul88: Pierre Gaston Paulin, High-level synthesis of digital circuits using global scheduling and binding algorithms, 1988
• Paul89: P.G. Paulin, J.P. Knight, "l?orce-Directed Scheduling for the Behavioral Synthesis of ASICs", IEEE Transactions on CAD of IC,'s and Systems, Vol. 8 (6), June 1989 (projected publication date).
• Pfah87: P. Pfahler, Automated datapath synthesis: A compilation approach, Microprocessing and Microprogramming, v.21 n.1-5, p.577-584, Aug. 1987 [doi>10.1016/0165-6074(87)90093-7]
• Sauc87: G. Saucier, M. Crastes de Paulet, P. Sicard, "ASYL: A Rule-Based System for Controller Synthesis", IEEE Trans. on CAD, Vol. CAD-6, Nov. 1987, pp, 1088-1097.
• Stok88: L. Stok, R. van den Born, "EASY: Multiprocessor Architecture Optimisation", Proc. of Intl. Workshop on Silicon Compilers, Grenoble, France, May 1988.
• Thom88: D. E. Thomas , E. M. Dirkes , R. A. Walker , J. V. Rajan , J. A. Nestor , R. L. Blackburn, The system architect's workbench, Proceedings of the 25th ACM/IEEE conference on Design automation, p.337-343, June 12-15, 1988, Atlantic City, New Jersey, United States
• Tsen86: C. Tseng, D.P. Siewiorek, "Automated Synthesis of Data Paths in Digital Systems", IEEE Trans. on CAD of ICs and Systems, July 1986, pp. 379-395.

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:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Automatic synthesis
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Experimentation, Performance