Title :
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
fDate :
4/1/2008 12:00:00 AM
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;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
DOI :
10.1109/TCAD.2008.917590
