Timing-Constrained Area Minimization Algorithm for Parallel Prefix Adders

Taeko MATSUNAGA; Yusuke MATSUNAGA

doi:10.1093/ietfec/e90-a.12.2770

Timing-Constrained Area Minimization Algorithm for Parallel Prefix Adders

Taeko MATSUNAGA, Yusuke MATSUNAGA

Full Text Views

0

Share
Cite this

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 technology-independent level, and a two-folded 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 re-structuring (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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E90-A No.12 pp.2770-2777

Publication Date: 2007/12/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e90-a.12.2770

Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)

Category: Logic Synthesis and Verification

Cite this

Copy

Taeko MATSUNAGA, Yusuke MATSUNAGA, "Timing-Constrained Area Minimization Algorithm for Parallel Prefix Adders" in IEICE TRANSACTIONS on Fundamentals, vol. E90-A, no. 12, pp. 2770-2777, December 2007, doi: 10.1093/ietfec/e90-a.12.2770.
Abstract: 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 technology-independent level, and a two-folded 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 re-structuring (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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e90-a.12.2770/_p

Copy

@ARTICLE{e90-a_12_2770,
author={Taeko MATSUNAGA, Yusuke MATSUNAGA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Timing-Constrained Area Minimization Algorithm for Parallel Prefix Adders},
year={2007},
volume={E90-A},
number={12},
pages={2770-2777},
abstract={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 technology-independent level, and a two-folded 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 re-structuring (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.},
keywords={},
doi={10.1093/ietfec/e90-a.12.2770},
ISSN={1745-1337},
month={December},}

Copy

TY - JOUR
TI - Timing-Constrained Area Minimization Algorithm for Parallel Prefix Adders
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2770
EP - 2777
AU - Taeko MATSUNAGA
AU - Yusuke MATSUNAGA
PY - 2007
DO - 10.1093/ietfec/e90-a.12.2770
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E90-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2007
AB - 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 technology-independent level, and a two-folded 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 re-structuring (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.
ER -