Fashion: A Fast and Accurate Solution to Global Routing Problem

Author

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

Author_Institution

Univ. of California, Los Angeles

Volume

27

Issue

4

fYear

2008

fDate

4/1/2008 12:00:00 AM

Firstpage

726

Lastpage

737

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

computational complexity; integrated circuit design; network routing; Fashion; dynamic pattern routing; low time complexity; movable-segment-driven DPR; overflow reduction; routability-driven global routing problem; runtime reduction; Computer science; Computer science education; Educational programs; Helium; Integrated circuit synthesis; Routing; Runtime; Space exploration; Space technology; Wire; Flexibility; Steiner tree; global routing; physical design; routability;

fLanguage

English

Journal_Title

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

Publisher

ieee

ISSN

0278-0070

Type

jour

DOI

10.1109/TCAD.2008.917590

Filename

4475242