Journal of the Association for Computing Machinery, Vol. 42, No. 2, March 1995, pp. 500–542.

Nearly Optimal Algorithms and Bounds for Multilayer Channel Routing

BONNIE BERGER

MARTIN BRADY

DONNA BROWN

AND

TOM LEIGHTON

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(\sqrt{d}) tracks to route two-terminal net problems and 2d + O(\sqrt{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(\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.

Categories and Subject Descriptors. B.7.2[placement and routing]; F.2.2[routing and layout]

General Terms. Design, Theory

Additional Key words and Phrases. Channel routing, multilayer routing, VLSI layout

Copyright 1995 by ACM, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.