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
Pages245-248
Number of pages4
StatePublished - Dec 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
CountryUnited States
CitySan Jose, CA
Period11/2/0911/5/09

    Fingerprint

Keywords

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

ASJC Scopus subject areas

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

Cite this

Yan, T., Kong, H., & Wong, M. D. F. (2009). Optimal layer assignment for escape routing of buses. In Proceedings of the 2009 IEEE/ACM International Conference on Computer-Aided Design - Digest of Technical Papers, ICCAD 2009 (pp. 245-248). [5361286] (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD).