A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> c: PARALLEL ALGORITHMS <s> As design complexities and circuit densities are increasing, the detailed-routing (DR) problem is becoming a more and more challenging problem. Due to the high complexity of DR algorithms, it is very important to start the routing process with clean solutions rather than starting with suboptimal routes and trying to fix them in an iterative process. In this paper, we propose an escape-routing algorithm that can optimize routing of a set of nets around their terminals. For this, we first propose a polynomial-time algorithm that guarantees to find the optimal escape-routing solution for a set of nets when the track structures are uniform. Then, we use this algorithm as a baseline and study the general problem with arbitrary track structures. For this, we propose a novel multicommodity-flow (MCF) model that has a one-to-one correspondence with the escape-routing problem. This MCF model is novel in the sense that the interdependence and contention between different flow commodities is minimal. Using this model, we propose a Lagrangian-relaxation-based algorithm to solve the escape problem. Our experiments demonstrate that this algorithm improves the overall routability significantly by reducing the number of nets that require rip-up and reroute. <s> BIB001 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> c: PARALLEL ALGORITHMS <s> Detailed routing is an important stage in very large scale integrated physical design. Due to the extreme scaling of transistor feature size and the complicated design rules, ensuring routing completion without design rule checking (DRC) violations becomes more and more difficult. Studies have shown that the low routing quality partly results from nonoptimal net-ordering nature of traditional sequential methods. The concurrent routing strategy is always based on an NP-hard model, thus is at a disadvantage in runtime. In this paper, we present a novel concurrent detailed routing algorithm that routes all nets simultaneously. Based on the multicommodity flow model, detailed routing problem with complex design rule constraints is formulated as an integer linear programming. Some model simplification heuristics and efficient model solving algorithms are proposed to improve the runtime. Experimental results show that, the proposed algorithms can reduce the DRC violations by 80%, meanwhile can reduce wirelength and via count by 5% and 8% compared with an industry tool. In addition, the proposed algorithm is general that it can be adopted as an incremental detailed router to refine a routing solution, so the number of DRC violations that industry tool cannot fix are further reduced by 27%. <s> BIB002
In order to reduce the dependence of routing results on the order of nets, a parallel detailed routing algorithm based on multi-commodity flow model is proposed BIB002 , which can simultaneously route for multiple nets. Ozdal BIB001 presented an insightful technique to perform escape routing for dense pin clusters and a Lagrangian relaxation based heuristic was proposed.