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

Ruiming Chen*, Hai Zhou

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-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 languageEnglish (US)
Article number4351998
Pages (from-to)2069-2073
Number of pages5
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume26
Issue number11
DOIs
StatePublished - Nov 2007

Keywords

  • Buffer insertion
  • Network flow
  • Timing optimization

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'An Effective algorithm for buffer insertion in general circuits based on network flow'. Together they form a unique fingerprint.

Cite this