蚁群算法在集成电路布线设计中的应用_东北大学_张鹏.pdf

东北大学论文 东北大学 离散数学课业设计论文 论文题目： 蚁群算法在集成电路布线问题中的应用 学生姓名： 张 鹏 年级专业： 自动化1104 学 号： 2 0 1 1 3 5 1 7 指导教师： 唐 青 松 日 期： 2013 05 16 东北大学论文 蚁群算法在集成电路布线问题中的应用 摘要 随着集成电路规模的不断增大，特征尺寸不断减小，时钟频率越 来越高，给集成电路工艺技术和生产技术(设备和材料) 以及设计生产 率等诸多方面的问题带来了更多的技术挑战，其中一个非常关键的环 节是集成电路设计技术的发展己经远远落后于集成电路的加工能力 的发展，另一方面，随着 VLSI 电路复杂性越来越高，其物理设计中 的许多问题目前己经被证明是 N.P 困难问题，所以一个快速的高效的 物理版图设计必须依赖于先进的 EDA 工具和先进的设计方法，而在 计算机智能领域，各种优化技术的蓬勃发展为解决非 NP 问题，N.P 完全问题和 NP 困难问题提供了新的思路和解决方法，本文正是在这 种背景下，讨论计算智能方法在 VLSI 设计过程中最重要的一个环节) 物理设计中的应用。 VLSI 工艺不断发展，物理设计中的布线问题的规模也急剧增大， 传统的优化算法正面临着计算量爆炸，容易陷入局部极值和无法接近 全局最优的难题，所以必须寻找更有效的优化方法，本文首先结合旅 行商问题(TSP)介绍了基于仿生特性的蚁群算法原理，随后介绍了 VLSI 物理设计中基于 BBL(BuildingBlockSLayout)模式的绕障碍线网布线问 题，然后将蚁群算法和两端绕障碍线网布线问题相结合，讨论了基于 网格和无网格模型的连接图的建立和解决方法，最后讨论了多层布线 和多端线网布线的解决方案，并讨论了蚁群算法在布线中其它问题中 的可行性， 东北大学论文 关键词:集成电路设计，布线设计，绕障碍线网布线，最短路径，蚁 群算法 引言 晶体管的发明揭开了微电子发展的序幕，同时为集成电路的问世 奠定 了 基础 ， 集 成电 路 自诞 生 以 来 ， 经 历了 小 规 模集 成 (smallsealeIniegration ，551) ，中规模集成(MediumScaleIntegration ， MSI)，大规模集成(LarseSealeIntegration，Lsl)，目前己进入超大规模 (Very Large Scale Integration ， VLSI) 和特大规模(Ultra Large Scale Integration，ULSI)阶段，传统上一般把含有 10^4 至 10^6 个甚至更多 晶体管或 3000 个以上门单元的集成电路(IniegratedCireuit，IC)称为 VLSI ，电子产业经过了近 50 年的发展使人类进入了信息时代，而集 成电路产业更是信息技术(hiformationTechnology，IT)产业的核心和基 础。目前，微电子已经成为国民经济和人类不可短缺的 “粮食”，其 发展水平是衡量一个国家综合实力的重要标志，我国为加强基础性制 造业的建设，在 20 世纪 90 年代就启动了 “909 ”工程，“十一五”计 划里，更是明确地把软件产业和集成电路产业确定