Optimal simultaneous pin assignment and escape routing for dense PCBs

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

doi:10.1109/ASPDAC.2010.5419881

Optimal simultaneous pin assignment and escape routing for dense PCBs

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

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

16 Citations (Scopus)

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 language	English
Title of host publication	Proceedings of The 15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010
Publisher	IEEE
Pages	275-280
Number of pages	6
ISBN (Print)	9781424457656
DOIs	https://doi.org/10.1109/ASPDAC.2010.5419881
Publication status	Published - 20 Jan 2010
Event	15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010 - Taipei International Convention Center, Taipei, Taiwan, Province of China Duration: 18 Jan 2010 → 21 Jan 2010 https://www.aspdac.com/aspdac2010/ (Conference website) https://www.aspdac.com/aspdac2010/pdf/ASP-DAC%202010%20Advance%20Program%20Final1215.pdf (Conference programme) https://ieeexplore.ieee.org/xpl/conhome/5415928/proceeding (Conference proceedings)

Publication series

Name	Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC
ISSN (Print)	2153-6961
ISSN (Electronic)	2153-697X

Conference

Conference	15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010
Country/Territory	Taiwan, Province of China
City	Taipei
Period	18/01/10 → 21/01/10
Internet address	https://www.aspdac.com/aspdac2010/ (Conference website) https://www.aspdac.com/aspdac2010/pdf/ASP-DAC%202010%20Advance%20Program%20Final1215.pdf (Conference programme) https://ieeexplore.ieee.org/xpl/conhome/5415928/proceeding (Conference proceedings)

Scopus Subject Areas

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

Access to Document

10.1109/ASPDAC.2010.5419881

Cite this

@inproceedings{93bf9599bd3f4c74ba7170f60dad75b2,

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.}",

note = "This work was partially supported by the National Science Foundation under grant CCF-0701821.; 15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010 ; Conference date: 18-01-2010 Through 21-01-2010",

year = "2010",

month = jan,

day = "20",

doi = "10.1109/ASPDAC.2010.5419881",

language = "English",

isbn = "9781424457656",

series = "Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC",

publisher = "IEEE",

pages = "275--280",

booktitle = "Proceedings of The 15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010",

address = "United States",

url = "https://www.aspdac.com/aspdac2010/, https://www.aspdac.com/aspdac2010/pdf/ASP-DAC%202010%20Advance%20Program%20Final1215.pdf, https://ieeexplore.ieee.org/xpl/conhome/5415928/proceeding",

}

Kong, H, Yan, T & Wong, MDF 2010, Optimal simultaneous pin assignment and escape routing for dense PCBs. in Proceedings of The 15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010. Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC, IEEE, pp. 275-280, 15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010, Taipei, Taiwan, Province of China, 18/01/10. 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.
Proceedings of The 15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010. IEEE, 2010. p. 275-280 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

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

AU - Kong, Hui

AU - Yan, Tan

AU - Wong, Martin D. F.

N1 - This work was partially supported by the National Science Foundation under grant CCF-0701821.

PY - 2010/1/20

Y1 - 2010/1/20

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

U2 - 10.1109/ASPDAC.2010.5419881

DO - 10.1109/ASPDAC.2010.5419881

M3 - Conference proceeding

AN - SCOPUS:77951234821

SN - 9781424457656

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

SP - 275

EP - 280

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

PB - IEEE

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

Y2 - 18 January 2010 through 21 January 2010

ER -

Optimal simultaneous pin assignment and escape routing for dense PCBs

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this