A fast algorithm for context-aware buffer insertion

Abstract

We study the problem of performing buffer insertion in the context of a given layout in a practical situation, there are restrictions on where buffers may be inserted while routing over such regions may be possible (e.g., due to the presence of macro cells). As a result, it is desirable to perform route planning and biffer insertion simultaneously. Further it is necessary that such an algorithm be aware of the tradeoff between cost (e.g. total capacitance) and delay. In this context we propose the Delay Reduction to Cost Ratio (DRCR) problem and present a fast algorithm for the same. Solutions identified by the algorithm are characterized with respect to the overall cost vs. performance tradeoff curve. Computational experiments demonstrate the viability of the approach.