skip to main content
10.1145/1228784.1228886acmconferencesArticle/Chapter ViewAbstractPublication PagesglsvlsiConference Proceedingsconference-collections
Article

Area minimization algorithm for parallel prefix adders under bitwise delay constraints

Published: 11 March 2007 Publication History

Abstract

This paper addresses parallel prefix adder synthesis which targets area minimization under given timing constraints. This problem is treated as synthesis of prefix graphs which represent global structures of parallel prefix adders, and a two-folded robust heuristic is proposed. The first process is dynamic programming based area minimization (DPAM), where the search space is limited to a specific subset of the whole set of prefix graphs by imposing some restrictions on structure of prefix graphs, and an exact minimum prefix graph for the limited space can be found efficiently by dynamic programming. The second process is area reduction with re-structuring (ARRS),which removes imposed restrictions on structure, and restructures the result of DPAM for further area reduction. Experimental results show that the size of prefix graph can be reduced by about 10% compared to an existing approach, and area at gate level can also be reduced by more than 30% compared to a commercial tool in some case.

References

[1]
R. P. Brent and H. T. Kung. A regular layout for parallel adders. IEEE Trans. Computers, 31(3):260--264, March 1982.
[2]
P. M. Kogge and H. S. Stone. A parallel algorithm for the efficient solution of a general class of recurrence equations. IEEE Trans. Computers, 22(8):786--793, August 1973.
[3]
I. Koren. Computer Arithmetic Algorithms. A K Peters, Ltd., 2002.
[4]
J. Liu, S. Zhou, H. Zhu, and C.-K. Cheng. An algorithmic approach for generic parallel adders. In ICCAD, pages 734--740, November 2003.
[5]
R. Rudell. Logic Synthesis for VLSI Design. PhD thesis, University of California, Berkeley, 1989.
[6]
J. Sklansky. Conditional sum addition logic. IRE Trans. Electron. Comput., 9(6):226--231, 1960.
[7]
M. Snir. Depth-size trade-offs for parallel prefix computation. Journal of Algorithms 7, pages 185--201, 1986.
[8]
H. Touati, C. Moon, R. K. Brayton, and A. Wang. Performance-oriented technology mapping. In MIT VLSI Conference, 1990.
[9]
N. H. Weste and D. Harris. CMOS VLSI Design: A Circuits and Systems Perspective, chapter 10. Datapath Subsystems, pages 637--711. Addison Wesley, 2004.
[10]
R. Zimmermann. Non-heuristic optimization and synthesis of parallel-prefix adders. In International Workshop on Logic and Architecture Synthesis, pages 123--132, December 1996.

Cited By

View all
  • (2024)Large circuit models: opportunities and challengesScience China Information Sciences10.1007/s11432-024-4155-767:10Online publication date: 25-Sep-2024
  • (2023)Hierarchical Dense Pattern Detection in TensorsACM Transactions on Knowledge Discovery from Data10.1145/357702217:6(1-29)Online publication date: 28-Feb-2023
  • (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
  • Show More Cited By

Index Terms

  1. Area minimization algorithm for parallel prefix adders under bitwise delay constraints

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      GLSVLSI '07: Proceedings of the 17th ACM Great Lakes symposium on VLSI
      March 2007
      626 pages
      ISBN:9781595936059
      DOI:10.1145/1228784
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 11 March 2007

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. arithmetic synthesis
      2. dynamic programming
      3. parallel prefix adder

      Qualifiers

      • Article

      Conference

      GLSVLSI07
      Sponsor:
      GLSVLSI07: Great Lakes Symposium on VLSI 2007
      March 11 - 13, 2007
      Stresa-Lago Maggiore, Italy

      Acceptance Rates

      Overall Acceptance Rate 312 of 1,156 submissions, 27%

      Upcoming Conference

      GLSVLSI '25
      Great Lakes Symposium on VLSI 2025
      June 30 - July 2, 2025
      New Orleans , LA , USA

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

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

      Other Metrics

      Citations

      Cited By

      View all
      • (2024)Large circuit models: opportunities and challengesScience China Information Sciences10.1007/s11432-024-4155-767:10Online publication date: 25-Sep-2024
      • (2023)Hierarchical Dense Pattern Detection in TensorsACM Transactions on Knowledge Discovery from Data10.1145/357702217:6(1-29)Online publication date: 28-Feb-2023
      • (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
      • (2023)Macro Construction Rules and Optimization for Long Bit Parallel Prefix Adders2023 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS46773.2023.10182180(1-5)Online publication date: 21-May-2023
      • (2022)High-Speed Adder Design Space Exploration via Graph Neural ProcessesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2021.311426241:8(2657-2670)Online publication date: Aug-2022
      • (2022)A novel generic modulo‐2 graph with full set taxonomical conversion to parallel prefix addersInternational Journal of Circuit Theory and Applications10.1002/cta.314850:4(1143-1159)Online publication date: 3-Jan-2022
      • (2021)Minimum Structural Transformation in Parallel Prefix Adders and Its Application to Search-Based Optimization2021 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS51556.2021.9401550(1-5)Online publication date: May-2021
      • (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
      • (2020)A New Implementation of 16-bit Parallel Prefix Adder for High Speed and Low AreaProceedings of the 2020 4th International Conference on Digital Signal Processing10.1145/3408127.3408185(284-288)Online publication date: 19-Jun-2020
      • (2020)Insertion-Based Procedural Construction and Optimization of Parallel Prefix Adders2020 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS45731.2020.9181184(1-5)Online publication date: Oct-2020
      • Show More Cited By

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media