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

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish (US)
Title of host publication2011 48th ACM/EDAC/IEEE Design Automation Conference, DAC 2011
Pages176-181
Number of pages6
StatePublished - Sep 16 2011
Event2011 48th ACM/EDAC/IEEE Design Automation Conference, DAC 2011 - San Diego, CA, United States
Duration: Jun 5 2011Jun 9 2011

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0738-100X

Other

Other2011 48th ACM/EDAC/IEEE Design Automation Conference, DAC 2011
CountryUnited States
CitySan Diego, CA
Period6/5/116/9/11

Fingerprint

Polychlorinated biphenyls
Optimal Algorithm
Routing
Assignment
Assignment Problem
Branch-and-bound
Assign
Consecutive
Count
Experimental Results

Keywords

  • Branch-and-bound
  • Escape routing
  • Optimal layer assignment

ASJC Scopus subject areas

  • Computer Science Applications
  • Control and Systems Engineering
  • Electrical and Electronic Engineering
  • Modeling and Simulation

Cite this

Ma, Q., Young, E. F. Y., & Wong, M. D. F. (2011). An optimal algorithm for layer assignment of bus escape routing on PCBs. In 2011 48th ACM/EDAC/IEEE Design Automation Conference, DAC 2011 (pp. 176-181). [5981933] (Proceedings - Design Automation Conference).

An optimal algorithm for layer assignment of bus escape routing on PCBs. / Ma, Qiang; Young, Evangeline F.Y.; Wong, Martin D.F.

2011 48th ACM/EDAC/IEEE Design Automation Conference, DAC 2011. 2011. p. 176-181 5981933 (Proceedings - Design Automation Conference).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Ma, Q, Young, EFY & Wong, MDF 2011, An optimal algorithm for layer assignment of bus escape routing on PCBs. in 2011 48th ACM/EDAC/IEEE Design Automation Conference, DAC 2011., 5981933, Proceedings - Design Automation Conference, pp. 176-181, 2011 48th ACM/EDAC/IEEE Design Automation Conference, DAC 2011, San Diego, CA, United States, 6/5/11.
Ma Q, Young EFY, Wong MDF. An optimal algorithm for layer assignment of bus escape routing on PCBs. In 2011 48th ACM/EDAC/IEEE Design Automation Conference, DAC 2011. 2011. p. 176-181. 5981933. (Proceedings - Design Automation Conference).
Ma, Qiang ; Young, Evangeline F.Y. ; Wong, Martin D.F. / An optimal algorithm for layer assignment of bus escape routing on PCBs. 2011 48th ACM/EDAC/IEEE Design Automation Conference, DAC 2011. 2011. pp. 176-181 (Proceedings - Design Automation Conference).
@inproceedings{a5aed75e2b614f9b900383aa814e7a1e,
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 = "Branch-and-bound, Escape routing, Optimal layer assignment",
author = "Qiang Ma and Young, {Evangeline F.Y.} and Wong, {Martin D.F.}",
year = "2011",
month = "9",
day = "16",
language = "English (US)",
isbn = "9781450306362",
series = "Proceedings - Design Automation Conference",
pages = "176--181",
booktitle = "2011 48th ACM/EDAC/IEEE Design Automation Conference, DAC 2011",

}

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.

PY - 2011/9/16

Y1 - 2011/9/16

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 - Branch-and-bound

KW - Escape routing

KW - Optimal layer assignment

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

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

M3 - Conference contribution

AN - SCOPUS:80052666454

SN - 9781450306362

T3 - Proceedings - Design Automation Conference

SP - 176

EP - 181

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

ER -