Network flow based buffer planning

The problem of planning the locations of large number of buffers is of utmo st importance in deep submicron VLSI design. Recently, [Cong, Kong, and Pan ICCAD-99, 1999, p. 358] proposed an algorithm to directly address this pro blem. 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 poss ible. This step is very important because if all buffers can be inserted in to 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 p olynomial-time optimal algorithm for solving the problem of inserting maxim um 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 diff erent, we can guarantee to insert maximum number of buffers with minimum to tal cost. Our algorithm is based on efficient min-cost network-flow computa tions. (C) 2001 Elsevier Science B.V. All rights reserved.