Article

Free access

Optimal allocation of carry-save-adders in arithmetic optimization

Authors:

Junhyung Um,

Taewhan Kim,

C. L. LiuAuthors Info & Claims

ICCAD '99: Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design

Pages 410 - 413

Published: 07 November 1999 Publication History

PDF eReader

Abstract

Carry-save-adder(CSA) is one of the most widely used schemes for fast arithmetic in industry. This paper provides a solution to the problem of finding an optimal-timing allocation of CSAs. Specifically, we present a polynomial time algorithm which finds an optimal-timing CSA allocation for a given arithmetic expression. In addition, we extend our result for CSA allocation to the problem of optimizing arithmetic expressions across the boundary of design hierarchy by introducing a new concept, called auxiliary ports. Our algorithm can be used to carry out the CSA allocation step optimally and automatically, and this can be done within the context of a standard HDL synthesis environment.

References

[1]

N. Weste and K. Eshraghian, Principles of CMOS VLSI Design - A Systems Perspective, Addition-Wesley Publishers, 1985.

Digital Library

Google Scholar

[2]

T. Kim, W. Jao, and S. Tjiang, "Arithmetic Optimization using Carry-Save-Adders", DAC, pp.433-438, 1998.

Digital Library

Google Scholar

[3]

D. Huffman, "A method for the construction of minimum redundancy codes", Proc. of the IRE, Vol.40, pp.1098-1101, 1952.

Crossref

Google Scholar

[4]

D. Parker Jr., "Conditions for optimality of the Huffman algorithm", SlAM Journal of Computing, Vol.9, No.3 pp.470-489, 1980.

Google Scholar

[5]

K. Hwang, Computer Arithmetic: Principles, architecture, and Design, New York, 1979.

Digital Library

Google Scholar

[6]

Synopsys Inc., DesignWare Components Databook, 1998.

Google Scholar

[7]

LSI Logic Inc., GlO-p Cell-BasedASIC Products Databook, 1996.

Google Scholar

Cited By

View all

Hosangadi AFallah FKastner RGielen G(2006)Optimizing high speed arithmetic circuits using three-term extractionProceedings of the conference on Design, automation and test in Europe: Proceedings10.5555/1131481.1131838(1294-1299)Online publication date: 6-Mar-2006
https://dl.acm.org/doi/10.5555/1131481.1131838
Chang YTing KAckland B(2002)Self-referential verification of gate-level implementations of arithmetic circuitsProceedings of the 39th annual Design Automation Conference10.1145/513918.513998(311-316)Online publication date: 10-Jun-2002
https://dl.acm.org/doi/10.1145/513918.513998
Mathur ASaluja SRabaey J(2001)Improved merging of datapath operators using information content and required precision analysisProceedings of the 38th annual Design Automation Conference10.1145/378239.378562(462-467)Online publication date: 22-Jun-2001
https://dl.acm.org/doi/10.1145/378239.378562
Show More Cited By

Index Terms

Optimal allocation of carry-save-adders in arithmetic optimization

Recommendations

Logic Networks of Carry-Save Adders

logic networks of carry-save adders such as high-speed multipliers, multioperand adders, and double-rail input parallel adders are designed based on the parallel adders with a minimum number of NOR gates discussed in [1]. After a discussion of the ...
Design of Residue Generators and Multioperand Modular Adders Using Carry-Save Adders

Residue generator is an essential building block of encoding/decoding circuitry for arithmetic error detecting codes and binary-to-residue number system (RNS) converter. In either case, a residue generator is an overhead for a system and as such it ...
An Optimal Allocation of Carry-Save-Adders in Arithmetic Circuits

Carry-save-adder (CSA) is one of the most widely used components for fast arithmetic in industry. This paper provides a solution to the problem of finding an optimal-timing allocation of CSAs in arithmetic circuits. Namely, we present a polynomial time ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICCAD '99: Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design

November 1999

613 pages

ISBN:0780358325

Publisher

IEEE Press

Publication History

Published: 07 November 1999

Check for updates

Qualifiers

Article

Conference

ICCAD '99

Sponsor:

IEEE-EDS
SIGDA
IEEE-CAS
IEEE-CS

ICCAD '99: The International Conference on Computer Aided Design.

November 7 - 11, 1999

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
423
Total Downloads

Downloads (Last 12 months)48
Downloads (Last 6 weeks)8

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hosangadi AFallah FKastner RGielen G(2006)Optimizing high speed arithmetic circuits using three-term extractionProceedings of the conference on Design, automation and test in Europe: Proceedings10.5555/1131481.1131838(1294-1299)Online publication date: 6-Mar-2006
https://dl.acm.org/doi/10.5555/1131481.1131838
Chang YTing KAckland B(2002)Self-referential verification of gate-level implementations of arithmetic circuitsProceedings of the 39th annual Design Automation Conference10.1145/513918.513998(311-316)Online publication date: 10-Jun-2002
https://dl.acm.org/doi/10.1145/513918.513998
Mathur ASaluja SRabaey J(2001)Improved merging of datapath operators using information content and required precision analysisProceedings of the 38th annual Design Automation Conference10.1145/378239.378562(462-467)Online publication date: 22-Jun-2001
https://dl.acm.org/doi/10.1145/378239.378562
Yu ZYu MWillson ARabaey J(2001)Signal representation guided synthesis using carry-save adders for synchronous data-path circuitsProceedings of the 38th annual Design Automation Conference10.1145/378239.378560(456-461)Online publication date: 22-Jun-2001
https://dl.acm.org/doi/10.1145/378239.378560
Kim YKim TGoto S(2001)Accurate exploration of timing and area trade-offs in arithmetic optimization using carry-save-addersProceedings of the 2001 Asia and South Pacific Design Automation Conference10.1145/370155.370565(622-628)Online publication date: 30-Jan-2001
https://dl.acm.org/doi/10.1145/370155.370565
Kim TUm JYoshida K(2000)A timing-driven synthesis of arithmetic circuits using carry-save-adders (short paper)Proceedings of the 2000 Asia and South Pacific Design Automation Conference10.1145/368434.368656(313-316)Online publication date: 28-Jan-2000
https://dl.acm.org/doi/10.1145/368434.368656
Um JKim TLiu CDe Micheli G(2000)A fine-grained arithmetic optimization technique for high-performance/low-power data path synthesisProceedings of the 37th Annual Design Automation Conference10.1145/337292.337325(98-103)Online publication date: 1-Jun-2000
https://dl.acm.org/doi/10.1145/337292.337325

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Logic Networks of Carry-Save Adders

Design of Residue Generators and Multioperand Modular Adders Using Carry-Save Adders

An Optimal Allocation of Carry-Save-Adders in Arithmetic Circuits