论文部分内容阅读
布线设计是超大规模集成电路(VLSI)物理设计的一个重要阶段。随着集成电路规模的日益扩大,传统的算法已经不能够满足设计要求。所以,要求不断提出新的算法。本文为超大规模集成电路(VLSI)物理设计提供一种智能化的线网布线方法。两端绕障碍布线是超大规模集成电路线网布线的基本问题。所以,文章以该问题的研究为切入点。该问题属NP问题。蚁群系统是一种典型的智能算法。文章对蚁群系统进行了研究,得出了蚁群系统有搜索时间长、算法易停滞的缺点。为了克服蚁群系统的这些不足之处,提出了改变布线平面初始信息素分布和改进蚂蚁在搜索过程中状态转移规则的改进方案,并结合禁忌搜索算法提出了解决线网布线问题的一种新的智能算法:禁忌蚁群系统(tabu-ant colonies system)。以连接图作为布线平面模型,用Java语言实现了新的智能算法。对会给实验结果产生重要影响的参数q0的取值进行了讨论,得出当q0取值适中时,实验可以获得较好的收敛效果的结论。通过一些实验的统计结果,对新算法和其它算法的性能进行了比较和分析。实验证明,该算法克服了搜索过程中的盲目性,有效加快了蚁群系统早期的收敛速度,并避免了局部最优,可以在较短时间内找到两端线网布线的最佳路径。该算法可以应用到无网格布线和多点、多层布线中。由于无网格布线模型中节点的数目相对网格布线模型中节点的数目较少,因此,算法的搜索空间和布线所用的时间相对减小。之后,提出了多点、多层布线的解决方案。以两层布线为例,可以用一个层面作为水平线网布线区域,另外一个层面作为垂直线网布线区域,层与层之间用通孔进行连接。用典型的最小生成树算法普里姆(Prim)算法对该问题进行求解,提出了用禁忌蚁群系统来搜索Prim算法每次迭代过程中当前最小代价路径的解决方法。这样,就把复杂的多点布线问题简化为多次求两点之间最短路径的问题。用这种方法对一个六点双层布线的实例进行了实验。实验结果表明,这种具有智能特征的最小生成树算法能够有效地解决多点、多层布线问题。