Area minimization algorithm for parallel prefix adders under bitwise delay constraints

Taeko Matsunaga, Yusuke Matsunaga

Research output: Chapter in Book/Report/Conference proceedingConference contribution

21 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationGLSVLSI'07
Subtitle of host publicationProceedings of the 2007 ACM Great Lakes Symposium on VLSI
Number of pages6
Publication statusPublished - 2007
Event17th Great Lakes Symposium on VLSI, GLSVLSI'07 - Stresa-Lago Maggiore, Italy
Duration: Mar 11 2007Mar 13 2007

Publication series

NameProceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI


Other17th Great Lakes Symposium on VLSI, GLSVLSI'07
CityStresa-Lago Maggiore

All Science Journal Classification (ASJC) codes

  • General Engineering


Dive into the research topics of 'Area minimization algorithm for parallel prefix adders under bitwise delay constraints'. Together they form a unique fingerprint.

Cite this