基于蚁群算法的超大规模集成电路布线研究

摘要

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

目录

文摘

英文文摘

声明

第一章绪论

1.1集成电路的发展

1.2 EDA的发展与问题

1.3超大规模集成电路设计概述

1.4物理设计过程

1.4.1物理设计

1.4.2物理设计的主要模式

1.5布线设计过程

1.5.1布线过程中出现的新问题

1.5.2时钟布线问题研究进展

1.6本文完成的工作及论文的内容安排

第二章VLSI布线设计算法分析

2.1 VLSI布线问题

2.2时钟布线问题

2.3物理设计算法

2.3.1图论算法

2.3.2计算几何算法

2.3.3基于运筹学的算法

2.3.4计算智能优化算法

2.4小结

第三章蚁群算法的研究及改进

3.1蚁群算法的原理

3.2基于蚁群算法所进行的相关工作

3.3蚁群算法应用于TSP旅行商问题

3.3.1基本程序流程

3.3.2仿真测试

3.3.3 TSP旅行商算法的优缺点

3.4蚁群算法应用于二叉树问题

3.4.1算法思想

3.4.2仿真测试

3.5走折线布线

3.5.1算法思想

3.5.2仿真结果

3.6开关盒布线问题

3.6.1开关盒布线问题的算法描述

3.6.2仿真测试结果

3.7仿真过程中的问题

3.8与其他算法的比较

3.8.1与迷宫算法的比较

3.8.2与遗传算法的比较

3.9小结

第四章基于无网格布线的蚁群算法

4.1两端绕障碍网格布线的连接图模型

4.1.1强连接图

4.1.2单层互连模型的建立

4.1.3复杂度减小以及开窗技术的原理

4.2无网格布线

4.3无网格布线模型的路径图

4.3.1路径图的定义和证明

4.3.2路径图的构造

4.4蚁群算法应用于无网格布线

4.4.1无网格布线的基本思想

4.4.2总体访问点阵的生成

4.4.3访问路径的搜索

4.4.4蚁群应用的改进

4.4.5信息素的刷新

4.4.6具体的布线

4.4.7多组多端点的线网

4.5实例仿真和结果

4.6小结

第五章基于粒子群算法的VLSI布线研究

5.1粒子群优化算法

5.2 DPSO优化算法

5.3 PSO优化算法的改进

5.3.1 PSO算法的优势与缺点

5.3.2粒子群优化算法与遗传算法的比较和改进方法

5.3.3杂交PSO算法

5.3.4 MPSO优化算法

5.3.5灾变粒子群算法

5.4无网格粒子群优化算法布线的基本思想

5.4.1数学模型

5.4.2总体访问点阵的生成

5.4.3 Prufer数编码树

5.4.4 Prufer数与访问点的关系

5.4.5初始化

5.4.6非模糊化

5.4.7算法描述

5.4.8实例仿真和结果

5.5小结

第六章总结与展望

6.1总结

6.2展望

致谢

参考文献

博士期间的学术论文及研究成果