Relative scheduling under timing constraints

ABSTRACT

Scheduling techniques are used in high-level synthesis of integrated circuits. Traditional scheduling techniques assume fixed execution delays for the operations. For the synthesis of ASIC designs that interface with external signals and events, operations with unbounded delays, i.e. delays unknown at compile time, must also be considered. We present a relative scheduling technique that supports operations with fixed and unbounded delays. The technique satisfies the timing constraints imposed by the user, which places bounds between the activation of operations. We analyze a novel property called well-posedness of timing constraints that is used to identify consistency of constraints in the presence of unbounded delay operations, and present an approach to relative scheduling that yields a minimum schedule that satisfies the constraints, or detects if no schedule exists, in polynomial time.

REFERENCES

• 1: M. Garey, D. Johnson, Computers and Intractability, W. Freeman and Co, 19/9.
• 2: R. Campeeano, W. Roum~el, Synthesizin& Circuits from Bekaw'oral Descriptions, IEEE Transacdcr, s on CAD, Vol 8, No. 2, Feb 1989, p. 171-180.
• 3: Michael C. McFarland, Using bottom-up design techniques in the synthesis of digital hardware from abstract behavioral descriptions, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.474-480, July 1986, Las Vegas, Nevada, United States
• 4: C. Tseng, D. Siewioxek, Automated Sy~thasis of Data Paths in Digital Systents, ~ Txamaction on CAD, Vol CAD-5, pp. 379-395, July 1986.
• 5: Thaddeus J. Kowalski, An Artificial Intelligence Approach to VLSI Design, Kluwer Academic Publishers, Norwell, MA, 1985
• 6: R. K. Brayton, R. Campceano, G. De lVfich~ll, IL Otten, I. van E.~jndhoven, The Yorktown Silicon Compiler System, in Silicon Compilers, D. Gajski (eeL), Addison Wesley t987, pp. 204-310,
• 7: Alice C. Parker , Jorge T. Pizarro , Mitch Mlinar, MAHA: a program for datapath synthesis, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.461-466, July 1986, Las Vegas, Nevada, United States
• 8: E. Girczyc, J. Kn~ht, An ADA to Standard Cell Hardware Compiler Based on Graph Grammars and Scheduling, Proceedings of ICCD, Oct 1984, p. 726-731.
• 9: S. Devad.u, R. Newton, AIgoriOons for Hardwar4e Allocation in Data-Path Synthesia, Pmoeedings of ICCD, Oct, 1987, pp. 526-531,
• 10: B. ~ngrle, D. Gajski, Slicer: a State Synthesizer for lntelligent Compilation, PrcceecLin~ of ICCD, pp. 42-45,1987.
• 11: 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]
• 12: 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
• 13: I. Nestor, D. Thomas, Behmn'oral Synthesis with Interfaces, Peoceedings ICCAD 86, pp. 112-115.
• 14: G. Bozrie.I1o, R. Katz, Synthesis and Optitm'~ations of interface Transducer Log/c, Proceedings of ICCAD 87, pp. 56-60.
• 15: Giovanni De Micheli , David C. Ku, HERCULES—a system for high-level synthesis, Proceedings of the 25th ACM/IEEE conference on Design automation, p.483-488, June 12-15, 1988, Atlantic City, New Jersey, United States
• 16: D. Ku, (3. De Mtch~li, High-level SyntlwJis and Optimization Strategies in Hcrcults andHeb~, Proceedings of EuroASIC, Paris, France, May 1990.
• 17: D. Ku, G. De l~cheli, Relative Scl~duling under Tinting Constraints, Stanfe~l CSL Technical Report CSL-TR-402, 1989.
• 18: M. I. McFarland, Valu~ Trace, CMU Interaal xepo~, 1978
• 19: Y. Liao, C. Wong, An Algorithm to Compact a Vl2~l Symbolic Layout with Mixed Constraints, 1~ Transactions on CAD, VoL CAD-2, No. 2, Apt t983, pp. 62-69.
• 20: A. 11. Newton, Symbo/k: Layout and Procedural Design, in De.slgn Systems for VLSI, G. De bliche.fi et. al. (ed.) pp. 65-112.
• 21: R. Ctmpouno. A. K~ Considering Tuning Constraints in Synthesis from a Behavioral Description, Proceedings of ICCD, pp. 6-9, 1986.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Design