Signal representation guided synthesis using carry-save adders for synchronous data-path circuits

ABSTRACT

Arithmetic transformations using carry-save adders have been exploited recently in design automation but existing transformation approaches only optimize combinatorial functions. Most applications need synchronous circuits and it is known that techniques that move the positions of the registers, such as retiming, can significantly reduce the cycle time of a synchronous circuit. However, retiming disregards arithmetic transformations and its power is limited by the circuit topology. This work is the first to exploit carry-save arithmetic transformations together with the moving of the register positions. To enable such transformations, we first propose the use of a new multiple-vector signal representation. Next, we use multiple-vector signal representation as a common guide for all of our simultaneous carry-save arithmetic transformations with the moving of the register positions. Specifically, we propose, operation forward and operation backward carry-save transformations, which are transformations across register boundaries. We also propose operation duplicate and operation merge transformations to exploit the resource sharing and timing trade-offs in the implementation of a multiple-fanout network. Finally, we propose an efficient and effective heuristic that selectively applies a sequence of transformations to optimize the timing and the area of a synchronous circuit. Experimental results show that the proposed techniques significantly out-perform previous approaches.

REFERENCES

• 1: 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]
• 2: Taewhan Kim , Junhyung Um, A timing-driven synthesis of arithmetic circuits using carry-save-adders (short paper), Proceedings of the 2000 conference on Asia South Pacific design automation, p.313-316, January 2000, Yokohama, Japan [doi>10.1145/368434.368656]
• 3: Y. Kim and T. Kim, "An accurate exploration of timing and area trade-offs in arithmetic optimization using carry-save adder cells," in Proc. Midwest Synposium on Circuit and Systems, Aug. 2000.
• 4: C.E. Leiserson, F.M. Rose, and J.B. Saxe, "Optimizing synchronous circuitry by retiming (preliminary version)," in Third Caltech Conf. on Very Large Scale Integration, Mar. 1983, pp. 87-116.
• 5: Zhan Yu , Kei-Yong Khoo , Alan N. Willson, Jr., The use of carry-save representation in joint module selection and retiming, Proceedings of the 37th conference on Design automation, p.768-773, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337773]
• 6: G. De Micheli, "Synchronous logic synthesis: Algorithms for cycle-time minimization," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 10, pp. 63-73, Jan. 1991.
• 7: 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

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

  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