A negotiated congestion based router for simultaneous escape routing

Qiang Ma; Tan Yan; Martin D. F. Wong

doi:10.1109/ISQED.2010.5450514

A negotiated congestion based router for simultaneous escape routing

Qiang Ma, Tan Yan, Martin D. F. Wong

Office of the Provost

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

26 Citations (Scopus)

Abstract

The negotiated congestion based routing scheme finds success in FPGA routing and IC global routing. However, its application in simultaneous escape routing, a key problem in PCB design, has never been reported in previous literature. In this paper, we investigate how well the negotiated congestion based router performs on escape routing problems. We propose an underlying routing graph which correctly models the routing resources of the pin grids on board. We then build a Negotiated Congestion based Escape Router (NCER) by applying the negotiated congestion routing scheme on the constructed routing graph. We compare the performance of NCER with that of Cadence PCB router Allegro on 14 industrial test cases, and experimental results show that the two routers have comparable routability: each of them completely routes 7 test cases. Moreover, we observe that NCER and Allegro exhibit complementary behaviors: each is able to solve most of the test cases that the other cannot solve. Together, they completely route 11 test cases. Therefore, by using NCER as a supplement to Allegro, we can solve a broader range of escape routing problems.

Original language	English
Title of host publication	Proceedings of the 11th International Symposium on Quality Electronic Design, ISQED 2010
Publisher	IEEE
Pages	606-610
Number of pages	5
ISBN (Electronic)	9781424464562
ISBN (Print)	9781424464548
DOIs	https://doi.org/10.1109/ISQED.2010.5450514
Publication status	Published - 24 Mar 2010
Event	11th International Symposium on Quality Electronic Design, ISQED 2010 - San Jose, United States Duration: 22 Mar 2010 → 24 Mar 2010 https://www.isqed.org/English/Archives/2010/index.html (Conference website) https://www.isqed.org/English/Archives/2010/Technical_Sessions/Technical_Sessions.html (Conference programme) https://ieeexplore.ieee.org/xpl/conhome/5443864/proceeding (Conference proceedings)

Publication series

Name	Proceedings of The International Symposium on Quality Electronic Design, ISQED
ISSN (Print)	1948-3287
ISSN (Electronic)	1948-3295

Conference

Conference	11th International Symposium on Quality Electronic Design, ISQED 2010
Country/Territory	United States
City	San Jose
Period	22/03/10 → 24/03/10
Internet address	https://www.isqed.org/English/Archives/2010/index.html (Conference website) https://www.isqed.org/English/Archives/2010/Technical_Sessions/Technical_Sessions.html (Conference programme) https://ieeexplore.ieee.org/xpl/conhome/5443864/proceeding (Conference proceedings)

Scopus Subject Areas

Electrical and Electronic Engineering

Access to Document

10.1109/ISQED.2010.5450514

Cite this

@inproceedings{f0437759d78844d5afb4bcf85ac98b6f,

title = "A negotiated congestion based router for simultaneous escape routing",

abstract = "The negotiated congestion based routing scheme finds success in FPGA routing and IC global routing. However, its application in simultaneous escape routing, a key problem in PCB design, has never been reported in previous literature. In this paper, we investigate how well the negotiated congestion based router performs on escape routing problems. We propose an underlying routing graph which correctly models the routing resources of the pin grids on board. We then build a Negotiated Congestion based Escape Router (NCER) by applying the negotiated congestion routing scheme on the constructed routing graph. We compare the performance of NCER with that of Cadence PCB router Allegro on 14 industrial test cases, and experimental results show that the two routers have comparable routability: each of them completely routes 7 test cases. Moreover, we observe that NCER and Allegro exhibit complementary behaviors: each is able to solve most of the test cases that the other cannot solve. Together, they completely route 11 test cases. Therefore, by using NCER as a supplement to Allegro, we can solve a broader range of escape routing problems.",

author = "Qiang Ma and Tan Yan and Wong, {Martin D. F.}",

note = "This work was partially supported by the National Science Foundation under grant CCF-0701821 and a grant from the Fujitsu Laboratories.; 11th International Symposium on Quality Electronic Design, ISQED 2010 ; Conference date: 22-03-2010 Through 24-03-2010",

year = "2010",

month = mar,

day = "24",

doi = "10.1109/ISQED.2010.5450514",

language = "English",

isbn = "9781424464548",

series = "Proceedings of The International Symposium on Quality Electronic Design, ISQED",

publisher = "IEEE",

pages = "606--610",

booktitle = "Proceedings of the 11th International Symposium on Quality Electronic Design, ISQED 2010",

address = "United States",

url = "https://www.isqed.org/English/Archives/2010/index.html, https://www.isqed.org/English/Archives/2010/Technical_Sessions/Technical_Sessions.html, https://ieeexplore.ieee.org/xpl/conhome/5443864/proceeding",

}

Ma, Q, Yan, T & Wong, MDF 2010, A negotiated congestion based router for simultaneous escape routing. in Proceedings of the 11th International Symposium on Quality Electronic Design, ISQED 2010. Proceedings of The International Symposium on Quality Electronic Design, ISQED, IEEE, pp. 606-610, 11th International Symposium on Quality Electronic Design, ISQED 2010, San Jose, California, United States, 22/03/10. https://doi.org/10.1109/ISQED.2010.5450514

A negotiated congestion based router for simultaneous escape routing. / Ma, Qiang; Yan, Tan; Wong, Martin D. F.
Proceedings of the 11th International Symposium on Quality Electronic Design, ISQED 2010. IEEE, 2010. p. 606-610 (Proceedings of The International Symposium on Quality Electronic Design, ISQED).

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

TY - GEN

T1 - A negotiated congestion based router for simultaneous escape routing

AU - Ma, Qiang

AU - Yan, Tan

AU - Wong, Martin D. F.

N1 - This work was partially supported by the National Science Foundation under grant CCF-0701821 and a grant from the Fujitsu Laboratories.

PY - 2010/3/24

Y1 - 2010/3/24

N2 - The negotiated congestion based routing scheme finds success in FPGA routing and IC global routing. However, its application in simultaneous escape routing, a key problem in PCB design, has never been reported in previous literature. In this paper, we investigate how well the negotiated congestion based router performs on escape routing problems. We propose an underlying routing graph which correctly models the routing resources of the pin grids on board. We then build a Negotiated Congestion based Escape Router (NCER) by applying the negotiated congestion routing scheme on the constructed routing graph. We compare the performance of NCER with that of Cadence PCB router Allegro on 14 industrial test cases, and experimental results show that the two routers have comparable routability: each of them completely routes 7 test cases. Moreover, we observe that NCER and Allegro exhibit complementary behaviors: each is able to solve most of the test cases that the other cannot solve. Together, they completely route 11 test cases. Therefore, by using NCER as a supplement to Allegro, we can solve a broader range of escape routing problems.

AB - The negotiated congestion based routing scheme finds success in FPGA routing and IC global routing. However, its application in simultaneous escape routing, a key problem in PCB design, has never been reported in previous literature. In this paper, we investigate how well the negotiated congestion based router performs on escape routing problems. We propose an underlying routing graph which correctly models the routing resources of the pin grids on board. We then build a Negotiated Congestion based Escape Router (NCER) by applying the negotiated congestion routing scheme on the constructed routing graph. We compare the performance of NCER with that of Cadence PCB router Allegro on 14 industrial test cases, and experimental results show that the two routers have comparable routability: each of them completely routes 7 test cases. Moreover, we observe that NCER and Allegro exhibit complementary behaviors: each is able to solve most of the test cases that the other cannot solve. Together, they completely route 11 test cases. Therefore, by using NCER as a supplement to Allegro, we can solve a broader range of escape routing problems.

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

U2 - 10.1109/ISQED.2010.5450514

DO - 10.1109/ISQED.2010.5450514

M3 - Conference proceeding

AN - SCOPUS:77952643445

SN - 9781424464548

T3 - Proceedings of The International Symposium on Quality Electronic Design, ISQED

SP - 606

EP - 610

BT - Proceedings of the 11th International Symposium on Quality Electronic Design, ISQED 2010

PB - IEEE

T2 - 11th International Symposium on Quality Electronic Design, ISQED 2010

Y2 - 22 March 2010 through 24 March 2010

ER -

A negotiated congestion based router for simultaneous escape routing

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this