Decomposition of timed decision tables and its use in presynthesis optimizations

ABSTRACT

Presynthesis optimizations transform a behavioral HDL description into an optimized HDL description that results in improved synthesis results. We introduce the decomposition of timed decision tables (TDT), a tabular model of system behavior. The TDT decomposition is based on the kernel extraction algorithm. By experimenting using named benchmarks, we demonstrate how TDT decomposition can be used in presynthesis optimizations.

REFERENCES

• 1: Jian Li , Rajesh K. Gupta, HDL optimization using timed decision tables, Proceedings of the 33rd annual conference on Design automation, p.51-54, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240528]
• 2: Jian Li , Rajesh K. Gupta, Limited exception modeling and its use in presynthesis optimizations, Proceedings of the 34th annual conference on Design automation, p.341-346, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266136]
• 3: Daniel D. Gajski , Frank Vahid , Sanjiv Narayan , Jie Gong, Specification and design of embedded systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 4: J. Li and R. K. Gupta, "System modeling and presynthesis using timed decision tables," Tech. Rep. UCI ICS- TR-97-12, University of California, March 1997.
• 5: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 6: R. Brayton and C. McMullen, "The decomposition and factorization of boolean expressions," in Proceedings of the IEEE International Symposium on Circuits and Systems, 1982.
• 7: Giovanni De Micheli , David Ku , Frederic Mailhot , Thomas Truong, The Olympus Synthesis System, IEEE Design & Test, v.7 n.5, p.37-53, September 1990 [doi>10.1109/54.60605]
• 8: M. M. Ligthard, A. Bechtolsheim, G. D. Micheli, and A. E. Gamal, "Design of a digital input output chip," in Custom IC Conference, May 1989.
• 9: David C. Ku , Giovanni De Micheli, High level synthesis of ASICs under timing and synchronization constraints, Kluwer Academic Publishers, Norwell, MA, 1992

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Hardware description languages

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Optimization

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Benchmarks

General Terms:
Algorithms, Design, Languages, Measurement, Performance, Standardization, Theory

Keywords:
TDT decomposition, behavioral HDL description, benchmarks, circuit synthesis, decision tables, kernel extraction algorithm, optimized HDL description, presynthesis optimizations, system behavior model, timed decision table decomposition