Timing-driven maze routing

This paper studies a natural formulation of the timing-driven maze routing problem, A multigraph model appropriate for global routing applications is adopted; the model naturally captures blockages, limited routing and wire-s izing resources, layer assignment, etc, Each edge in the multigraph is anno tated with resistance and capacitance values associated with the particular wiring segment. The timing-driven maze routing problem is then to find pat hs which exhibit low resistance-capacitance (RC) delay or achieve a tradeof f between RC delay and total capacitance. An easy-to-implement labeling alg orithm is presented to solve the problem along with effective speedup enhan cements to the basic algorithm which yield up to 300 times speedup, it is s uggested that such an algorithm will become a fundamental tool in an arsena l of interconnect optimization techniques. The tractability of the approach is supported via computational experiments.