An optimal algorithm for layer assignment of bus escape routing on PCBs

Qiang Ma; Evangeline F. Y. Young; Martin D. F. Wong

doi:10.1145/2024724.2024764

An optimal algorithm for layer assignment of bus escape routing on PCBs

Qiang Ma, Evangeline F. Y. Young, Martin D. F. Wong

Office of the Provost

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

19 Citations (Scopus)

Abstract

Bus escape routing is a critical problem in modern PCB design. Due to the huge pin count and high density of the pin array, it usually requires multiple layers to route the buses without any conflict. How to assign the escape routing of buses to different layers becomes an important issue. In addition, some buses are required to be assigned on consecutive layers, which adds more difficulties to the layer assignment problem. In this paper, we propose a branch-and-bound based algorithm that optimally solves the layer assignment problem of bus escape routing. Our algorithm guarantees to produce a feasible layer assignment of the buses with a minimum number of layers. We applied our algorithm on industrial data and the experimental results validate our approach.

Original language	English
Title of host publication	48th ACM/IEEE Design Automation Conference - Proceedings 2011
Publisher	Association for Computing Machinery (ACM)
Pages	176-181
Number of pages	6
ISBN (Print)	9781450306362
DOIs	https://doi.org/10.1145/2024724.2024764
Publication status	Published - 7 Jun 2011
Event	48th ACM/IEEE Design Automation Conference, DAC 2011 - San Diego, United States Duration: 5 Jun 2011 → 9 Jun 2011 https://www.dac.com/About/Conference-Archive/48th-DAC-2011 (Conference website) https://www.dac.com/portals/0/documents/archive/2011/48DAC_Final_Program_front.pdf (Conference programme) https://dl.acm.org/doi/proceedings/10.1145/2024724 (Conference proceedings) https://ieeexplore.ieee.org/xpl/conhome/5968673/proceeding (Conference proceedings)

Publication series

Name	ACM/IEEE Design Automation Conference - Proceedings
ISSN (Print)	0738-100X

Conference

Conference	48th ACM/IEEE Design Automation Conference, DAC 2011
Country/Territory	United States
City	San Diego
Period	5/06/11 → 9/06/11
Internet address	https://www.dac.com/About/Conference-Archive/48th-DAC-2011 (Conference website) https://www.dac.com/portals/0/documents/archive/2011/48DAC_Final_Program_front.pdf (Conference programme) https://dl.acm.org/doi/proceedings/10.1145/2024724 (Conference proceedings) https://ieeexplore.ieee.org/xpl/conhome/5968673/proceeding (Conference proceedings)

Scopus Subject Areas

Control and Systems Engineering
Computer Science Applications
Electrical and Electronic Engineering
Modelling and Simulation

User-Defined Keywords

Escape routing
Optimal layer assignment
Branch-and-bound

Access to Document

10.1145/2024724.2024764

Cite this

@inproceedings{062e3811baeb48da9e3a64c43efbb48c,

title = "An optimal algorithm for layer assignment of bus escape routing on PCBs",

abstract = "Bus escape routing is a critical problem in modern PCB design. Due to the huge pin count and high density of the pin array, it usually requires multiple layers to route the buses without any conflict. How to assign the escape routing of buses to different layers becomes an important issue. In addition, some buses are required to be assigned on consecutive layers, which adds more difficulties to the layer assignment problem. In this paper, we propose a branch-and-bound based algorithm that optimally solves the layer assignment problem of bus escape routing. Our algorithm guarantees to produce a feasible layer assignment of the buses with a minimum number of layers. We applied our algorithm on industrial data and the experimental results validate our approach.",

keywords = "Escape routing, Optimal layer assignment, Branch-and-bound",

author = "Qiang Ma and Young, {Evangeline F. Y.} and Wong, {Martin D. F.}",

note = "Funding information: This work was partially supported by the National Science Foundation under grant CCF-1017516.; 48th ACM/IEEE Design Automation Conference, DAC 2011 ; Conference date: 05-06-2011 Through 09-06-2011",

year = "2011",

month = jun,

day = "7",

doi = "10.1145/2024724.2024764",

language = "English",

isbn = "9781450306362",

series = "ACM/IEEE Design Automation Conference - Proceedings",

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

pages = "176--181",

booktitle = "48th ACM/IEEE Design Automation Conference - Proceedings 2011",

address = "United States",

url = "https://www.dac.com/About/Conference-Archive/48th-DAC-2011, https://www.dac.com/portals/0/documents/archive/2011/48DAC_Final_Program_front.pdf, https://dl.acm.org/doi/proceedings/10.1145/2024724, https://ieeexplore.ieee.org/xpl/conhome/5968673/proceeding",

}

Ma, Q, Young, EFY & Wong, MDF 2011, An optimal algorithm for layer assignment of bus escape routing on PCBs. in 48th ACM/IEEE Design Automation Conference - Proceedings 2011. ACM/IEEE Design Automation Conference - Proceedings, Association for Computing Machinery (ACM), pp. 176-181, 48th ACM/IEEE Design Automation Conference, DAC 2011, San Diego, California, United States, 5/06/11. https://doi.org/10.1145/2024724.2024764

An optimal algorithm for layer assignment of bus escape routing on PCBs. / Ma, Qiang; Young, Evangeline F. Y.; Wong, Martin D. F.
48th ACM/IEEE Design Automation Conference - Proceedings 2011. Association for Computing Machinery (ACM), 2011. p. 176-181 (ACM/IEEE Design Automation Conference - Proceedings).

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

TY - GEN

T1 - An optimal algorithm for layer assignment of bus escape routing on PCBs

AU - Ma, Qiang

AU - Young, Evangeline F. Y.

AU - Wong, Martin D. F.

N1 - Funding information: This work was partially supported by the National Science Foundation under grant CCF-1017516.

PY - 2011/6/7

Y1 - 2011/6/7

N2 - Bus escape routing is a critical problem in modern PCB design. Due to the huge pin count and high density of the pin array, it usually requires multiple layers to route the buses without any conflict. How to assign the escape routing of buses to different layers becomes an important issue. In addition, some buses are required to be assigned on consecutive layers, which adds more difficulties to the layer assignment problem. In this paper, we propose a branch-and-bound based algorithm that optimally solves the layer assignment problem of bus escape routing. Our algorithm guarantees to produce a feasible layer assignment of the buses with a minimum number of layers. We applied our algorithm on industrial data and the experimental results validate our approach.

AB - Bus escape routing is a critical problem in modern PCB design. Due to the huge pin count and high density of the pin array, it usually requires multiple layers to route the buses without any conflict. How to assign the escape routing of buses to different layers becomes an important issue. In addition, some buses are required to be assigned on consecutive layers, which adds more difficulties to the layer assignment problem. In this paper, we propose a branch-and-bound based algorithm that optimally solves the layer assignment problem of bus escape routing. Our algorithm guarantees to produce a feasible layer assignment of the buses with a minimum number of layers. We applied our algorithm on industrial data and the experimental results validate our approach.

KW - Escape routing

KW - Optimal layer assignment

KW - Branch-and-bound

UR - https://dl.acm.org/doi/10.1145/2024724.2024764

UR - https://ieeexplore.ieee.org/document/5981933

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

U2 - 10.1145/2024724.2024764

DO - 10.1145/2024724.2024764

M3 - Conference proceeding

AN - SCOPUS:80052666454

SN - 9781450306362

T3 - ACM/IEEE Design Automation Conference - Proceedings

SP - 176

EP - 181

BT - 48th ACM/IEEE Design Automation Conference - Proceedings 2011

PB - Association for Computing Machinery (ACM)

T2 - 48th ACM/IEEE Design Automation Conference, DAC 2011

Y2 - 5 June 2011 through 9 June 2011

ER -

An optimal algorithm for layer assignment of bus escape routing on PCBs

Abstract

Publication series

Conference

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this