PROVABLY OPTIMAL-ALGORITHMS FOR SIGNAL ROUTING

In this paper, we propose a provably good performance-driven global ro uting algorithm for both cell-based and building block design. The alg orithm simultaneously minimizes both routing cost and the longest inte rconnection path, so that both are bounded by small constant factors a way from optimal. Our method is based on the following two results. Fi rst, for any given value of a parameter epsilon, we can construct a ro uting tree with a cost of at most (1 + (1/epsilon)) times the minimum spanning tree weight, and with a longest interconnection path length o f at most (1 + (1/epsilon)). R. Moreover, for Steiner global routing i n arbitrary weighted graphs, we achieve a wiring cost within a factor of the optimal Steiner tree cost, again with a longest path length of at most (1 + (1/epsilon)). R. In both cases, R is the minimum possible length from the source to the furthest sink. We also show that geomet ry helps in routing: in the Manhattan plane, the total wirelength for Steiner routing improves to 3/2. (1 + (1/epsilon)) times the optimal S teiner tree cost, while in the Euclidean plane, the total cost is furt her reduced to 2/square-root 3 . (1 + (1/epsilon)) times optimal. Exte nsive simulations confirm that this approach works well, using a large set of examples which reflect both cell based and building block layo ut styles.