Improved layout-driven area-constrained timing optimization by net buffering

With the advent of deep sub-micron technologies, interconnect loads and delays have become significant, and layout-driven synthesis has become the need of the day. However, due to the tight layout constraints (e.g., area availability, congestion), only layout-friendly logic transforms such as net buffering and gate resizing can be used effectively. In this paper, we address the problem of minimizing the delay of a mapped, roughly-placed and globally-routed design by buffer insertion and/or deletion without violating the local area constraints imposed by the layout. To the best of our knowledge, only one earlier work has addressed this problem (Murgai, 2000). Although the algorithm presented by Murgai (2000) is optimum for a single net, it has worst-case exponential run-time and is not suitable for large nets. In this paper, we present techniques to make this algorithm practical by improving the run-time without sacrificing the quality. We present a condition called ONPRB, which, if satisfied by the net, improves the worst case runtime complexity to quadratic, without causing a loss in optimality. A study of industrial designs showed that up to 80% of the critical nets satisfied the ONPRB condition. To further reduce the run-time, we propose a technique to convert a net into one that satisfies this condition. Experiments on industrial designs show that the proposed scheme gives up to 12.5 times speed-up over (Murgai, 2000), without sacrificing the design quality (i.e., final delay and area).