AbstractThis 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(\sqrt{d}) tracks to route two-terminal net problems and 2d + O(\sqrt{d}) tracks to route multiterminal nets. We also show that d + \Omega(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(\sqrt{d/L}+1) tracks for two-terminal net problems (within O(\sqrt{d/L}+1) tracks of optimal) and d/(L-2) + O(\sqrt{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-tree routing of two-terminal, two-sided nets), and gives a new upper bound for routing with 45-degree diagonal wires. Copyright 1995 by ACM, Inc.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Categories and Subject Descriptors: B.7.2 [Integrated Circuits]: Design Aids -- placement and routing; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- routing and layout
General Terms: Design, Theory
Additional Key Words and Phrases: Channel routing, multilayer routing, VLSI layout
Selected papers that cite this one
- M. L. Brady, D. J. Brown, and K. D. Powers. Hexagonal models for channel routing. Algorithmica, 19(3):263-290, November 1997.
- Shaodi Gao and Michael Kaufmann. Channel routing of multiterminal nets. Journal of the ACM, 41(4):791-818, July 1994.
Selected references
- Shaodi Gao and Michael Kaufmann. Channel routing of multiterminal nets. In 28th Annual Symposium on Foundations of Computer Science, pages 316-325, Los Angeles, California, 12-14 October 1987. IEEE.
- Shaodi Gao and Michael Kaufmann. Channel routing of multiterminal nets. Journal of the ACM, 41(4):791-818, July 1994.