改进的进化蚁群算法在超深亚微米VLSI电路线障布线问题中的应用

摘要

该文我们首先就物理设计中BBL模式下典型的两端绕障碍布线问题,提出了解决不同条件下实际问题的两种模型,即非均匀网格和无网格的两种模型,使问题的复杂度大大下降.然后,介绍了一种兼具生物仿生特性的蚁群和遗传算法特点的进化蚁群算法,并对该算法模仿蚁群的协同学习机制,以及遗传算法的优秀群体中的个体之间信息交换的策略进行了阐述,接着探讨了该算法在总体布线和斯坦纳树问题中的应用.接下来把该算法用于解决两端绕障碍的布局布线问题,同时给出了实验仿真以及在此基础上分析的结果.最后还探讨了两端绕障碍布线问题的模型在多端线网布线问题、总体布线问题以及最小费用问题中应用的可行性问题.

目录

文摘

英文文摘

声明

第一章引言

1.1在微电子技术中发展EDA的战略意义

1.1.1 IC及EDA技术的发展

1.1.2IC及EDA技术的发展迫切性和必要性

1.2 VLSI设计流程

1.3物理设计的定义、流程及主要模式和基本问题

1.3.1物理设计的定义

1.3.2物理设计的流程过程

1.3.3物理设计的主要布图模式

1.4布图设计中的常用的计算智能方法

1.5论文完成的工作和内容安排

第二章VLSI布线设计及其算法介绍

2.1线网布线

2.1.1线网布线问题的描述

2.1.2线网布线的算法

2.1.3布线顺序的影响及处理

2.1.4整体布线

2.2总体布线

2.2.1总体规划图和总体布线图

2.2.2总体布线问题的定义

2.2.3总体布线算法

2.3通道布线

2.3.1通道布线的描述

2.3.2通道布线的定义

2.3.3常见的几种通道布线算法

2.3.4开关盒布线问题

第三章绕障碍线网布线问题及进化蚁群算法

3.1绕障碍两端线网布线问题

3.1.1绕障碍两端线网布线问题

3.1.2绕障碍寻目标路径布线问题的算法研究

3.1.3本文提出的绕障碍寻目标路径布线问题的新算法思路

3.2进化蚁群算法

3.2.1遗传算法

3.2.2蚁群算法

3.2.3进化蚁群算法

3.2.4改进的进化蚁群算法

3.3 IEACS在VLSI布线中的应用研究

3.3.1在VLSI总体布线中的初步应用

3.3.2基于信息素吸引的矩形斯坦纳树算法

第四章进化蚁群算法在线网布线求解中的应用

4.1布图设计中的图论解决方案

4.2网格布线和无网格布线模式

4.3绕障碍不均匀网格布线的连接图解决方案

4.3.1均匀网格布线的缺点以及强连接图的提出

4.3.2均匀网格布线复杂度的减小的一种方法——开窗技术

4.3.3单层不均匀网格强连接图的建立

4.3.4双层或多层强连接图的研究

4.3.5 IECAS在不均匀网格强连接图模型上的C语言实现

4.4绕障碍无网格布线的路径图解决方案

4.4.1绕障碍无网格线网布线模型的路径图

4.4.2双层问题的方案研究

4.4.3 IEACS在路径图上搜索目标路径C语言实现

4.4.4实验例及结果

4.5对两端线网布线进一步研究

4.5.1两端线网布线用于求解多端线网布线的问题

4.5.2两端线网布线用于求解总体布线的问题

4.5.3两端线网布线用于求解最小费用的问题

第五章总结与展望

参考文献

致谢

个人简历