Incremental Capacitance Extraction and its Application to Iterative Timing-Driven Detailed Routing

In this paper, we consider delay optimization in multilayer detailed routing. Given a detailed routing by some detailed router, we iteratively improve the delays of critical nets or nets with timing violation in an aggressive way. A rip-up and reroute approach is employed to generate the alter-nate routes. The optimal route which satisfies the timing constraints is chosen. The net delays are calculated us-ing the Elmore delay model. The coupling capacitances are computed using a 3D extractor by applying the process parameters. In such an approach, the interconnect delay can be most accurately modeled. However, this aggressive approach is likely to be computationally unaffordable, be-cause the delay of each alternate route should be evaluated. To overcome this problem, the key is to efficiently handle the detailed 3-D extraction in each iteration step. In our approach, we represent the design changes in an incremen-tal way. Then we compute the coupling capacitance using the incremental extraction algorithm which is specifically tuned to an iterative design environment. This makes the aggressive improvement approach computationally practi-cal. Experimental results are presented to demonstrate the efficiency of the approach. 1