research-article

A Regular Layout for Parallel Adders

Authors:

R. P. Brent,

H. T. KungAuthors Info & Claims

IEEE Transactions on Computers, Volume 31, Issue 3

Pages 260 - 264

https://doi.org/10.1109/TC.1982.1675982

Published: 01 March 1982 Publication History

Publisher Site

Abstract

With VLSI architecture, the chip area and design regularity represent a better measure of cost than the conventional gate count. We show that addition of n-bit binary numbers can be performed on a chip with a regular layout in time proportional to log n and with area proportional to n.

References

[1]

R. P. Brent, "On the addition of binary numbers," IEEE Trans. Comput., vol. C-19, pp. 758-759, 1970.

Digital Library

Google Scholar

[2]

R. P. Brent and H. T. Kung, "The chip complexity of binary arithmetic," in Proc. 12th Annu. ACM Symp. Theory of Comput., Apr. 1980, pp. 190-200.

Digital Library

Google Scholar

[3]

R. P. Brent and H. T. Kung, "The area-time complexity of binary multiplication," J. Ass. Comput. Mach., vol. 28, pp. 521-534, July 1981.

Digital Library

Google Scholar

[4]

H. L. Garner, "A survey of some recent contributions to computer arithmetic," IEEE Trans. Comput., vol. C-25, pp. 1277-1282, 1976.

Digital Library

Google Scholar

[5]

L. Guibas and J. Vuillemin, private communication, Aug. 1980.

Google Scholar

[6]

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

Digital Library

Google Scholar

[7]

D. J. Kuck, The Structure of Computers and Computations. New York: Wiley, 1978.

Digital Library

Google Scholar

[8]

R. E. Ladner and M. J. Fischer, "Parallel prefix computation," J. Ass. Comput. Mach., vol. 27, pp. 831-838, Oct. 1980.

Digital Library

Google Scholar

[9]

C. E. Leiserson, "Area-efficient VLSI computation," Ph.D. dissertation, Dep. Comput. Sci., Carnegie-Mellon Univ., Pittsburgh, PA, 1981.

Digital Library

Google Scholar

[10]

C. A. Mead and L. A. Conway, Introduction to VISI Systems. Reading, MA: Addison-Wesley, 1980.

Digital Library

Google Scholar

[11]

J. E. Savage, The Complexity of Computing. New York: Wiley 1976.

Google Scholar

[12]

C. D. Thompson, "Area-time complexity for VLSI," in Proc. 11th Annu. ACM Symp. Theory of Com put., May 1979, pp. 81-88.

Digital Library

Google Scholar

[13]

C. Tung, "Arithmetic," in Computer SCience, A. F. Cardenas, L. Press, and M. A. Marin, Eds. New York: Wiley-Interscience. 1972.

Google Scholar

[14]

S. Winograd, "On the time required to perform addition," J. Ass. Comput. Mach., vol. 12, no. 2, pp. 277-285, 1965.

Digital Library

Google Scholar

Cited By

View all

Hiruma GYang MLi YSakiyama KHara-Azumi Y(2024)High-Level Synthesis Countermeasure Using Threshold Implementation with Mixed Number of SharesProceedings of the 14th International Symposium on Highly Efficient Accelerators and Reconfigurable Technologies10.1145/3665283.3665286(18-26)Online publication date: 19-Jun-2024
https://dl.acm.org/doi/10.1145/3665283.3665286
de Wolff Ivan Balen DKeller GMcDonell T(2024)Zero-Overhead Parallel Scans for Multi-Core CPUsProceedings of the 15th International Workshop on Programming Models and Applications for Multicores and Manycores10.1145/3649169.3649248(52-61)Online publication date: 3-Mar-2024
https://dl.acm.org/doi/10.1145/3649169.3649248
Biryukov AFisch BHerold GKhovratovich DLeurent GNaya-Plasencia MWesolowski B(2024)Cryptanalysis of Algebraic Verifiable Delay FunctionsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68382-4_14(457-490)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68382-4_14
Show More Cited By

A Regular Layout for Parallel Adders
1. Hardware

Recommendations

An area-time efficient NMOS adder

A model of computation for VLSI systems has been developed based on the Mead and Conway approach. This model accommodates the fan-out dependency in NMOS technology. Based on this model, a method for producing area-time efficient carry lookahead adders ...
Integer Division in Linear Time with Bounded Fan-In

A binary algorithm for division of an (M + N)-bit integer by an N-bit integer is presented. The algorithm produces the (M + 1)-bit quotient and the N-bit remainder in time O(M + N). Two hardware implementations, one using combinational logic in cellular ...
A Heuristic for Suffix Solutions

The suffix problem has appeared in solutions of recurrence systems for parallel and pipelined machines and more recently in the design of gate and silicon compilers. In this paper we present two algorithms. The first algorithm generates parallel suffix ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 31, Issue 3

March 1982

89 pages

ISSN:0018-9340

Issue’s Table of Contents

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 March 1982

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

135
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hiruma GYang MLi YSakiyama KHara-Azumi Y(2024)High-Level Synthesis Countermeasure Using Threshold Implementation with Mixed Number of SharesProceedings of the 14th International Symposium on Highly Efficient Accelerators and Reconfigurable Technologies10.1145/3665283.3665286(18-26)Online publication date: 19-Jun-2024
https://dl.acm.org/doi/10.1145/3665283.3665286
de Wolff Ivan Balen DKeller GMcDonell T(2024)Zero-Overhead Parallel Scans for Multi-Core CPUsProceedings of the 15th International Workshop on Programming Models and Applications for Multicores and Manycores10.1145/3649169.3649248(52-61)Online publication date: 3-Mar-2024
https://dl.acm.org/doi/10.1145/3649169.3649248
Biryukov AFisch BHerold GKhovratovich DLeurent GNaya-Plasencia MWesolowski B(2024)Cryptanalysis of Algebraic Verifiable Delay FunctionsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68382-4_14(457-490)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68382-4_14
Koizumi TShioya RSugita SAmano TDegawa YKadomoto JIrie HSakai S(2023)Clockhands: Rename-free Instruction Set Architecture for Out-of-order ProcessorsProceedings of the 56th Annual IEEE/ACM International Symposium on Microarchitecture10.1145/3613424.3614272(1-16)Online publication date: 28-Oct-2023
https://dl.acm.org/doi/10.1145/3613424.3614272
Cheng JXiao YShao YDong GLyu SYu W(2023)Machine-learning-driven Architectural Selection of Adders and Multipliers in Logic SynthesisACM Transactions on Design Automation of Electronic Systems10.1145/356071228:2(1-16)Online publication date: 6-Mar-2023
https://dl.acm.org/doi/10.1145/3560712
Guo GHuang TLin YGuo ZYellapragada SWong M(2023)A GPU-Accelerated Framework for Path-Based Timing AnalysisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.327227442:11(4219-4232)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1109/TCAD.2023.3272274
Nam KOh HMoon HPaek YMitra TYoung EXiong J(2022)Accelerating N-Bit Operations over TFHE on Commodity CPU-FPGAProceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design10.1145/3508352.3549413(1-9)Online publication date: 30-Oct-2022
https://dl.acm.org/doi/10.1145/3508352.3549413
Brenner USilvanus AWang T(2022)Delay Optimization of Combinational Logic by AND-OR Path RestructuringProceedings of the 27th Asia and South Pacific Design Automation Conference10.1109/ASP-DAC52403.2022.9712548(403-409)Online publication date: 17-Jan-2022
https://dl.acm.org/doi/10.1109/ASP-DAC52403.2022.9712548
He ZWang ZBail CYang HYu B(2021)Graph Learning-Based Arithmetic Block Identification2021 IEEE/ACM International Conference On Computer Aided Design (ICCAD)10.1109/ICCAD51958.2021.9643581(1-8)Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1109/ICCAD51958.2021.9643581
Roy RRaiman JKant NElkin IKirby RSiu MOberman SGodil SCatanzaro B(2021)PrefixRL: Optimization of Parallel Prefix Circuits using Deep Reinforcement Learning2021 58th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC18074.2021.9586094(853-858)Online publication date: 5-Dec-2021
https://dl.acm.org/doi/10.1109/DAC18074.2021.9586094
Show More Cited By

Abstract

References

Cited By

Recommendations

An area-time efficient NMOS adder

Integer Division in Linear Time with Bounded Fan-In

A Heuristic for Suffix Solutions

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations