The use of carry-save representation in joint module selection and retiming

ABSTRACT

Joint module selection and retiming is a powerful technique to optimize the implementation cost and the speed of a circuit specified using a synchronous data-flow graph (DFG). In implementing high-speed circuits, the use of carry-save signal representation is also a powerful technique to optimize the implementation cost and the speed of arithmetic circuits. This paper is the first to combine these two techniques to solve the joint module selection and retiming problem while allowing the use of carry-save representation. To solve this problem efficiently, we first propose a mixed-representation data-flow graph (MFG) that allows signals to be expressed in carry-save representation. We also propose techniques to accurately model the costs associated with different signal representations. In addition, we propose a solution-space pruning technique that significantly reduces the run-time of our algorithm. Our algorithm, by allowing carry-save representation, can produce a wider range of solutions. In our experiments, our fastest implementation is 28% faster and our smallest implementation is 47% smaller, in comparison to solutions obtained using the previously known joint module selection and retiming technique.

REFERENCES

• 1: ILOG CPLEX User's Manual, March 1999.
• 2: S. Heemstra de Groot, S. Gerez, and O. Herrmann. Range-chart-guided iterative data-flow graph scheduling. IEEE Trans. on Circuits and Systems I: Fundamental Theory and Applications, 39(5):351-364, May 1992.
• 3: Kazuhito Ito , Lori E. Lucke , Keshab K. Parhi, ILP-based cost-optimal DSP synthesis with module selection and data format conversion, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.6 n.4, p.582-594, Dec. 1998 [doi>10.1109/92.736132]
• 4: 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]
• 5: C. Leiserson, F. Rose, and J. Saxe. Optimizing synchronous circuitry by retiming (preliminary version). In Third Caltech Conference on Very Large Scale Integration, pages 87-116, March 1983.
• 6: S. Note, F. Catthoor, G. Goossens, and H. De Man. Combined hardware selection and pipelining in high-performance data-path design. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 11(4):413-423, April 1992.

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.3 Interconnections (subsystems)
          Subjects: Asynchronous/synchronous operation
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Data-path design
  B.7 INTEGRATED CIRCUITS
  B.8 Performance and Reliability

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