TY - JOUR
T1 - A New Approach to Three- or Four-Layer Channel Routing
AU - Cong, Jingsheng
AU - Wong, D. F.
AU - Liu, C. L.
N1 - Funding Information:
Manuscript received February 5, 1988; revised June 8, 1988. This work was partially supported by the National Science Foundation under Grant MIP 87-03273. by the Semiconductor Research Corporation under Con- tract 87-DP-109, by a grant from the General Electric Company, and by the Texas Advanced Research Program. The review of this paper was arranged by Associate Editor Alfred E. Dunlop.
This is an expanded version of the work originally presented at the ICCAD-87.
PY - 1988/10
Y1 - 1988/10
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0024089373&partnerID=8YFLogxK
U2 - 10.1109/43.7808
DO - 10.1109/43.7808
M3 - Journal article
AN - SCOPUS:0024089373
SN - 0278-0070
VL - 7
SP - 1094
EP - 1104
JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
IS - 10
ER -