蚁群算法在集成电路布线问题中的应用

文摘

英文文摘

声明

1引言

1.1集成电路设计的发展

1.2超大规模集成电路(VLSI)的设计过程

1.3 VLSI中的物理设计

1.3.1物理设计的过程

1.3.2物理设计的设计方法

1.3.3布线过程中的问题

1.3.4论文的结构安排

2物理设计中布图和布线算法简介

2.1算法复杂性的相关概念

2.2布图设计中的一些基本算法

2.2.1图论算法

2.2.2计算几何算法

2.2.3基于运筹学的算法

2.2.4计算智能优化算法

2.3 VLSI布线设计及其算法介绍

2.3.1线网布线

2.3.2总体布线

2.3.3通道布线

3绕障碍线网布线简介及蚁群算法原理

3.1绕障碍线网布线问题描述

3.2绕障碍两端线网布线算法

3.2.1迷宫算法

3.2.2两种图论方案

3.3蚁群算法

3.3.1蚁群算法原理

3.3.2结合TSP介绍蚁群算法的数学模型及流程

4绕障碍线网布线的解决方案及仿真实现

4.1绕障碍线网布线模式的几种类型

4.2基于均匀网格的两端绕障碍线网布线

4.2.1强连接图的概念

4.2.2单层均匀网格两端绕障碍线网布线连接图的建立

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

4.2.4基于均匀网格的蚁群算法的基本思想

4.3单层非均匀网格两端绕障碍线网布线连接图的建立

4.3.1对基本蚁群算法的一些改进

4.3.2实例仿真

4.4绕障碍无网格布线模式

4.4.1绕障碍无网格布线模式路径图的建立

4.4.2无网格布线模型的蚁群算法实现

4.5绕障碍布线的进一步讨论

4.5.1双层或多层布线中连接图的建立

4.5.2多端线网布线

4.5.3蚁群算法在线网布线中的其它应用

5总结与展望

参考文献

致谢