Automatic synthesis of compressor trees: reevaluating large counters

ABSTRACT

Despite the progress of the last decades in electronic design automation, arithmetic circuits have always received way less attention than other classes of digital circuits. Logic synthesisers, which play a fundamental role in design today, play a minor role on most arithmetic circuits, performing some local optimisations but hardly improving the overall structure of arithmetic components. Architectural optimisations have been often studied manually, and only in the case of very common building blocks such as fast adders and multi-input adders, ad-hoc techniques have been developed. A notable case is multi-input addition, which is the core of many circuits such as multipliers, etc. The most common technique to implement multi-input addition is using compressor trees, which are often composed of carry-save adders (based on (3 : 2) counters, i.e., full adders). A large body of literature exists to implement compressor trees using large counters. However, all the large counters were built by using full and half adders recursively. In this paper we give some definite answers to issues related to the use of large counters. We present a general technique to implement large counters whose performance is much better than the ones composed of full and half adders. Also we show that it is not always useful to use larger optimised counters and sometimes a combination of various size counters gives the best performance. Our results show 15% improvement in the critical path delay. In some cases even hardware area is reduced by using our counters.

REFERENCES

• 1: L. Dadda. Some schemes for parallel multipliers. Alta Frequenza, XXXIV:349--56, 1965.
• 2: L. Dadda and D. Ferrari. Digital multipliers: A unified approach. Alta Frequenza, XXXVII(11):1079--86, Nov. 1968.
• 3: J. Fadavi-Ardekani. M x N Booth encoded multiplier generator using optimized Wallace trees. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, VLSI-1(2):120--25, June 1993.
• 4: ILOG. CPLEX Optimization Engine, 2006. Version 10.0
• 5: Vojin G. Oklobdzija , David Villeger , Simon S. Liu, A Method for Speed Optimized Partial Product Reduction and Generation of Fast Parallel Multipliers Using an Algorithmic Approach, IEEE Transactions on Computers, v.45 n.3, p.294-306, March 1996 [doi>10.1109/12.485568]
• 6: P. Song and G. De Micheli. Circuit and architecture trade-offs for high speed multiplication. IEEE Journal of Solid-State Circuits, 26(9), Sept. 1991.
• 7: Paul F. Stelling , Charles U. Martel , Vojin G. Oklobdzija , R. Ravi, Optimal Circuits for Parallel Multipliers, IEEE Transactions on Computers, v.47 n.3, p.273-285, March 1998 [doi>10.1109/12.660163]
• 8: Paul F. Stelling , Vojin G. Oklobdzija, Design strategies for optimal hybrid final adders in a parallel multiplier, Journal of VLSI Signal Processing Systems, v.14 n.3, p.321-331, Dec. 1996 [doi>10.1007/BF00929625]
• 9: E. E. Swartzlander, Jr. Parallel counters. IEEE Transactions on Computers, C-22(11):1021--24, Nov. 1973.
• 10: Synopsys. Creating High-Speed Data-Path Components---Application Note, Aug. 2001. Version 2001.08.
• 11: Junhyung Um , Taewhan Kim, An Optimal Allocation of Carry-Save-Adders in Arithmetic Circuits, IEEE Transactions on Computers, v.50 n.3, p.215-233, March 2001 [doi>10.1109/12.910813]
• 12: A. K. Verma , P. Ienne, Improved use of the carry-save representation for the synthesis of complex arithmetic circuits, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.791-798, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382683]
• 13: A. K. Verma and P. Ienne. Improving XOR-dominated arithmetic circuits by exploiting dependencies between operands. In Proceedings of the Asia and South Pacific Design Automation Conference, Yokohama, Japan, Jan. 2007.
• 14: C. S. Wallace. A suggestion for a fast multiplier. IEEE Transactions on Electronic Computers, C-13(2):14--17, Feb. 1964.
• 15: A. Weinberger. 4:2 carry-save adder module. IBM Technical Disclosure Bulletin, 23, Jan. 1981.