Bonnie Berger
Abstract
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.
- ~BAKER, B., BHATI', S. N., AND LEIGHTON, T. 1984. An approximation algorithm for Manhattan ~routing. In Advances m Computing Research, vol. 2 (VLSI Theory), F. P. Preparata, Ed. JAI ~Press, Inc., Greenwich, Conn. pp. 205-229. Google Scholar
- ~BERGER, B. 1986. New upper bounds for two-layer channel routing. M.S. dissertation, Mas- ~sachusetts Institute of Technology, Cambridge, Mass. (Jan.)Google Scholar
- ~BOLOGNESI, t., AND BROWN, D. J. 1982. A channel routing algorithm with bounded wire ~length, unpublished manuscript, Coordinated Science Lab., Univ. Illinois at Urbana-Champaign, ~Urbana, Ill.Google Scholar
- ~BRADY, M. 1987. New algorithms and bounds for multilayer channel routing. Ph.D. disserta- ~ion, Univ. Illinois at Urbana-Champaign, Urbana, Ill. (May). Google Scholar
- ~BRADY, M., AND BROWN, D.J. 1991. Optimal multilayer channel routing with overlap. Algo- ~rithmica 6, 1, 83-101.Google Scholar
- ~BROWN, D. J. AND RIVEST, R.L. 1981. New lower bounds for channel width. In Proceedings of ~1981 CMU Conference on VLSI Systems and Computations. Carnegie-Mellon Univ., Pittsburgh, ~Pa, (Oct.), pp. 178-185.Google Scholar
- ~DEUTSCH, D. N. 1976. A "DOGLEG" channel router. In Proceedings of the 13th Design ~Automation Conference (San Francisco, Calif., June 28-30). ACM, New York, pp. 425-433. Google Scholar
- ~DWYER, D., BROWN, D. J., AND BRADY, M. 1995. Density plus flux lower bounds for manhattan ~channel routing. Tech. rep., Coordinated Science Lab., University of Illinois at Urbana- ~Champaign, Urbana, Ill.Google Scholar
- ~GAO, S., AND HAMBRUSCH, S. 1986. Two-layer channel routing with vertical unit-length over- ~lap. Algorithmica 1, 2, 223-232.Google Scholar
- ~GAO, S., AND KAUFMANN, M. 1994. Channel routing of multiterminal nets. JACM 41, 4 (July), ~791-818. Google Scholar
- ~HAMBRUSCH, S. 1983. Using overlap and minimizing contact points in channel routing. In ~Proceedings of the 21st Annual Allerton Conference on Communication, Control, and Computing. ~University of Illinois at Urbana-Champaign, Urbana, Ill. (Oct.) pp. 256-257.Google Scholar
- ~HAMBRUSCH, S. 1985. Channel routing algorithms for overlap models. IEEE Trans. Computer- ~Aided Des. Integ. Circuits Syst. CAD-4, 1, (Jan.), 23-30.Google Scholar
- ~HASHIMOTO, A., AND STEVENS, J. 1971. Wire routing by optimizing channel assignment within ~large apertures. In Proceedings of the 8th Design Automation Workshop (Atlantic City, N.J., June ~28-30). ACM, New York, pp. 155-169. Google Scholar
- ~LAPAUCH, A., AND PINTER, R. 1990. Channel routing for integrated circuits. Annual Rev. ~Comput. Sci. 4, 307-363.Google Scholar
- ~LEIGHTON, F.T. 1994. A 2d- 1 lower bound for two-layer knock-knee channel routing. SIAM ~J. Discrete Math. 7, 2 (May), 230-237. Google Scholar
- ~LODI, E., LuccIo, F., AND PAGLI, L. 1989. A preliminary study of a diagonal channel routing ~model. AIgorithmica 4, 4, 585-597.Google Scholar
- ~LEHLHORN, K., PREPARATA, F. P., AND SARRAFZADEH, M. 1986. Channel routing in knock-knee ~mode. Algorithmica 1, 2, 213-221.Google Scholar
- ~PREPARATA, F. P., AND LIPSKI, JR., W. 1984. Optimal three-layer channel routing. IEEE Trans. ~Computers C-33, 427-437. Google Scholar
- ~RIVEST, R. L. 1982. The "PI" (placement and interconnect) system. In Proceedings of the ~ACM/IEEE 19th Design Automatton Conference (Las Vegas, Nev., June 14-16). ACM, New ~York, pp. 475-481. Google Scholar
- ~RIVEST, R. L., BARATZ, A., AND MILLER, G. 1981. Provably good channel routing algorithms. ~In Proceedings of the 1981 CMU Conference on ITLSI System and Computattons (Oct.), 153 159.Google Scholar
- ~RiVEST, R. m., AND FIDUCCIA. C.M. 1982. A "Greedy" Channel Router. In Proceedings of the ~ACM/IEEE 19th Destgn Automation Conference (Las Vegas, Nev., June 14 16) ACM, New ~York, pp. 418-424. Google Scholar
- ~SARRAFZADEH, M. 1987a. Hierarchical approaches to VLSI clrcmt layout. Ph.D. dissertation, ~Univ. Ill. Urbana-Champaign, Urbana, Ill.Google Scholar
- ~SARRAFZADEH, M. 1987b. Channel routing problem in the knock-knee mode is NP-complete. ~IEEE Trans. Computer-Atded Deszgn of Integrated Circ. and Syst. CAD-6, 4. 503 506 (July 1987).Google Scholar
- ~SARRAFZADEH, M., AND PREPARATA, F. P. 1985. Compact channel routing of multiterminal ~nets. Ann. Disc. Math. 25, 255-280.Google Scholar
- ~SZYMANSKI, T.G. 1985. Dogleg channel routing is NP-complete. IEEE Trans. on Computer- ~Aided Design o)' Integrated Circ. Syst. CAD-4, I (Jan.), 31-41.Google Scholar
- ~YOSHIMURA, T., AND KUH, E.S. 1982. Efficient algorithms for channel routing," iEEE Trans. ~on Computer-Aided Design of Integrated Circ'. Svst. CAD-l, 1 (Jan.), 25-35.Google Scholar
Index Terms
- Nearly optimal algorithms and bounds for multilayer channel routing
Recommendations
Channel routing of multiterminal nets
This paper presents new upper bounds for channel routing of multiterminal nets, which answers the long-standing open question whether or not multiterminal problems really require channels two times wider than 2-terminal problems. We transform any ...
Optimal multilayer channel routing with overlap
AbstractThis paper presents algorithms for multiterminal net channel routing where multiple interconnect layers are available. Major improvements are possible if wires are able to overlap, and our generalized main algorithm allows overlap, but only on ...
Optimal Three-Layer Channel Routing
In this paper we show that any channel routing problem of density d involving only two-terminal nets can always be solved in the knock-knee mode in a channel of width equal to the density d with three conducting layers. An algorithm is described which ...
Reviews
Douglas M. Campbell
This densely written paper reports on work completed in 1988, but which has only now been published. As the authors note, many of the paper's contribution s have been superseded by Gao and Kaufmann in a paper [1] that appeared in 1994, a year before this paper appeared. The authors first develop a two-layer algorithm, which improves known results from the early 1980s: their model is weaker; their results show that some routing problems become easier when unit vertical overlap is allowed; and their algorithm presents a unified framework within which previous results for Manhattan and knock-knee routing, and new results for 45-degree diagonal routing, can be derived. Their algorithm tolerates variations in the routing model. In the second part of the paper, the authors extend their results to multilayer channel routing. The lack of a concrete example makes the details difficult to follow.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments