An Effective algorithm for buffer insertion in general circuits based on network flow

Ruiming Chen; Hai Zhou

doi:10.1109/TCAD.2007.906481

An Effective algorithm for buffer insertion in general circuits based on network flow

Ruiming Chen^*, Hai Zhou

^*Corresponding author for this work

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

The problem of buffer insertion in a single net has been the focus of most previous research works. However, effective algorithms for buffer insertion in whole circuits are generally needed. In this paper, we relate the timing-constrained minimal buffer insertion problem to the convex cost-flow dual problem and propose an algorithm based on the convex cost-flow theory to solve it in combinational circuits. Experimental results demonstrate that our approach is effective. On the average, for the cases where buffering locations are not specified, our approach achieves a 46% reduction on the total buffer area in comparison to a traditional approach; for the cases where buffering locations are specified, our approach achieves a 52% reduction.

Original language	English (US)
Article number	4351998
Pages (from-to)	2069-2073
Number of pages	5
Journal	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume	26
Issue number	11
DOIs	https://doi.org/10.1109/TCAD.2007.906481
State	Published - Nov 2007

Funding

Manuscript received January 23, 2006; revised May 15, 2006, October 14, 2006, and January 2, 2007. This work was supported by the National Science Foundation under Grant CCR-0238484. This paper was recommended by Associate Editor D. Z. Pan.

Keywords

Buffer insertion
Network flow
Timing optimization

ASJC Scopus subject areas

Software
Computer Graphics and Computer-Aided Design
Electrical and Electronic Engineering

Access to Document

10.1109/TCAD.2007.906481

Cite this

@article{649eecd9d9f04866a0b2c9d853f83e34,

title = "An Effective algorithm for buffer insertion in general circuits based on network flow",

abstract = "The problem of buffer insertion in a single net has been the focus of most previous research works. However, effective algorithms for buffer insertion in whole circuits are generally needed. In this paper, we relate the timing-constrained minimal buffer insertion problem to the convex cost-flow dual problem and propose an algorithm based on the convex cost-flow theory to solve it in combinational circuits. Experimental results demonstrate that our approach is effective. On the average, for the cases where buffering locations are not specified, our approach achieves a 46% reduction on the total buffer area in comparison to a traditional approach; for the cases where buffering locations are specified, our approach achieves a 52% reduction.",

keywords = "Buffer insertion, Network flow, Timing optimization",

author = "Ruiming Chen and Hai Zhou",

note = "Funding Information: Manuscript received January 23, 2006; revised May 15, 2006, October 14, 2006, and January 2, 2007. This work was supported by the National Science Foundation under Grant CCR-0238484. This paper was recommended by Associate Editor D. Z. Pan.",

year = "2007",

month = nov,

doi = "10.1109/TCAD.2007.906481",

language = "English (US)",

volume = "26",

pages = "2069--2073",

journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",

issn = "0278-0070",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "11",

}

TY - JOUR

T1 - An Effective algorithm for buffer insertion in general circuits based on network flow

AU - Chen, Ruiming

AU - Zhou, Hai

N1 - Funding Information: Manuscript received January 23, 2006; revised May 15, 2006, October 14, 2006, and January 2, 2007. This work was supported by the National Science Foundation under Grant CCR-0238484. This paper was recommended by Associate Editor D. Z. Pan.

PY - 2007/11

Y1 - 2007/11

N2 - The problem of buffer insertion in a single net has been the focus of most previous research works. However, effective algorithms for buffer insertion in whole circuits are generally needed. In this paper, we relate the timing-constrained minimal buffer insertion problem to the convex cost-flow dual problem and propose an algorithm based on the convex cost-flow theory to solve it in combinational circuits. Experimental results demonstrate that our approach is effective. On the average, for the cases where buffering locations are not specified, our approach achieves a 46% reduction on the total buffer area in comparison to a traditional approach; for the cases where buffering locations are specified, our approach achieves a 52% reduction.

AB - The problem of buffer insertion in a single net has been the focus of most previous research works. However, effective algorithms for buffer insertion in whole circuits are generally needed. In this paper, we relate the timing-constrained minimal buffer insertion problem to the convex cost-flow dual problem and propose an algorithm based on the convex cost-flow theory to solve it in combinational circuits. Experimental results demonstrate that our approach is effective. On the average, for the cases where buffering locations are not specified, our approach achieves a 46% reduction on the total buffer area in comparison to a traditional approach; for the cases where buffering locations are specified, our approach achieves a 52% reduction.

KW - Buffer insertion

KW - Network flow

KW - Timing optimization

UR - http://www.scopus.com/inward/record.url?scp=64149122388&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=64149122388&partnerID=8YFLogxK

U2 - 10.1109/TCAD.2007.906481

DO - 10.1109/TCAD.2007.906481

M3 - Article

AN - SCOPUS:64149122388

SN - 0278-0070

VL - 26

SP - 2069

EP - 2073

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

IS - 11

M1 - 4351998

ER -

An Effective algorithm for buffer insertion in general circuits based on network flow

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this