Improved merging of datapath operators using information content and required precision analysis

ABSTRACT

We introduce the notions of required precision and information content of datapath signals and use them to define functionally safe transformations on data ow graphs. These transformations reduce widths of datapath operators and enhance their mergeability. Using efficient algorithms to compute required precision and information content of signals, we define a new algorithm for partitioning a data flow graph consisting of datapath operators into mergeable clusters. Experimental results indicate that use of our clustering algorithm for operator merging based synthesis of datapath intensive designs, can lead to significant improvement in the delay and area of the implementation.

REFERENCES

• 1: D. A. Huffman, A method for the construction of minimum-redundancy codes, Proceedings of the IRE, 40(9), 1952, pp. 1098-1101.
• 2: Taewhan Kim , William Jao , Steve Tjiang, Arithmetic optimization using carry-save-adders, Proceedings of the 35th annual conference on Design automation, p.433-438, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277166]
• 3: Amos R. Omondi, Computer arithmetic systems: algorithms, architecture and implementation, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1994
• 4: Junhyung Um , Taewhan Kim , C. L. Liu, Optimal allocation of carry-save-adders in arithmetic optimization, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.410-413, November 07-11, 1999, San Jose, California, United States
• 5: Junhyung Um , Taewhan Kim , C. L. Liu, A fine-grained arithmetic optimization technique for high-performance/low-power data path synthesis, Proceedings of the 37th conference on Design automation, p.98-103, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337325]
• 6: C. S. Wallace, "A suggestion for a fast multiplier" IEEE Trans. Electron. Comput., Feb. 1964, vol EC-13, pp.14-17.
• 7: Neil H. E. Weste , Kamran Eshraghian, Principles of CMOS VLSI design: a systems perspective, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
• 8: Markus Willems , Volker Bürsgens , Holger Keding , Thorsten Grötker , Heinrich Meyr, System level fixed-point design based on an interpolative approach, Proceedings of the 34th annual conference on Design automation, p.293-298, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266105]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Data-path design

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Simulation
  B.8 Performance and Reliability

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

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