Wire segmenting for improved buffer insertion

Abstract

Buffer insertion seeks to place buffers on the wires of a signal net to minimize delay. Van Ginneken [14] proposed an optimal dynamic programming solution (with extensions proposed by [7] [8] [9] [12]) such that at most one buffer can be placed on a single wire. This constraint can hurt solution quality, but it may be circumvented by dividing each wire into multiple smaller segments. This work studies the problem of finding the correct number of segments for each wire in the routing tree. Too few segments yields sub-par solutions, but too many segments can lead to excessive run times and memory loads. We derive new theoretical results for computing the appropriate number of buffers (and hence wire segments) which motivate our new wire segmenting algorithm. We show that using wire segmenting as a precursor to buffer insertion produces solutions within a few percent of optimal, while using only seconds of CPU time.