Global Routing with Inherent Static Timing Constraints

We show how to incorporate global static timing constraints into global routing. Our approach is based on the min-max resource sharing model that proved successful for global routing in theory and practice. Static timing constraints are modeled by a linear number of additional resources and customers. The algorithm dynamically adjusts delay budgets and can, thus, trade off wiring congestion for delay. The approach works for many delay models. As a subroutine, the algorithm routes a single net. If this subroutine is near-optimal, we will find near-optimal solutions for the overall problem very efficiently. We demonstrate the benefit of our timing-driven global routing algorithm by experimental results on industrial chips.