A New Approach to Three- or Four-Layer Channel Routing

Jingsheng Cong, D. F. Wong, C. L. Liu

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1094-1104
Number of pages11
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume7
Issue number10
DOIs
StatePublished - Oct 1988
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'A New Approach to Three- or Four-Layer Channel Routing'. Together they form a unique fingerprint.

  • Cite this