A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> 2) APPLYING ACO TO GLOBAL ROUTING <s> The rectilinear Steiner minimum tree (RSMT) problem is one of the fundamental problems in physical design, especially in routing, which is known to be NP-complete. This paper presents a practical heuristic for RSMT construction based on ant colony optimization (ACO). This algorithm has been implemented on a Sun workstation with Unix operating system and the results have been compared with the GeoSteiner 3.1 and a recent work using batched greedy triple construction (BGTC). Experimental results show that our algorithm, named ACO-Steiner, can get a very short run time and keep the high performance. <s> BIB001 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> 2) APPLYING ACO TO GLOBAL ROUTING <s> Rapid advances in VLSI technology have increased the number of transistors that fit on a single chip to about two billion. In such complex designs, a primary design goal is to limit the power consumption of the chip. Power consumption depends on capacitance, which depends on the length of wires on the chip and the number of vias which connect wires on different layers of the chip. We use Ant Colony Optimization (ACO) algorithms to minimize wirelength, vias and capacitance. ACO provide a multi-agent framework for combinatorial optimization by combining memory, stochastic decision making and strategies of collective and distributed learning by ant-like agents. This paper applies ACO to the NP-hard problem of finding optimal routes with minimum capacitance for interconnect routing on VLSI chips. The constraints on interconnect routing are used by ants as heuristics which guide their search process. We implemented ACO algorithms on both manhattan and non-manhattan routing architectures. The results are compared with several state of the art academic routers. The ACO routing algorithm was able to obtain an overall improvement of 8% in terms of wire-length, 7% in terms of vias and capacitance. Running times were longer than those routers, but very similar to the other router which is able to route all wires on all benchmark chips. <s> BIB002 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> 2) APPLYING ACO TO GLOBAL ROUTING <s> Rapid advances in VLSI technology have increased the number of transistors that fit on a single chip to about two billion. A frequent problem in the design of such high performance and high density VLSI layouts is that of routing wires that connect such large numbers of components. Most wire‐routing problems are computationally hard. The quality of any routing algorithm is judged by the extent to which it satisfies routing constraints and design objectives. Some of the broader design objectives include minimizing total routed wire length, and minimizing total capacitance induced in the chip, both of which serve to minimize power consumed by the chip. Ant Colony Optimization algorithms (ACO) provide a multi‐agent framework for combinatorial optimization by combining memory, stochastic decision and strategies of collective and distributed learning by ant‐like agents. This paper applies ACO to the NP‐hard problem of finding optimal routes for interconnect routing on VLSI chips. The constraints on interconnec... <s> BIB003
ACO-Steiner can be easily extended to other routing problems such as power-driven routing. References BIB002 and BIB003 implement ACO algorithms on both grid-less Manhattan architectures and non-Manhattan routing architectures that use diagonal routing, which aim at limiting the power consumption of the chip. The difference is that, BIB003 actives power on the chip not only by minimizing wirelength and vias, but also capacitance. In BIB003 , the characteristics of ant colony's memory, stochastic decision making and strategies of collective and distributed learning are used to find the shortest possible routes, then choose the one that minimizes capacitance from those routes. Unlike BIB001 , an ant will not die when meeting another ant, but rather a particular connection is marked as completed. Completing these paths can also reduce redundant paths, thereby decreasing the number of vias. The first step of the algorithm is to create a Hanan grid, then start routing nets using ACO. Notice that small nets are routed first in order to minimize obstruction from bigger nets. The specific ACO-Route approach can be described as Algorithm 2. The probability of unvisited nodes are calculated through the heuristic to minimize the distance between the ant and other ants and pheromone values (Step 10). If the ant meets another ant, for both the ants add the routes traveled by one to the route list of the other. The experiments prove that ACO is successful in solving the multi-constraint optimization problem of VLSI chip power minimization. Construct a complete tour for ant; 10 Calculate the probability of unvisited nodes; 11 Deposit pheromone on the paths taken by the ant;