Title :
BoxRouter: a new global router based on box expansion and progressive ILP
Author :
Cho, Minsik ; Pan, David Z.
Author_Institution :
Dept. of Electr. & Comput. Eng., Texas Univ., Austin, TX
Abstract :
In this paper, we propose a new global router, BoxRouter, powered by the concept of box expansion and progressive integer linear programming (ILP). BoxRouter first uses a simple prerouting strategy which can predict and capture the most congested regions with high fidelity compared to the final routing. Based on progressive box expansion initiated from the most congested region, BoxRouting is performed with progressive ILP and adaptive maze routing. It is followed by an effective postrouting step which reroutes without rip-up to obtain smooth tradeoff between wirelength and routability. Our experimental results show that BoxRouter significantly outperforms the state-of-the-art published global routers. Given the fundamental importance of routing, such dramatic improvement shall sparkle renewed interests in routing which plays a key role in nanometer design and manufacturing closure
Keywords :
VLSI; integer programming; integrated circuit design; linear programming; network routing; BoxRouter; VLSI; adaptive maze routing; global routing; integer linear programming; nanometer design; Chemicals; Copper; Interference; Linear programming; Pulp manufacturing; Routing; Surfaces; Timing; Very large scale integration; Wire; Algorithms; Congestion; Design; Global Routing; Performance; VLSI;
Conference_Titel :
Design Automation Conference, 2006 43rd ACM/IEEE
Conference_Location :
San Francisco, CA
Print_ISBN :
1-59593-381-6
DOI :
10.1109/DAC.2006.229299