Untangling twisted nets for bus routing

Tan Yan; Martin D. F. Wong

doi:10.1109/ICCAD.2007.4397297

Untangling twisted nets for bus routing

Tan Yan, Martin D. F. Wong

Office of the Provost

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

15 Citations (Scopus)

Abstract

Previous works [1], [2] on PCB bus routing assume matched pin ordering for both sides. But in practice, the pin ordering might be mismatched and the nets become twisted. In this paper, we propose a preprocessing step to untangle such twisted nets. We also present an algorithm to solve this untangling problem. Our algorithm produces an optimal singledetour routing scheme that rematches the pin ordering. By integrating our preprocessing step into the bus router in [2], we show that many routing problems that cannot be solved previously can now be solved with insignificant increase in runtime.

Original language	English
Title of host publication	Proceedings of The 2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2007
Publisher	IEEE
Pages	396-400
Number of pages	5
ISBN (Print)	9781424413812
DOIs	https://doi.org/10.1109/ICCAD.2007.4397297
Publication status	Published - 4 Nov 2007
Event	2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2007 - DoubleTree Hotel, San Jose, United States Duration: 4 Nov 2007 → 8 Nov 2007 https://ieeexplore.ieee.org/xpl/conhome/4397222/proceeding (Conference proceedings)

Publication series

Name	IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
ISSN (Print)	1092-3152
ISSN (Electronic)	1558-2434

Conference

Conference	2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2007
Country/Territory	United States
City	San Jose
Period	4/11/07 → 8/11/07
Internet address	https://ieeexplore.ieee.org/xpl/conhome/4397222/proceeding (Conference proceedings)

Scopus Subject Areas

Software
Computer Science Applications
Computer Graphics and Computer-Aided Design

Access to Document

10.1109/ICCAD.2007.4397297

Cite this

@inproceedings{fe0cf39cde31488c92afd2d3d5a70a0d,

title = "Untangling twisted nets for bus routing",

abstract = "Previous works [1], [2] on PCB bus routing assume matched pin ordering for both sides. But in practice, the pin ordering might be mismatched and the nets become twisted. In this paper, we propose a preprocessing step to untangle such twisted nets. We also present an algorithm to solve this untangling problem. Our algorithm produces an optimal singledetour routing scheme that rematches the pin ordering. By integrating our preprocessing step into the bus router in [2], we show that many routing problems that cannot be solved previously can now be solved with insignificant increase in runtime.",

author = "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.; 2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2007 ; Conference date: 04-11-2007 Through 08-11-2007",

year = "2007",

month = nov,

day = "4",

doi = "10.1109/ICCAD.2007.4397297",

language = "English",

isbn = "9781424413812",

series = "IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD",

publisher = "IEEE",

pages = "396--400",

booktitle = "Proceedings of The 2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2007",

address = "United States",

url = "https://ieeexplore.ieee.org/xpl/conhome/4397222/proceeding",

}

Yan, T & Wong, MDF 2007, Untangling twisted nets for bus routing. in Proceedings of The 2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2007. IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD, IEEE, pp. 396-400, 2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2007, San Jose, California, United States, 4/11/07. https://doi.org/10.1109/ICCAD.2007.4397297

Untangling twisted nets for bus routing. / Yan, Tan; Wong, Martin D. F.
Proceedings of The 2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2007. IEEE, 2007. p. 396-400 (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD).

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

TY - GEN

T1 - Untangling twisted nets for bus routing

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 - 2007/11/4

Y1 - 2007/11/4

N2 - Previous works [1], [2] on PCB bus routing assume matched pin ordering for both sides. But in practice, the pin ordering might be mismatched and the nets become twisted. In this paper, we propose a preprocessing step to untangle such twisted nets. We also present an algorithm to solve this untangling problem. Our algorithm produces an optimal singledetour routing scheme that rematches the pin ordering. By integrating our preprocessing step into the bus router in [2], we show that many routing problems that cannot be solved previously can now be solved with insignificant increase in runtime.

AB - Previous works [1], [2] on PCB bus routing assume matched pin ordering for both sides. But in practice, the pin ordering might be mismatched and the nets become twisted. In this paper, we propose a preprocessing step to untangle such twisted nets. We also present an algorithm to solve this untangling problem. Our algorithm produces an optimal singledetour routing scheme that rematches the pin ordering. By integrating our preprocessing step into the bus router in [2], we show that many routing problems that cannot be solved previously can now be solved with insignificant increase in runtime.

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

U2 - 10.1109/ICCAD.2007.4397297

DO - 10.1109/ICCAD.2007.4397297

M3 - Conference proceeding

AN - SCOPUS:50249139142

SN - 9781424413812

T3 - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD

SP - 396

EP - 400

BT - Proceedings of The 2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2007

PB - IEEE

T2 - 2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2007

Y2 - 4 November 2007 through 8 November 2007

ER -

Untangling twisted nets for bus routing

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this