Optimal layer assignment for escape routing of buses

Tan Yan; Hui Kong; Martin D. F. Wong

doi:10.1145/1687399.1687444

Optimal layer assignment for escape routing of buses

Tan Yan, Hui Kong, Martin D. F. Wong

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

18 Citations (Scopus)

Abstract

Escape routing is a critical problem in PCB design. In ICCAD'07, a layer assignment algorithm was proposed for escape routing of buses. The algorithm is optimal for single layer design in the sense that it determines if a set of buses can all be escaped on one layer. If they cannot, the algorithm is able to select a maximum subset of the buses that can be escaped on one layer. This, in turn, leads to a heuristic for the layer assignment problem with multiple layers, which is to repeatedly assign a maximum subset of the unassigned buses to a new layer. In this work, we present an algorithm that solves the multi-layer layer assignment problem optimally. Our algorithm guarantees to produce a layer assignment with minimum number of layers. We applied our algorithm on industrial data and obtained encouraging results.

Original language	English
Title of host publication	ICCAD '09
Subtitle of host publication	Proceedings of the 2009 International Conference on Computer-Aided Design
Publisher	Association for Computing Machinery (ACM)
Pages	245-248
Number of pages	4
ISBN (Print)	9781605588001
DOIs	https://doi.org/10.1145/1687399.1687444
Publication status	Published - 2 Nov 2009
Event	2009 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2009 - DoubleTree Hotel, San Jose, United States Duration: 2 Nov 2009 → 5 Nov 2009 https://dl.acm.org/doi/proceedings/10.1145/1687399 (Conference proceedings)

Publication series

Name	IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
ISSN (Print)	1092-3152
ISSN (Electronic)	1558-2434

Conference

Conference	2009 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2009
Country/Territory	United States
City	San Jose
Period	2/11/09 → 5/11/09
Internet address	https://dl.acm.org/doi/proceedings/10.1145/1687399 (Conference proceedings)

Scopus Subject Areas

Software
Computer Science Applications
Computer Graphics and Computer-Aided Design

User-Defined Keywords

Bus
Escape routing
Layer assignment
Printed circuit board (PCB)

Access to Document

10.1145/1687399.1687444

Cite this

Yan, T., Kong, H., & Wong, M. D. F. (2009). Optimal layer assignment for escape routing of buses. In ICCAD '09: Proceedings of the 2009 International Conference on Computer-Aided Design (pp. 245-248). (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD). Association for Computing Machinery (ACM). https://doi.org/10.1145/1687399.1687444

@inproceedings{662e40dfc7dd44e3a1afb581729bb3cc,

title = "Optimal layer assignment for escape routing of buses",

abstract = "Escape routing is a critical problem in PCB design. In ICCAD'07, a layer assignment algorithm was proposed for escape routing of buses. The algorithm is optimal for single layer design in the sense that it determines if a set of buses can all be escaped on one layer. If they cannot, the algorithm is able to select a maximum subset of the buses that can be escaped on one layer. This, in turn, leads to a heuristic for the layer assignment problem with multiple layers, which is to repeatedly assign a maximum subset of the unassigned buses to a new layer. In this work, we present an algorithm that solves the multi-layer layer assignment problem optimally. Our algorithm guarantees to produce a layer assignment with minimum number of layers. We applied our algorithm on industrial data and obtained encouraging results.",

keywords = "Bus, Escape routing, Layer assignment, Printed circuit board (PCB)",

author = "Tan Yan and Hui Kong and Wong, {Martin D. F.}",

note = "This work was partially supported by the National Science Foundation under grant CCF-0701821 and a grant from the Fujitsu Laboratories.; 2009 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2009 ; Conference date: 02-11-2009 Through 05-11-2009",

year = "2009",

month = nov,

day = "2",

doi = "10.1145/1687399.1687444",

language = "English",

isbn = "9781605588001",

series = "IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD",

publisher = "Association for Computing Machinery (ACM)",

pages = "245--248",

booktitle = "ICCAD '09",

address = "United States",

url = "https://dl.acm.org/doi/proceedings/10.1145/1687399",

}

Yan, T, Kong, H & Wong, MDF 2009, Optimal layer assignment for escape routing of buses. in ICCAD '09: Proceedings of the 2009 International Conference on Computer-Aided Design. IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD, Association for Computing Machinery (ACM), pp. 245-248, 2009 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2009, San Jose, California, United States, 2/11/09. https://doi.org/10.1145/1687399.1687444

Optimal layer assignment for escape routing of buses. / Yan, Tan; Kong, Hui; Wong, Martin D. F.
ICCAD '09: Proceedings of the 2009 International Conference on Computer-Aided Design. Association for Computing Machinery (ACM), 2009. p. 245-248 (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - Optimal layer assignment for escape routing of buses

AU - Yan, Tan

AU - Kong, Hui

AU - Wong, Martin D. F.

N1 - This work was partially supported by the National Science Foundation under grant CCF-0701821 and a grant from the Fujitsu Laboratories.

PY - 2009/11/2

Y1 - 2009/11/2

N2 - Escape routing is a critical problem in PCB design. In ICCAD'07, a layer assignment algorithm was proposed for escape routing of buses. The algorithm is optimal for single layer design in the sense that it determines if a set of buses can all be escaped on one layer. If they cannot, the algorithm is able to select a maximum subset of the buses that can be escaped on one layer. This, in turn, leads to a heuristic for the layer assignment problem with multiple layers, which is to repeatedly assign a maximum subset of the unassigned buses to a new layer. In this work, we present an algorithm that solves the multi-layer layer assignment problem optimally. Our algorithm guarantees to produce a layer assignment with minimum number of layers. We applied our algorithm on industrial data and obtained encouraging results.

AB - Escape routing is a critical problem in PCB design. In ICCAD'07, a layer assignment algorithm was proposed for escape routing of buses. The algorithm is optimal for single layer design in the sense that it determines if a set of buses can all be escaped on one layer. If they cannot, the algorithm is able to select a maximum subset of the buses that can be escaped on one layer. This, in turn, leads to a heuristic for the layer assignment problem with multiple layers, which is to repeatedly assign a maximum subset of the unassigned buses to a new layer. In this work, we present an algorithm that solves the multi-layer layer assignment problem optimally. Our algorithm guarantees to produce a layer assignment with minimum number of layers. We applied our algorithm on industrial data and obtained encouraging results.

KW - Bus

KW - Escape routing

KW - Layer assignment

KW - Printed circuit board (PCB)

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

U2 - 10.1145/1687399.1687444

DO - 10.1145/1687399.1687444

M3 - Conference proceeding

AN - SCOPUS:76349111070

SN - 9781605588001

T3 - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD

SP - 245

EP - 248

BT - ICCAD '09

PB - Association for Computing Machinery (ACM)

T2 - 2009 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2009

Y2 - 2 November 2009 through 5 November 2009

ER -

Optimal layer assignment for escape routing of buses

Abstract

Publication series

Conference

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this