Bonnie Berger


Nearly Optimal Algorithms and Bounds for Multilayer Channel Routing

Bonnie Berger, Martin Brady, Donna Brown, and Tom Leighton


This paper presents algorithms for routing channels with L 2 layers. For the unit vertical overlap model, we describe a two-layer channel routing algorithm that uses at most d + O(d½) tracks to route two-terminal net problems and 2d + O(d½) tracks to route multiterminal nets. We also show that d + (log d) tracks are required to route two-terminal net problems in the worst case even if arbitrary vertical overlap is allowed. We generalize the algorithm to unrestricted multilayer routing and use only d/(L-1) + O((d/L)½ + 1) tracks for two-terminal net problems (within O((d/L)½ + 1) tracks of optimal) and d/(L-2) + O((d/L)½ + 1) tracks for multiterminal net problems (within a factor of (L-1)/(L-2) times optimal). We demonstrate the generality of our routing strategy by showing that it can be used to duplicate some of the best previous upper bounds for other models (two-layer Manhattan routing and two and three-layer knock-knee routing of two-terminal, two-sided nets), and gives a new upper bound for rotuing with 45-degree diagonal wires.