Optimal simultaneous pin assignment and escape routing for dense PCBs

Hui Kong, Tan Yan, Martin D F Wong

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

Abstract

In PCB designs, pin positions greatly affect routability of the design. State-of-the-art pin assignment algorithms are guided by simple (heuristic) metrics to estimate routability and thus have no guarantee to obtain a routable solution. In this paper, we present a novel approach to obtain a pin assignment solution that guarantees routability. We show that the problem of simultaneous pin assignment and escape routing can be solved optimally in polynomial time. We then focus on the pin assignment and escape routing for the terminals in a bus, and present algorithmic enhancements as well as discuss the trade-offs between single-layer and multi-layer implementations. We tested our approach on a state-of-the-art industrial board with 80 buses (over 7000 nets). The pin assignment and escape routing solutions for all the 80 buses are successfully obtainted in less than 5 minutes of CPU time.

Original languageEnglish (US)
Title of host publication2010 15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010
Pages275-280
Number of pages6
DOIs
StatePublished - Apr 28 2010
Event2010 15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010 - Taipei, Taiwan, Province of China
Duration: Jan 18 2010Jan 21 2010

Publication series

NameProceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

Other

Other2010 15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010
CountryTaiwan, Province of China
CityTaipei
Period1/18/101/21/10

    Fingerprint

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Cite this

Kong, H., Yan, T., & Wong, M. D. F. (2010). Optimal simultaneous pin assignment and escape routing for dense PCBs. In 2010 15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010 (pp. 275-280). [5419881] (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC). https://doi.org/10.1109/ASPDAC.2010.5419881