
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

TimingConstrained Area Minimization Algorithm for Parallel Prefix Adders
Taeko MATSUNAGA Yusuke MATSUNAGA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E90A
No.12
pp.27702777 Publication Date: 2007/12/01
Online ISSN: 17451337
DOI: 10.1093/ietfec/e90a.12.2770
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms) Category: Logic Synthesis and Verification Keyword: parallel prefix adder, arithmetic synthesis, dynamic programming,
Full Text: PDF>>
Summary:
This paper addresses parallel prefix adder synthesis which targets area minimization under given bitwise timing constraints. This problem is treated as a problem to synthesize prefix graphs which represent global structures of parallel prefix adders at technologyindependent level, and a twofolded algorithm to minimize area of prefix graphs is proposed. The first process is dynamic programming based area minimization (DPAM), which focuses on a specific subset of prefix graphs and finds an exact minimum solution for the subset by dynamic programming. The subset is defined by imposing some restrictions on structures of prefix graphs. By utilizing these restrictions, DPAM can find the minimum solutions efficiently for practical bit width. The second process is area reduction with restructuring (ARRS), which removes the imposed restrictions on structures, and restructures the result of DPAM for further area reduction while satisfying timing constraints. Experimental results show that smaller area can be achieved compared to existing methods both at prefix graph level and at gate level.

