Ant Colony Optimization for power efficient routing in manhattan and non-manhattan VLSI architectures
Ant Colony Optimization for power efficient routing in manhattan and non-manhattan VLSI architectures
复制标题
DOI：
10.1109/sis.2009.4937856
复制
发表时间：
2009-05
期刊：
影响因子：
--
通讯作者：
Tamanna Arora;M. Moses
中科院分区：
文献类型：
--
作者：
Tamanna Arora;M. Moses
超大规模集成电路技术的快速发展使单个芯片上可以容纳的晶体管数量增加到约20亿个。在这种复杂的设计中，主要的设计目标是限制芯片的功耗。功耗取决于电容，而电容取决于芯片上导线的长度以及连接芯片不同层上导线的通孔数量。我们使用蚁群优化(ACO)算法来最小化导线长度、通孔和电容。蚁群算法通过结合记忆、随机决策以及类蚂蚁智能体的集体和分布式学习策略，为组合优化问题提供了一个多智能体框架。本文将蚁群算法应用于寻找VLSI芯片互连布线容量最小的最优路径的NP-Hard问题。蚂蚁使用互连布线上的约束作为启发式算法来指导它们的搜索过程。我们在曼哈顿和非曼哈顿的路由体系结构上实施了蚁群算法。将结果与几种最先进的学术路由器进行了比较。ACO布线算法在布线长度方面获得了8%的整体改进，在通孔和电容方面获得了7%的整体改进。运行时间比这些路由器长，但与其他路由器非常相似，后者能够布线所有基准芯片上的所有线路。
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.