skip to main content
10.5555/1326073.1326155acmconferencesArticle/Chapter ViewAbstractPublication PagesiccadConference Proceedingsconference-collections
research-article

Untangling twisted nets for bus routing

Published: 05 November 2007 Publication History

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 single-detour 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.

References

[1]
M. M. Ozdal and M. D. F. Wong, "A provably good algorithm for high performance bus routing," ICCAD'04, pages 830--837.
[2]
M. M. Ozdal and M. D. F. Wong, "Length-matching routing for high-speed printed circuit boards," ICCAD'03, pages 394--400.
[3]
T. H. Cormen, C. E. Leiserson and R. L. Rivest, Introduction to Algorithms, MIT Press, 1992.
[4]
L. W. Ritchey, "Busses: What are they and how do they work?" Printed Circuit Design Magazine, 2000.
[5]
L. W. Ritchey, Right the First Time-A Practical Handbook on High Speed PCB and System Design, Volume 1, 2003.
[6]
D. Wiens, "Printed circuit board routing at the threshold," White Paper, Mentor Graphics, 2000.

Cited By

View all
  • (2019)Synergistic Topology Generation and Route Synthesis for On-Chip Performance-Critical Signal GroupsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.283442438:6(1147-1160)Online publication date: 1-Jun-2019
  • (2017)StreakProceedings of the 54th Annual Design Automation Conference 201710.1145/3061639.3062321(1-6)Online publication date: 18-Jun-2017
  • (2010)Recent research development in PCB layoutProceedings of the International Conference on Computer-Aided Design10.5555/2133429.2133514(398-403)Online publication date: 7-Nov-2010
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ICCAD '07: Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design
November 2007
933 pages
ISBN:1424413826
  • General Chair:
  • Georges Gielen

Sponsors

Publisher

IEEE Press

Publication History

Published: 05 November 2007

Check for updates

Qualifiers

  • Research-article

Conference

ICCAD07
Sponsor:

Acceptance Rates

ICCAD '07 Paper Acceptance Rate 139 of 510 submissions, 27%;
Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 09 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2019)Synergistic Topology Generation and Route Synthesis for On-Chip Performance-Critical Signal GroupsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.283442438:6(1147-1160)Online publication date: 1-Jun-2019
  • (2017)StreakProceedings of the 54th Annual Design Automation Conference 201710.1145/3061639.3062321(1-6)Online publication date: 18-Jun-2017
  • (2010)Recent research development in PCB layoutProceedings of the International Conference on Computer-Aided Design10.5555/2133429.2133514(398-403)Online publication date: 7-Nov-2010
  • (2010)CAFE routerProceedings of the 2010 Asia and South Pacific Design Automation Conference10.5555/1899721.1899782(281-286)Online publication date: 18-Jan-2010
  • (2010)Two-sided single-detour untangling for bus routingProceedings of the 47th Design Automation Conference10.1145/1837274.1837325(206-211)Online publication date: 13-Jun-2010
  • (2009)Theories and algorithms on single-detour routing for untangling twisted busACM Transactions on Design Automation of Electronic Systems10.1145/1529255.152926814:3(1-21)Online publication date: 4-Jun-2009
  • (2009)BSG-routeIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2009.203035228:11(1679-1690)Online publication date: 1-Nov-2009
  • (2008)BSG-RouteProceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design10.5555/1509456.1509569(499-505)Online publication date: 10-Nov-2008

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media