Layer Assignment Problem for Three-Layer Routing

K. C. Chang, H. C. Du

Research output: Contribution to journalArticlepeer-review

29 Scopus citations

Abstract

The layer assignment problem for interconnect is the problem of determining which layers should be used for wiring the signal sets so that the number of vias is minimized. It is often also referred to as via minimization problem. In this paper, the layer assignment problem for three-layer routing is considered. We concentrate on one version of the layer assignment problems called Constrained Via Minimization (CYM3) problem. We have first shown that CVM3 problem is NP-complete. Then a heuristic algorithm is proposed. The experimental results show that the proposed algorithm is efficient and generates fairly good solutions.

Original languageEnglish (US)
Pages (from-to)625-632
Number of pages8
JournalIEEE Transactions on Computers
Volume37
Issue number5
DOIs
StatePublished - May 1988

Bibliographical note

Funding Information:
The W M problem for two-layer routing has been studied extensively [I]-[13]. Chen et al. [7]-[9] and Pinter [lo] proposed Stanuscript received October 15, 1985; revised August 18, 1986 and Smernber 3. 1986. This work was supported in part by NSF Grants DCR-FA20935 and MIP-8605297, and by a grant from MEIS. M C Chang was with the Department of Computer Science, University of Sfrnncjcu. Minneapolis, MN 55455. He is now with Boeing Electronic Cornpan). Seattle, WA 98058. H. C. Du is with the Department of Computer Science, University of Sl~nnssota.M inneapolis, MN 55455. IEEE Log Number 8716233.

Keywords

  • IC layout
  • NP-complete
  • layer assignment
  • via minimization

Fingerprint Dive into the research topics of 'Layer Assignment Problem for Three-Layer Routing'. Together they form a unique fingerprint.

Cite this