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 proceedingpeer-review

18 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 languageEnglish
Title of host publication48th ACM/IEEE Design Automation Conference - Proceedings 2011
PublisherAssociation for Computing Machinery (ACM)
Pages176-181
Number of pages6
ISBN (Print)9781450306362
DOIs
Publication statusPublished - 7 Jun 2011
Event48th ACM/IEEE Design Automation Conference, DAC 2011 - San Diego, United States
Duration: 5 Jun 20119 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

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

Conference

Conference48th ACM/IEEE Design Automation Conference, DAC 2011
Country/TerritoryUnited States
CitySan Diego
Period5/06/119/06/11
Internet address

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

Fingerprint

Dive into the research topics of 'An optimal algorithm for layer assignment of bus escape routing on PCBs'. Together they form a unique fingerprint.

Cite this