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

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.