Efficient algorithms for buffer insertion in general circuits based on network flow

Ruiming Chen*, Hai Zhou

*Corresponding author for this work

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

11 Scopus citations

Abstract

With shrinking VLSI feature sizes and increasing overall chip areas, buffering has emerged as an effective solution to the problem of growing interconnect delays in modern designs. The problem of buffer insertion in a single net has been the focus of most previous researches. However, efficient algorithms for buffer insertion in whole circuits are generally needed. In this paper, we relate the timing constrained minimal buffer insertion problem to the min-cost flow dual problem, and propose two algorithms based on min-cost flow and min-cut techniques, respectively, to solve it in combinational circuits. We compare our approaches to a traditional approach based on Lagrangian relaxation. Experimental results demonstrate that our approaches are efficient and effective. On the average, our approaches achieve 45% and 39% reduction, respecitively, on the number of buffers inserted in comparison to the traditional approach.

Original languageEnglish (US)
Title of host publicationProceedings of theICCAD-2005
Subtitle of host publicationInternational Conference on Computer-Aided Design
Pages322-326
Number of pages5
DOIs
StatePublished - 2005
EventICCAD-2005: IEEE/ACM International Conference on Computer-Aided Design, 2005 - San Jose, CA, United States
Duration: Nov 6 2005Nov 10 2005

Publication series

NameIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
Volume2005
ISSN (Print)1092-3152

Other

OtherICCAD-2005: IEEE/ACM International Conference on Computer-Aided Design, 2005
CountryUnited States
CitySan Jose, CA
Period11/6/0511/10/05

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design

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

Cite this