Algorithms for Routing in Chip Design
Abstract:
Routing in Chip Design is tasked with the computation of rectilinear Steiner trees that have to obey numerous constraints and design rules.
In practice different objectives should be optimized and timing constraints need to be met. Due to its high complexity, the routing process is traditionally split into at least two steps: global routing and detailed routing. This talk focuses on global routing, where wires are assigned to coarse “tiles” before precise legalization.
The global routing problem can be formulated as a min-max resource sharing problem, which is a generalization of fractional packing and the maximum concurrent flow problem. We improve upon the currently fastest known FPTAS for the min-max resource sharing problem, surpassing the previously best-known running times for both the primal and dual problem. Moreover, we discuss how timing constraints can be incorporated in the resource sharing formulation.
Further, we introduce a novel usage model for tile-internal wire capacity in global routing, capturing local congestion more accurately than existing methods. We present new algorithms tailored to this usage model and discuss experimental results on real-world microprocessors, demonstrating its superiority over a state-of-the-art traditional global router.