Ant Colony Optimization for Power Efficient Routing in Manhattan and Non-Manhattan VLSI Architectures

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 wire-length, vias and capacitance. ACID 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 ACID 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.