Title :
An auction based pre-processing technique to determine detour in global routing
Author :
Xu, Yue ; Chu, Chris
Author_Institution :
Dept. of Electr. & Comput. Eng., Iowa State Univ., Ames, IA, USA
Abstract :
Global Routing has been a traditional EDA problem. It has congestion elimination as the first and foremost priority. Despite of the recent development for popular rip-up and reroute framework, the congestion elimination process remains arbitrary and requires significant tunings. In order to achieve more consistent congestion elimination, we propose a new preprocessing framework for global routing. In the framework, we first identify the most congested global routing locations by an interval overflow lower bound technique. Then we use auction based detour algorithm to compute which nets and where to detour. The framework can be applied to any global router and would help them to achieve significant improvement in both solution quality and runtime.
Keywords :
network routing; technology CAD (electronics); auction; congestion elimination; global routing; interval overflow lower bound technique; pre-processing technique; Complexity theory; Cost function; Heuristic algorithms; Integrated circuits; Mathematical model; Routing; Runtime;
Conference_Titel :
Computer-Aided Design (ICCAD), 2010 IEEE/ACM International Conference on
Conference_Location :
San Jose, CA
Print_ISBN :
978-1-4244-8193-4
DOI :
10.1109/ICCAD.2010.5654089