Limited exception modeling and its use in presynthesis optimizations

ABSTRACT

In behavioral descriptions, statementsthat allow limited control jumps, such as Verilog disablestatements on named blocks, are often used for describingsystem behavior in presence of exceptions.In this paper,we extend Timed Decision Tables (TDT), a tabularbehavior model, to represent more general control structuresincluding exceptions.We introduce the notion of action sharing that allows us to reduce resoruce requirementsusing existing high-level synthesis tools on descriptionswith control exceptions.We present presynthesisalgorithms that work on the extended TDT model and analgorithm that performs action sharing in TDT models.Our experiments on well-known HardwareC benchmarksshow size reduction resulting from sharing actions in theinput behavioral descriptions.

REFERENCES

• 1: Donald E. Thomas , Philip R. Moorby, The Verilog hardware description language (4th ed.), Kluwer Academic Publishers, Norwell, MA, 1998
• 2: Claudionor N. Coelho, Jr. , Giovanni De Micheli, Dynamic scheduling and synchronization synthesis of concurrent digital systems under system-level constraints, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.175-181, November 06-10, 1994, San Jose, California, United States
• 3: 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
• 4: 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]
• 5: Donald E. Thomas , Elizabeth D. Lagnese , John A. Nestor , Jayanth V. Rajan , Robert L. Blackburn , Robert A. Walker, Algorithmic and Register-Transfer Level Synthesis: The System Architect's Workbench, Kluwer Academic Publishers, Norwell, MA, 1989
• 6: R. K. Brayton, R. Camposano, G. D. Micheli, R. Otten, and J. van Eijndhoven, "The Yorktown Silicon Compiler System," in Silicon Compilation (D. Gajski, ed.), pp. 204-310, Addison Wesley, 1988.
• 7: 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]
• 8: Kamlesh Rath , M. Esen Tuna , Steven D. Johnson, Behavior tables: a basis for system representation and transformational system synthesis, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.736-740, November 07-11, 1993, Santa Clara, California, United States
• 9: A. J. W. M. ten Berg , C. Huijs , Th. Krol, Relational algebra as formalism for hardware design, Microprocessing and Microprogramming, v.38 n.1-5, p.403-410, Sept. 1993
• 10: 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.
• 11: Brenda S. Baker, An Algorithm for Structuring Flowgraphs, Journal of the ACM (JACM), v.24 n.1, p.98-120, Jan. 1977 [doi>10.1145/321992.321999]
• 12: L. Dumitrascu and A. Ioachim, Generating Fortran Pragrams from Decision Tables. EDITURA ACADEMIEI, 1990.
• 13: T. Yasui, "Conversion of Decision Tables into Decision Trees," Tech. Rep. UIUCDCS-R-72-501, University of Illinois, February 1972.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization

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

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