We present in this paper a new approach to the three- or four-layer channel routing problem. Since two-layer channel routing has been well studied, there are several two-layer routers which can produce optimal or near optimal solutions for almost all the practical problems. We develop a general technique which transforms a two-layer routing solution systematically into a three-layer routing solution. This solution transformation approach is different from previous approaches for three-layer and multilayer channel routing. Our router performs well in comparison with other three-layer channel routers proposed thus far. In particular, it provides a ten-track optimal solution for the famous Deutsch's difficult example, whereas other well known three-layer channel routers required 11 or more tracks. We extend our approach to four-layer channel routing. Given any two-layer channel routing solution without an unrestricted dogleg that uses w tracks, our router can provably obtain a four-layer routing solution using no more than ⌈w/2⌉ tracks. We also give a new theoretical upper bound ⌈d/2⌉+2 for arbitrary four-layer channel routing problems.
|Number of pages
|IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
|Published - Oct 1988
Scopus Subject Areas
- Computer Graphics and Computer-Aided Design
- Electrical and Electronic Engineering