基于蚁群算法的集成电路无网格布线

Gridless Net Routing of Integrate Circuit with Ant Colony Algorithm

蚁群算法[1]作为一种较新的进化类方法,目前已经在若干领域取得了成功的应用,诸如:旅行商问题、二次分配问题、通讯网络中的路由问题以及负载平衡问题、大规模集成电路设计等。本文提出了一种基于蚁群算法的集成电路无网格布线算法。对于给定的布线平面,该算法首先由障碍图形和各个线网的端点生成一个包含最短路径的访问点阵,建立初始信息素矩阵,然后利用蚁群算法所特有的路径寻优功能来找到当前布线路径上的最短路径。同时本文在路径搜索过程中引入了引力的概念,使得蚁群在引力的作用下以较快的速度找到目标端点。

As one of the latter algorithms, ant colony algorithm [1] has been used to many fields, such as： Traveling Salesman Problem, Quadratic Assignment Problem, Network Routing and Load-Balancing Problem, VLSI Design, etc. A gridless net routing with ant colony algorithm for IC design is presented. For a given routing plane, first of all, this algorithm generates the corresponding grid group by barriers and nets＇ ports, establishes initialization pheromone matrix, then the algorithm will use the character of ant colony algorithm to find out the shortest routing path only if it exits. At the same time, the conception of gravitation is used to find the path, which can help ants find the aim more quickly.