Fashion: A fast and accurate solution to global routing problem

Zhen Cao; Tom Tong Jing; Jinjun Xiong; Yu Hu; Zhe Feng; Lei He; Xian Long Hong

doi:10.1109/TCAD.2008.917590

Fashion: A fast and accurate solution to global routing problem

Zhen Cao
, Tom Tong Jing
, Jinjun Xiong
, Yu Hu
, Zhe Feng
, Lei He
, Xian Long Hong

Department of Computer Science and Engineering

University at Buffalo

Research output: Contribution to journal › Article › peer-review

14 Scopus citations

Abstract

This paper presents a fast and accurate solution, namely Fashion, to routability-driven global routing problem. Fashion is based on two efficient yet effective techniques: 1) dynamic pattern routing (DPR) and 2) movable-segment-driven DPR. These two techniques enable Fashion to explore large solution space to achieve high routability with low time complexity. Compared with BoxRouter, Fashion has a shorter wire length and reduces overflow and runtime by 5 and 15 times, respectively. Compared with FastRoute, Fashion has similar runtime but 90% smaller overflow and 1.9% shorter wire length. Fashion is significantly better than Labyrinth and Fengshui in terms of overflow, wire length, and runtime.

Original language	English
Article number	4475242
Pages (from-to)	726-737
Number of pages	12
Journal	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume	27
Issue number	4
DOIs	https://doi.org/10.1109/TCAD.2008.917590
State	Published - Apr 2008

Keywords

Flexibility
Global routing
Physical design
Routability
Steiner tree

Access to Document

10.1109/TCAD.2008.917590

Cite this

@article{d6ea24f4421b43e2841ed06e9876dd8d,

title = "Fashion: A fast and accurate solution to global routing problem",

abstract = "This paper presents a fast and accurate solution, namely Fashion, to routability-driven global routing problem. Fashion is based on two efficient yet effective techniques: 1) dynamic pattern routing (DPR) and 2) movable-segment-driven DPR. These two techniques enable Fashion to explore large solution space to achieve high routability with low time complexity. Compared with BoxRouter, Fashion has a shorter wire length and reduces overflow and runtime by 5 and 15 times, respectively. Compared with FastRoute, Fashion has similar runtime but 90\% smaller overflow and 1.9\% shorter wire length. Fashion is significantly better than Labyrinth and Fengshui in terms of overflow, wire length, and runtime.",

keywords = "Flexibility, Global routing, Physical design, Routability, Steiner tree",

author = "Zhen Cao and Jing, \{Tom Tong\} and Jinjun Xiong and Yu Hu and Zhe Feng and Lei He and Hong, \{Xian Long\}",

year = "2008",

month = apr,

doi = "10.1109/TCAD.2008.917590",

language = "English",

volume = "27",

pages = "726--737",

journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",

issn = "0278-0070",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "4",

}

TY - JOUR

T1 - Fashion

T2 - A fast and accurate solution to global routing problem

AU - Cao, Zhen

AU - Jing, Tom Tong

AU - Xiong, Jinjun

AU - Hu, Yu

AU - Feng, Zhe

AU - He, Lei

AU - Hong, Xian Long

PY - 2008/4

Y1 - 2008/4

N2 - This paper presents a fast and accurate solution, namely Fashion, to routability-driven global routing problem. Fashion is based on two efficient yet effective techniques: 1) dynamic pattern routing (DPR) and 2) movable-segment-driven DPR. These two techniques enable Fashion to explore large solution space to achieve high routability with low time complexity. Compared with BoxRouter, Fashion has a shorter wire length and reduces overflow and runtime by 5 and 15 times, respectively. Compared with FastRoute, Fashion has similar runtime but 90% smaller overflow and 1.9% shorter wire length. Fashion is significantly better than Labyrinth and Fengshui in terms of overflow, wire length, and runtime.

AB - This paper presents a fast and accurate solution, namely Fashion, to routability-driven global routing problem. Fashion is based on two efficient yet effective techniques: 1) dynamic pattern routing (DPR) and 2) movable-segment-driven DPR. These two techniques enable Fashion to explore large solution space to achieve high routability with low time complexity. Compared with BoxRouter, Fashion has a shorter wire length and reduces overflow and runtime by 5 and 15 times, respectively. Compared with FastRoute, Fashion has similar runtime but 90% smaller overflow and 1.9% shorter wire length. Fashion is significantly better than Labyrinth and Fengshui in terms of overflow, wire length, and runtime.

KW - Flexibility

KW - Global routing

KW - Physical design

KW - Routability

KW - Steiner tree

UR - https://www.scopus.com/pages/publications/41549140997

U2 - 10.1109/TCAD.2008.917590

DO - 10.1109/TCAD.2008.917590

M3 - Article

SN - 0278-0070

VL - 27

SP - 726

EP - 737

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

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

IS - 4

M1 - 4475242

ER -

Fashion: A fast and accurate solution to global routing problem

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this