Provably good algorithms for performance-driven global routing

Abstract

We propose a provably good performance-driven global routing algorithm for both cell-based and building block design. The approach is. based on a new bounded-radius minimum routing tree formulation, which simultaneously minimizes both routing cost and the longest interconnection path, so that both are bounded by small constant factors away from optimal. For any given value of a parameter e, we construct a routing tree with longest interconnection path length at most (1 + ∈)-R, and with cost at most (1 + 2/∈) times the minimum spanning tree weight, where R is the minimum possible length from the source to the farthest sink. Our method generalizes to Steiner global routing in arbitrary weighted graphs, and to the case where varying wirelength bounds are prescribed for different source-sink paths. Extensive simulations confirm the utility of the approach.1.