NEARLY OPTIMAL-ALGORITHMS AND BOUNDS FOR MULTILAYER CHANNEL ROUTING

This paper presents algorithms for routing channels with L greater-tha n-or-equal-to 2 layers. For the unit vertical overlap model, we descri be a two-layer channel routing algorithm that uses at most d + O(squar e-root d) tracks to route two-terminal net problems and 2d + O(square- root d) tracks to route multiterminal nets. We also show that d + OMEG A(log d) tracks are required to route two-terminal net problems in the worst case even if arbitrary vertical overlap is allowed. We generali ze the algorithm to unrestricted multilayer routing and use only d/(L - 1) + O(square-root d/L + 1) tracks for two-terminal net problems (wi thin O(square-root d/L + 1) tracks of optimal) and d/(L - 2) + O(squar e-root d/L + 1) tracks for multiterminal net problems (within a factor of (L - 1)/(L - 2) times optimal). We demonstrate the generality of o ur routing strategy by showing that it can be used to duplicate some o f the best previous upper bounds for other models (two-layer Manhattan routing and two-and three-layer knock-knee routing of two-terminal, t wo-sided nets), and gives a new upper bound for routing with 45-degree diagonal wires.