Timing-driven maze routing

Abstract

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-sizing resources, layer assignment, etc. Each edge in the multigraph is annotated with resistance and capacitance values associated with the particular wiring segment. The timing-driven maze routing problem is then to find paths which exhibit low resistance-capacitance (RC) delay or achieve a tradeoff between RC delay and total capacitance. An easy-to-implement labeling algorithm is presented to solve the problem along with effective speedup enhancements to the basic algorithm which yield up to 300 times speedup. It is suggested that such an algorithm will become a fundamental tool in an arsenal of interconnect optimization techniques. The tractability of the approach is supported via computational experiments.