论文部分内容阅读
当前集成电路产业向深亚微米工艺不断推进,正力图突破100nm大关。现有EDA工具难以应付复杂度呈指数增长的诸多VLSI设计难题,也缺乏对深亚微米工艺下一系列新问题的考虑。另一方面,在计算智能领域,各种优化技术日新月异,为解决非NP和NP复杂度的大规模、超大规模问题展示了广阔的前景。本文正是在这样的背景下,研究计算智能方法在深亚微米工艺下性能驱动VLSI生产工序中关键环节—物理设计中的应用。随着VLSI的工艺向深亚微米的推进,物理设计中的布线问题(无论是非NP问题、NP完全问题和NP困难问题),由于问题规模的急剧增大,都迫切需要更有效的优化算法解决方案。蚁群算法作为一种较新的进化类方法,目前已经在若干领域取得了成功的应用,诸如:旅行商问题、二次分配问题、通讯网络中的路由问题以及负载平衡问题、大规模集成电路设计等。本文深入讨论了蚁群算法应用于解决TSP问题,并对其进行了基本功能验证;对开关盒布线,本文也进行了初步尝试,针对较少的线网进行了布线仿真;就物理设计中BBL模式下典型的两端绕障碍布线问题,首先提出了解决不同条件下实际问题的两种理论模型,模型分别基于图论和计算几何学方法,减少了问题的时空复杂度。然后,介绍了一种基于生物仿生特性的蚁群算法,通过选择适当的模型表述,该算法可采用蚁群任务调度策略,模仿蚁群的协同学习机制,来解决两端绕障碍的布局布线问题,并能给出较优的解。本文提出了一种基于蚁群算法的集成电路无网格布线算法。对于给定的布线平面,该算法首先由障碍图形和各个线网的端点生成一个包含最短路径的访问点阵,建立初始信息素矩阵,然后利用蚁群算法所特有的路径寻优功能来找到当前布线路径上的最短路径。同时本文在路径搜索过程中引入了引力的概念,使得蚁群在引力的作用下以较快的速度找到目标端点。粒子群优化算法作为一种较新的进化类方法,目前已经在若干领域取得了成功的应用,本文提出了一种基于粒子群优化算法的集成电路无网格布线算法。对于给定的布线平面,该算法首先由障碍图形和各个线网的端点生成一个包含最短路径的访问点阵,建立初始粒子位置矩阵,然后利用粒子群优化算法的路径寻优功能来找到当前布线路径上的最短路径。