An Efficient Algorithm for RLC Buffer Insertion

Traditional buffer insertion algorithms neglect the impact of inductance effect, which often introduces large error in circuit optimization. On the other hand, ultra-fast buffering techniques are always desirable as buffering is such a widely used technique in industry. It is a challenge to design an RLC buffering algorithm which excels in both runtime and solution quality. In this paper, such an algorithm is proposed. The new algorithm works under the dynamic programming framework and runs in provably linear time for multiple buffer types due to two novel techniques: restrictive cost bucketing and efficient delay update. Experiment results on industrial netlists demonstrate that the new algorithm consistently outperforms van Ginneken/Lillis algorithm (van Ginneken, 1990) and (Lillis, 1996) for RC buffering and all known RLC buffering algorithms. Without buffer cost minimization, the new algorithm saves up to 8.5% buffer area and provides up to 4times speedup over Ismail's algorithm (Ismail, 2001), When buffer cost minimization is handled, the new algorithm uses 33.4% fewer buffers than van Ginnenken-Lillis's algorithm, and saves up to 5.3% buffer area and gives up to 5times speedup compared to the algorithm in (Jiang et al., 2006)