A fast algorithm for identifying good buffer insertion candidate locations
Charles J. Alpert, Miloš Hrkić, Stephen T. Quay · 2004
Van Ginneken's algorithm [18] for performing buffer insertion is a classic in the field, since it optimally solves the problem subject to a set of fixed buffer insertion candidate locations for a given Steiner topology. The generation of these candidate locations is typically performed by dividing the routed wires into small uniformly sized pieces [1]. However, certain regions of the layout are generally more attractive to place buffers than others, e.g., sparse regions are preferred to dense ones. This work presents a fast, shortest path based algorithm to identify good candidate buffer insertion locations to be passed to van Ginneken's algorithm. Our experiments show that the buffers inserted significantly improve the overall design density with virtually no impact on either CPU time or buffered net delays.