skip to main content
10.5555/1131481.1131838guideproceedingsArticle/Chapter ViewAbstractPublication PagesdateConference Proceedingsconference-collections
Article
Free access

Optimizing high speed arithmetic circuits using three-term extraction

Published: 06 March 2006 Publication History

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]
B. Parhami, Computer Arithmetic: Algorithms and Hardware Designs: Oxford University Press, 2000.
[2]
A. K. Verma and P. Ienne, "Improved use of the carry-save representation for the synthesis of complex arithmetic circuits," presented at International Conference on Computer Aided Design (ICCAD), 2004.
[3]
T. Kim and J. Um, "A timing-driven synthesis of arithmetic circuits using carry-save-adders," presented at Design Automation Conference, 2000. Proceedings of the ASP-DAC 2000. Asia and South Pacific, 2000.
[4]
J. Um and T. Kim, "Layout-aware synthesis of arithmetic circuits," presented at Design Automation Conference (DAC), 2002. Proceedings. 39th, 2002.
[5]
T. Kim, W. Jao, and S. Tjiang, "Arithmetic optimization using carry-save-adders," presented at Design Automation Conference (DAC), 1998. Proceedings, 1998.
[6]
J. Um, T. Kim, and C. L. Liu, "Optimal allocation of carry-save-adders in arithmetic optimization," presented at (ICCAD) Computer-Aided Design, 1999. Digest of Technical Papers. 1999 IEEE/ACM International Conference on, 1999.
[7]
J. Um, T. Kim, and C. L. Liu, "A fine-grained arithmetic optimization technique for high-performance low-power data path synthesis," presented at Design Automation Conference (DAC), 2000. Proceedings 2000. 37th, 2000.
[8]
A. Hosangadi, F. Fallah, and R. Kastner, "Common Subexpression Involving Multiple Variables for Linear DSP Synthesis," presented at IEEE International conference on Application Specific Architectures and Processors (ASAP), Galveston, TX, 2004.
[9]
A. Hosangadi, F. Fallah, and R. Kastner, "Reducing Hardware Complexity of Linear DSP Systems by Iteratively Eliminating Two Term Common Subexpressions," presented at IEEE/ACM Asia South Pacific Design Automation Conference (ASP-DAC), Shanghai, China, 2005.
[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]
A. Hosangadi, F. Fallah, and R. Kastner, "Reducing Hardware complexity by iteratively eliminating two term common subexpressions," presented at Asia South Pacific Design Automation Conference (ASP-DAC), 2005.
[12]
I. E. G. Richardson, H.264 and MPEG-4 Video Compression: John Wiley and Sons, 2003.
[13]
S. K. Mitra, Digital Signal Processing: A computer based approach, second ed: McGraw-Hill, 2001.
[14]
A. Nicolau and R. Potasman, "Incremental tree height reduction for high level synthesis," presented at Design Automation Conference, 1991. 28th ACM/IEEE, 1991.

Cited By

View all
  • (2009)XquasherProceedings of the 46th Annual Design Automation Conference10.1145/1629911.1629980(254-257)Online publication date: 26-Jul-2009
  • (2008)Area optimization algorithms in high-speed digital FIR filter synthesisProceedings of the 21st annual symposium on Integrated circuits and system design10.1145/1404371.1404396(64-69)Online publication date: 1-Sep-2008

Recommendations

Comments

Information & Contributors

Information

Published In

cover image Guide Proceedings
DATE '06: Proceedings of the conference on Design, automation and test in Europe: Proceedings
March 2006
1390 pages
ISBN:3981080106

Sponsors

  • EDAA: European Design Automation Association
  • The EDA Consortium
  • IEEE-CS\DATC: The IEEE Computer Society

Publisher

European Design and Automation Association

Leuven, Belgium

Publication History

Published: 06 March 2006

Qualifiers

  • Article

Acceptance Rates

DATE '06 Paper Acceptance Rate 267 of 834 submissions, 32%;
Overall Acceptance Rate 518 of 1,794 submissions, 29%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)56
  • Downloads (Last 6 weeks)7
Reflects downloads up to 27 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2009)XquasherProceedings of the 46th Annual Design Automation Conference10.1145/1629911.1629980(254-257)Online publication date: 26-Jul-2009
  • (2008)Area optimization algorithms in high-speed digital FIR filter synthesisProceedings of the 21st annual symposium on Integrated circuits and system design10.1145/1404371.1404396(64-69)Online publication date: 1-Sep-2008

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media