Layer assignment for multi-layer PCB and VLSI routing

Kuo-En Chang, Sung Chuan Fang

Research output: Contribution to journalArticle

Abstract

The layer assignment problem for VLSI routing is the problem of determining which layers can be used for routing the wire segments in the interconnections of nets so that the number of vias is minimized. In this paper, we first transform the problem of layer assignment for multi-layer routing to the graph contractability problem and then a heuristic algorithm is proposed on the basis of the graph contractability model. The algorithm was evaluated using Deustch’s five-layer difficult example. The result showed that the number of vias is reduced 38.5 percent.

Original languageEnglish
Pages (from-to)373-382
Number of pages10
JournalJournal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an
Volume14
Issue number4
DOIs
Publication statusPublished - 1991 Jan 1

Fingerprint

Heuristic algorithms
Polychlorinated biphenyls
Wire

Keywords

  • Graph contractability
  • Layer assignment
  • NP-compIete
  • Via minimization

ASJC Scopus subject areas

  • Engineering(all)

Cite this

@article{43bd983352384217989942f359e8bd2c,
title = "Layer assignment for multi-layer PCB and VLSI routing",
abstract = "The layer assignment problem for VLSI routing is the problem of determining which layers can be used for routing the wire segments in the interconnections of nets so that the number of vias is minimized. In this paper, we first transform the problem of layer assignment for multi-layer routing to the graph contractability problem and then a heuristic algorithm is proposed on the basis of the graph contractability model. The algorithm was evaluated using Deustch’s five-layer difficult example. The result showed that the number of vias is reduced 38.5 percent.",
keywords = "Graph contractability, Layer assignment, NP-compIete, Via minimization",
author = "Kuo-En Chang and Fang, {Sung Chuan}",
year = "1991",
month = "1",
day = "1",
doi = "10.1080/02533839.1991.9677348",
language = "English",
volume = "14",
pages = "373--382",
journal = "Chung-kuo Kung Ch'eng Hsueh K'an/Journal of the Chinese Institute of Engineers",
issn = "0253-3839",
publisher = "Chinese Institute of Engineers",
number = "4",

}

TY - JOUR

T1 - Layer assignment for multi-layer PCB and VLSI routing

AU - Chang, Kuo-En

AU - Fang, Sung Chuan

PY - 1991/1/1

Y1 - 1991/1/1

N2 - The layer assignment problem for VLSI routing is the problem of determining which layers can be used for routing the wire segments in the interconnections of nets so that the number of vias is minimized. In this paper, we first transform the problem of layer assignment for multi-layer routing to the graph contractability problem and then a heuristic algorithm is proposed on the basis of the graph contractability model. The algorithm was evaluated using Deustch’s five-layer difficult example. The result showed that the number of vias is reduced 38.5 percent.

AB - The layer assignment problem for VLSI routing is the problem of determining which layers can be used for routing the wire segments in the interconnections of nets so that the number of vias is minimized. In this paper, we first transform the problem of layer assignment for multi-layer routing to the graph contractability problem and then a heuristic algorithm is proposed on the basis of the graph contractability model. The algorithm was evaluated using Deustch’s five-layer difficult example. The result showed that the number of vias is reduced 38.5 percent.

KW - Graph contractability

KW - Layer assignment

KW - NP-compIete

KW - Via minimization

UR - http://www.scopus.com/inward/record.url?scp=0026190657&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026190657&partnerID=8YFLogxK

U2 - 10.1080/02533839.1991.9677348

DO - 10.1080/02533839.1991.9677348

M3 - Article

VL - 14

SP - 373

EP - 382

JO - Chung-kuo Kung Ch'eng Hsueh K'an/Journal of the Chinese Institute of Engineers

JF - Chung-kuo Kung Ch'eng Hsueh K'an/Journal of the Chinese Institute of Engineers

SN - 0253-3839

IS - 4

ER -