Arithmetic optimization using carry-save-adders

ABSTRACT

Carry-save-adder(CSA) is the most often used type of operation in implementing a fast computation of arithmetics of register-transfer level design in industry. This paper establishes a relationship between the properties of arithmetic computations and several optimizing transformations using CSAs to derive consistently better qualities of results than those of manual implementations. In particular, we introduce two important concepts, operation-duplication and operation-split, which are the main driving techniques of our algorithm for achieving an extensive utilization of CSAs. Experimental results from a set of typical arithmetic computations found in industry designs indicate that automating CSA optimization with our algorithm produces designs with significantly faster timing and less area.

REFERENCES

• 1: Neil H. E. Weste , Kamran Eshraghian, Principles of CMOS VLSI design: a systems perspective, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
• 2: M. Potkonjak and J. Rabaey, "Optimizing Resource Utilization Using Transformations", Proc. of ICCA D, pp. 88-91, 1991.
• 3: Donald A. Lobo , Barry M. Pangrle, Redundant operator creation: a scheduling optimization technique, Proceedings of the 28th conference on ACM/IEEE design automation, p.775-778, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127768]
• 4: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 5: Kai Hwang, Computer Arithmetic: Principles, Architecture and Design, John Wiley & Sons, Inc., New York, NY, 1979
• 6: Synopsys Inc., Design Ware Components Databook, 1996.
• 7: LSI Logic Inc., Gl O-pCell- Based A SIC Products Databook, 1996.

INDEX TERMS

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

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

  C. Computer Systems Organization

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

  J. Computer Applications

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

Keywords:
ISM frequency band, RF CMOS, digital radio, spread spectrum communication, transceiver