Optimal layer assignment for escape routing of buses

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

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

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 languageEnglish (US)
Title of host publicationProceedings of the 2009 IEEE/ACM International Conference on Computer-Aided Design - Digest of Technical Papers, ICCAD 2009
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages245-248
Number of pages4
ISBN (Print)9781605588001
DOIs
StatePublished - Jan 1 2009
Event2009 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2009 - San Jose, CA, United States
Duration: Nov 2 2009Nov 5 2009

Publication series

NameIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
ISSN (Print)1092-3152

Other

Other2009 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2009
Country/TerritoryUnited States
CitySan Jose, CA
Period11/2/0911/5/09

Keywords

  • Bus
  • Escape routing
  • Layer assignment
  • Printed circuit board (PCB)

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design

Fingerprint

Dive into the research topics of 'Optimal layer assignment for escape routing of buses'. Together they form a unique fingerprint.

Cite this