ABSTRACT
Buffer insertion algorithms need to be aware of layout environment and be able to handle the trade off between timing performance and congestion avoidance. The graph-based approach can be easily extended to handle multiple buffer types and wire sizing. Because the rerouting has no knowledge if buffers are needed on a path, it may cause some unnecessary wire detours. The buffered tree with minimized maximum sink delay is obtained by applying E. W. Dijkstra’s shortest path algorithm on the abstraction graph. Practically, it is essential that buffer insertion algorithms consider layout environment such as the placement and routing congestion, which obviously leads to a more complicated problem. When we consider both placement and routing congestions at the same time applying simultaneous Steiner tree construction and buffer insertion seems to be computationally prohibitive for practical circuit designs. L. P. P. P. Van Ginneken style algorithm assumes that a set of buffer insertion candidate locations are predetermined for the given topology.
