Optimizing high speed arithmetic circuits using three-term extraction

ABSTRACT

Carry Save Adder (CSA) trees are commonly used for high speed implementation of multi-operand additions. We present a method to reduce the number of the adders in CSA trees by extracting common three-term subexpressions. Our method can optimize multiple CSA trees involving any number of variables. This optimization has a significant impact on the total area of the synthesized circuits, as we show in our experiments. To the best of our knowledge, this is the only known method for eliminating common subexpressions in CSA structures. Since extracting common subexpressions can potentially increase delay, we also present a delay aware extraction algorithm that takes into account the different arrival times of the signals.

REFERENCES

• 1: Behrooz Parhami, Computer arithmetic: algorithms and hardware designs, Oxford University Press, Oxford, 1999
• 2: 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]
• 3: 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]
• 4: Junhyung Um , Taewhan Kim, Layout-aware synthesis of arithmetic circuits, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513971]
• 5: 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]
• 6: 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
• 7: 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]
• 8: Anup Hosangadi , Farzan Fallah , Ryan Kastner, Common Subexpression Elimination Involving Multiple Variables for Linear DSP Synthesis, Proceedings of the Application-Specific Systems, Architectures and Processors, 15th IEEE International Conference on (ASAP'04), p.202-212, September 27-29, 2004 [doi>10.1109/ASAP.2004.14]
• 9: Anup Hosangadi , Farzan Fallah , Ryan Kastner, Reducing hardware complexity of linear DSP systems by iteratively eliminating two-term common subexpressions, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120953]
• 10: M. Potkonjak, M. B. Srivastava, and A. P. Chandrakasan, "Multiple Constant Multiplications: Efficient and Versatile Framework and Algorithms for Exploring Common Subexpression Elimination," IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 1996.
• 11: Anup Hosangadi , Farzan Fallah , Ryan Kastner, Reducing hardware complexity of linear DSP systems by iteratively eliminating two-term common subexpressions, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120953]
• 12: I. E. G. Richardson, H.264 and MPEG-4 Video Compression: John Wiley and Sons, 2003.
• 13: Sanjit K. Mitra, Digital Signal Processing: A Computer-Based Approach, McGraw-Hill School Education Group, 2001
• 14: Alexandru Nicolau , Roni Potasmann, Incremental tree height reduction for high level synthesis, Proceedings of the 28th conference on ACM/IEEE design automation, p.770-774, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127767]