Theories and algorithms on single-detour routing for untangling twisted bus

Research output: Contribution to journalArticle

Abstract

Previous works on PCB bus routing assume matched pin ordering on both sides. But in practice, the pin ordering might be mismatched and the nets become twisted. In this article, we propose a preprocessing step to untangle such twisted nets. We also introduce a practical routing style, which we call single-detour routing, to simplify the untangling problem. We then present a necessary and sufficient condition for the existence of single-detour routing solutions. Furthermore, we present a dynamic-programming-based algorithm to solve the single-detour untangling problem with consideration of wire capacity between adjacent pins. Our algorithm produces an optimal single-detour routing solution that rematches the pin ordering. By integrating our algorithm into the bus router in a previous length-matching router, we show that many routing problems that cannot be solved previously can now be solved with insignificant increase in runtime.

Original languageEnglish (US)
Article number46
JournalACM Transactions on Design Automation of Electronic Systems
Volume14
Issue number3
DOIs
StatePublished - May 1 2009

Keywords

  • Bus routing
  • Dynamic programming
  • Printed circuit board (PCB)
  • Single-detour routing
  • Twisted bus

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'Theories and algorithms on single-detour routing for untangling twisted bus'. Together they form a unique fingerprint.

  • Cite this