Network flow based buffer planning

Xiaoping Tang*, D. F. Wong

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

5 Citations (Scopus)


The problem of planning the locations of large number of buffers is of utmost importance in deep submicron VLSI design. Recently, [Cong, Kong, and Pan ICCAD-99, 1999, p. 358] proposed an algorithm to directly address this problem. Given a placement of circuit blocks, a key step in [1] is to use the free space between the circuit blocks for inserting as many buffers as possible. This step is very important because if all buffers can be inserted into existing spaces, no expansion of chip area would be needed. An effective greedy heuristic was used in [1] for this step. In this paper, we give a polynomial-time optimal algorithm for solving the problem of inserting maximum number of buffers into the free space between the circuit blocks. In the case where the "costs" of placing a buffer at different locations are different, we can guarantee to insert maximum number of buffers with minimum total cost. Our algorithm is based on efficient min-cost network-flow computations.

Original languageEnglish
Pages (from-to)143-155
Number of pages13
JournalIntegration, the VLSI Journal
Issue number2
Publication statusPublished - Oct 2001

Scopus Subject Areas

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering

User-Defined Keywords

  • Buffer insertion
  • Buffer planning
  • CAD
  • Network flow
  • VLSI


Dive into the research topics of 'Network flow based buffer planning'. Together they form a unique fingerprint.

Cite this