第1章 超大规模集成电路布图问题、方法及版图设计自动化 1
1.1 VLSI设计流程 1
1.1.1 传统的VLSI设计流程 1
1.1.2 传统的布图设计过程 2
1.1.3 VLSI设计流程的新趋势 3
1.1.4 VLSI物理设计的新趋势 4
1.2 芯片费用和电性能的估计 5
1.3 布图模式 5
1.3.1 全定制版图模式 6
1.3.2 门阵列设计模式 8
1.3.3 标准单元设计模式 8
1.3.4 现场可编程门阵列 9
1.3.5 不同设计方法的比较 11
1.4 系统封装类型 11
参考文献 14
第2章 VLSI器件设计和制造的布图描述 15
2.1 VLSI制造工艺 15
2.2 设计规则 16
2.3 基本器件的版图实例 17
2.4 工艺制造中的其他因素 18
2.5 VLSI版图的几何表示 21
2.5.1 CIF格式 21
2.5.2 EDIF格式 22
2.5.3 GDSII格式 26
2.5.4 OASIS格式 30
2.6 单元的拓扑描述与网表描述 33
参考文献 35
第3章 VLSI布图的数学基础和数据结构 36
3.1 图的基本概念及其基本数据结构 36
3.1.1 基本概念 36
3.1.2 图的基本数据结构 37
3.2 算法及其复杂度 39
3.2.1 算法问题及算法复杂性 39
3.2.2 求解NP-困难问题的方法 40
3.3 解决布图问题的基本算法 42
3.3.1 图论算法 42
3.3.2 确定性算法 50
3.3.3 随机算法 54
3.4 多目标优化 57
3.4.1 多目标优化问题的定义（MOP） 57
3.4.2 多目标优化方法 57
3.5 布图设计中涉及的基本数据结构 63
3.5.1 版图数据的基本操作 63
3.5.2 链表结构 64
3.5.3 基于Bin的结构 65
3.5.4 邻接指针 66
3.5.5 角勾链 66
3.5.6 四叉树 70
3.5.7 各种版图数据结构的比较 70
3.5.8 布图中模块和网表的数据结构 71
3.5.9 树的数据结构 74
参考文献 77
第4章 电路系统的划分 79
4.1 问题描述 79
4.2 代价函数和约束 80
4.3 解决划分问题的基本方法 81
参考文献 86
第5章 布图规划 88
5.1 问题描述 88
5.2 布图结构的表示方法 89
5.2.1 可二划分结构 89
5.2.2 不可二划分结构 90
5.3 解决布图规划问题的方法 96
5.3.1 镞生长法 96
5.3.2 解析法 98
5.3.3 对偶图技术 101
5.3.4 模拟退火算法 105
5.3.5 其他方法 108
5.4 高层次综合与布图结合技术 109
5.4.1 传统的布图规划 109
5.4.2 传统的高层次综合 109
5.4.3 高层次与布图规划结合 110
参考文献 116
第6章 布局 119
6.1 问题描述 119
6.2 代价函数与约束 120
6.2.1 线长估计 120
6.2.2 总线长最小化 123
6.2.3 最大割线数目最小化 123
6.2.4 最大密度最小化 123
6.2.5 性能最大化 124
6.2.6 其他约束 124
6.3 解决布局问题的方法 125
6.3.1 基于划分的方法 125
6.3.2 启发式最小割算法 129
6.3.3 解析方法 131
6.3.4 模拟退火 137
6.3.5 神经网络 138
6.3.6 遗传算法 141
6.3.7 其他 143
参考文献 143
第7章 线网布线 146
7.1 迷宫算法 147
7.1.1 基本的迷宫算法——Lee算法 147
7.1.2 迷宫算法的改进 150
7.1.3 迷宫算法的比较 152
7.1.4 迷宫算法中提高布线效率的方法 153
7.1.5 多端线网布线 156
7.1.6 多层布线 156
7.2 线探索法 157
7.3 布线顺序的影响及其处理 158
7.4 整体布线 160
7.5 电源地线线网布线 162
7.6 层次式布线方法 163
7.7 全芯片多级布线方法 163
7.8 最新的研究成果 164
参考文献 165
第8章 总体布线 167
8.1 总体布线问题 167
8.1.1 总体布线图 167
8.1.2 总体布线问题定义 168
8.2 总体布线算法的分类 169
8.3 总体布线图上的斯坦纳树算法 171
8.3.1 基于最短路径的算法 172
8.3.2 基于最小代价生成树的算法 172
8.3.3 基于可分离性的算法 173
8.3.4 基于非矩形边斯坦纳树的算法 175
8.3.5 Dreyfus-Wagner算法 175
8.3.6 最小最大权重边的斯坦纳树算法 177
8.4 总体布线算法 178
8.4.1 串行布线和拆线重布算法 178
8.4.2 基于加权的斯坦纳树算法 179
8.4.3 基于整数规划的方法 180
8.4.4 基于网络流的总体布线算法 183
8.4.5 基于拥挤度分析的并行层次迭代布线算法 188
8.4.6 启发式总体布线 190
8.5 其他最新算法 192
8.5.1 FGR 193
8.5.2 BoxRouter 194
8.5.3 MaizeRouter 195
8.5.4 FastRoute 195
8.6 时钟布线技术 197
8.6.1 时钟布线的研究对象 198
8.6.2 时钟布线问题描述 199
8.6.3 时钟布线算法简介 199
参考文献 203
第9章 其他布图问题 207
9.1 通孔优化问题 207
9.1.1 通孔最少化 207
9.1.2 带约束的通孔最小化问题 208
9.1.3 二层CVM问题的图表示法 209
9.1.4 无约束的通孔最小化 212
9.1.5 交叉通道的TVM问题的最优化算法 212
9.1.6 一般的k-TVM问题的近似解 213
9.1.7 基于拓扑解的布线 213
9.1.8 通孔最少化算法 214
9.1.9 统一通孔最少化和线长最小化层分配算法 218
9.1.10 最少通孔和最小线长分层的无向图表示 219
9.2 时延和功耗优化 220
9.2.1 时延和功耗双重驱动布局算法 220
9.2.2 延迟模型 221
9.2.3 问题定义 221
9.2.4 功耗 223
9.3 芯片热模型和均匀分布 226
9.3.1 热问题分析 226
9.3.2 功耗和热的关系 227
9.3.3 在芯片设计的不同层次上考虑热问题 228
9.3.4 热问题的解决方案与技术 230
9.3.5 小结 234
9.4 布图设计的可制造性 234
参考文献 235
第10章 三维芯片布图问题 241
10.1 三维芯片对集成电路带来的影响 241
10.2 三维芯片的布图规划表示方法 243
10.3 三维芯片布局算法 245
10.4 三维芯片布线与热通孔规划 247
10.5 三维芯片的热模型及求解算法 249
10.5.1 热模型 249
10.5.2 热模型的计算 251
10.6 小结 253
参考文献 253
附录 255