|
|
|
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.
|
|
http://portal.acm.org/citation.cfm?id=201037
|
|
|
|