A new strategy for simultaneous escape based on boundary routing

Lijuan Luo, Tan Yan, Qiang Ma, Martin D F Wong, Toshiyuki Shibuya

Research output: Contribution to journalArticle

Abstract

Simultaneous escape routing on dense circuit boards is a very challenging task and a great amount of manual effort is still needed in order to achieve high routability. In this paper, we present a new simultaneous escape routing algorithm which is based upon a novel boundary routing approach. Our algorithm can solve complicated escape problems in a very short time. For a set of industrial escape problems, our algorithm successfully solved all of them while Cadence Allegro PCB router was only able to complete the routing of half of the problems. In addition, we propose a clustering strategy targeting at large escape routing problems. Experimental results show that this clustering strategy can significantly cut down the runtime of our router when solving large problems.

Original languageEnglish (US)
Article number5689348
Pages (from-to)205-214
Number of pages10
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume30
Issue number2
DOIs
StatePublished - Feb 1 2011

Fingerprint

Routers
Routing algorithms
Polychlorinated biphenyls
Networks (circuits)

Keywords

  • Boundary routing
  • computer-aided design
  • escape routing
  • printed circuit board (PCB)

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Cite this

A new strategy for simultaneous escape based on boundary routing. / Luo, Lijuan; Yan, Tan; Ma, Qiang; Wong, Martin D F; Shibuya, Toshiyuki.

In: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 30, No. 2, 5689348, 01.02.2011, p. 205-214.

Research output: Contribution to journalArticle

@article{626ece5487e042579c8dc3c5ac5afd89,
title = "A new strategy for simultaneous escape based on boundary routing",
abstract = "Simultaneous escape routing on dense circuit boards is a very challenging task and a great amount of manual effort is still needed in order to achieve high routability. In this paper, we present a new simultaneous escape routing algorithm which is based upon a novel boundary routing approach. Our algorithm can solve complicated escape problems in a very short time. For a set of industrial escape problems, our algorithm successfully solved all of them while Cadence Allegro PCB router was only able to complete the routing of half of the problems. In addition, we propose a clustering strategy targeting at large escape routing problems. Experimental results show that this clustering strategy can significantly cut down the runtime of our router when solving large problems.",
keywords = "Boundary routing, computer-aided design, escape routing, printed circuit board (PCB)",
author = "Lijuan Luo and Tan Yan and Qiang Ma and Wong, {Martin D F} and Toshiyuki Shibuya",
year = "2011",
month = "2",
day = "1",
doi = "10.1109/TCAD.2010.2097173",
language = "English (US)",
volume = "30",
pages = "205--214",
journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",
issn = "0278-0070",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "2",

}

TY - JOUR

T1 - A new strategy for simultaneous escape based on boundary routing

AU - Luo, Lijuan

AU - Yan, Tan

AU - Ma, Qiang

AU - Wong, Martin D F

AU - Shibuya, Toshiyuki

PY - 2011/2/1

Y1 - 2011/2/1

N2 - Simultaneous escape routing on dense circuit boards is a very challenging task and a great amount of manual effort is still needed in order to achieve high routability. In this paper, we present a new simultaneous escape routing algorithm which is based upon a novel boundary routing approach. Our algorithm can solve complicated escape problems in a very short time. For a set of industrial escape problems, our algorithm successfully solved all of them while Cadence Allegro PCB router was only able to complete the routing of half of the problems. In addition, we propose a clustering strategy targeting at large escape routing problems. Experimental results show that this clustering strategy can significantly cut down the runtime of our router when solving large problems.

AB - Simultaneous escape routing on dense circuit boards is a very challenging task and a great amount of manual effort is still needed in order to achieve high routability. In this paper, we present a new simultaneous escape routing algorithm which is based upon a novel boundary routing approach. Our algorithm can solve complicated escape problems in a very short time. For a set of industrial escape problems, our algorithm successfully solved all of them while Cadence Allegro PCB router was only able to complete the routing of half of the problems. In addition, we propose a clustering strategy targeting at large escape routing problems. Experimental results show that this clustering strategy can significantly cut down the runtime of our router when solving large problems.

KW - Boundary routing

KW - computer-aided design

KW - escape routing

KW - printed circuit board (PCB)

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

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

U2 - 10.1109/TCAD.2010.2097173

DO - 10.1109/TCAD.2010.2097173

M3 - Article

AN - SCOPUS:78951469738

VL - 30

SP - 205

EP - 214

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

SN - 0278-0070

IS - 2

M1 - 5689348

ER -