In this paper we present two n-layer channel routing algorithms that guarantee successful routing of the channel for n greater than three. The first is linear and optimal given a VHV...HV assignment of layers. The second, using an HVH...VH layer assignment, is quasilinear and performs optimally on examples from the literature. Except in pathological cases, we expect the latter router to perform within one row of optimal. For comparison with published examples we implemented the second router in five and three layers. The five-layer implementation routed all examples optimally while the three-layer implementation routed the examples with the same or fewer rows than the published examples. With its n-layer capability this channel router will allow channel routing to be used when more than three layers are available. This router can also be used to evaluate the utility of additional layers.
|Original language||English (US)|
|Title of host publication||Proceedings of the 23rd ACM/IEEE Design Automation Conference, DAC 1986|
|Publisher||Institute of Electrical and Electronics Engineers Inc.|
|Number of pages||7|
|State||Published - Jul 2 1986|
|Event||23rd ACM/IEEE Design Automation Conference, DAC 1986 - Las Vegas, United States|
Duration: Jun 29 1986 → Jul 2 1986
|Name||Proceedings - Design Automation Conference|
|Other||23rd ACM/IEEE Design Automation Conference, DAC 1986|
|Period||6/29/86 → 7/2/86|
Bibliographical noteFunding Information:
in part by ‘NSF grant DCR-
© 1986 IEEE.