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

Polychlorinated biphenyls
Program processors
Polynomials

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

Optimal simultaneous pin assignment and escape routing for dense PCBs. / Kong, Hui; Yan, Tan; Wong, Martin D F.

2010 15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010. 2010. p. 275-280 5419881 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC).

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

Kong, H, Yan, T & Wong, MDF 2010, Optimal simultaneous pin assignment and escape routing for dense PCBs. in 2010 15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010., 5419881, Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC, pp. 275-280, 2010 15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010, Taipei, Taiwan, Province of China, 1/18/10. https://doi.org/10.1109/ASPDAC.2010.5419881
Kong H, Yan T, Wong MDF. Optimal simultaneous pin assignment and escape routing for dense PCBs. In 2010 15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010. 2010. p. 275-280. 5419881. (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC). https://doi.org/10.1109/ASPDAC.2010.5419881
Kong, Hui ; Yan, Tan ; Wong, Martin D F. / Optimal simultaneous pin assignment and escape routing for dense PCBs. 2010 15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010. 2010. pp. 275-280 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC).
@inproceedings{666eabea00fe470ea66e96f912f0b319,
title = "Optimal simultaneous pin assignment and escape routing for dense PCBs",
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.",
author = "Hui Kong and Tan Yan and Wong, {Martin D F}",
year = "2010",
month = "4",
day = "28",
doi = "10.1109/ASPDAC.2010.5419881",
language = "English (US)",
isbn = "9781424457656",
series = "Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC",
pages = "275--280",
booktitle = "2010 15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010",

}

TY - GEN

T1 - Optimal simultaneous pin assignment and escape routing for dense PCBs

AU - Kong, Hui

AU - Yan, Tan

AU - Wong, Martin D F

PY - 2010/4/28

Y1 - 2010/4/28

N2 - 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.

AB - 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.

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

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

U2 - 10.1109/ASPDAC.2010.5419881

DO - 10.1109/ASPDAC.2010.5419881

M3 - Conference contribution

AN - SCOPUS:77951234821

SN - 9781424457656

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

SP - 275

EP - 280

BT - 2010 15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010

ER -