本书根据集成电路芯片物理设计的流程，首先介绍集成电路物理设计中的基础数学知识、数据结构和文件格式，然后对物理设计中的各个阶段进行详细的论述，包括电路系统的划分、布图规划和布局算法、网格布线算法、总体布线算法、通道布线算法、布图领域最新的相关技术以及三维集成电路布图等算法。

本书覆盖面广，内容由浅入深，满足了当前集成电路向SoC、大规模和高性能发展的需求，既可作为高等院校计算机系和电子工程系从事VLSI设计和VLSI CAD的研究生的教材或教学参考书，也可作为从事VLSI CAD技术研究和开发人员的参考书。

  21世纪，世界全面进入信息时代。作为信息产业的支柱，超大规模集成电路（VeryLargeScale Integration, VLSI）的设计和制造在推动经济发展、社会产业结构和生活方式的变革中的作用日益增长。

从20世纪50年代开始，集成电路制造技术经历了从小规模集成（SSI) 、中规模集成（MSI）到大规模集成（LSI）阶段，乃至进入超大规模集成（VLSI）和甚大规模集成（Ultra Large Scale Integration,ULSI)阶段。尤其在过去的30年中，集成电路几乎完全遵循摩尔定律发展，即集成电路的集成度每隔18个月就翻一番。进入20世纪90年代以及21世纪以后，其设计规模由VLSI、ULSI向G规模集成（Giga-Scale Integration,GSI)的方向发展，于是，越来越多的功能，甚至是一个完整的系统都能够被集成到单个芯片之中。电子系统设计已从板上系统（System on Board,SoB)、多芯片模块（Multi-Chip Modules,MCM)进入到系统级芯片（System on Chip,SoC)时代。

集成电路的飞速发展体现出如下特点： 特征尺寸越来越小，芯片面积越来越大，单片上的晶体管数目越来越多，时钟频率越来越高，电源电压越来越低，布线层数越来越多，I/O引线越来越多。美国半导体工业协会SIA组织给出了1997年到2009年美国集成电路工艺发展趋势。随着集成度的提高，芯片内部晶体管数目越来越多，集成电路设计的复杂性越来越高，传统的手工设计和适应小规模的设计模式已经不再适用。为了设计复杂的大规模集成电路，人们越来越借助于电子设计自动化（EDA）工具。因此，越来越多的人致力于研究集成电路计算机辅助设计的算法，并且将这些算法集成到EDA工具中。

在集成电路的设计过程中，物理设计（或版图设计）是其中最费时的一步。它是VLSI设计过程中的一个重要环节，也是目前超大规模集成电路计算机辅助设计技术中最重要、最活跃的研究领域之一。它要把每个元件的电路表示转换成几何表示，同时，元件间的线网也被转换成几何连线图形。电路的几何表示叫版图，版图设计要符合与制造工艺有关的设计规则要求。版图设计可以有许多不同的模式，从对布局布线位置的限制和对布局模块的限制来分，可分为如下几种常用的模式： 积木块模式（Building Block Layout,BBL)、标准单元模式（Standard Cell)、门阵列模式（Gate Array)和门海模式（Sea-of-Gates)等。布图设计自动化指根据电路性能和工艺水平的要求，自动完成电路元件或功能单元在芯片上的安置，实现它们所需要的互连关系，并尽可能使得电路占有的面积最小或性能最优。布图设计的输入是电路的元件说明和网表（可用原理图说明），其输出是设计好的版图。

由于物理设计的复杂性，整个布图过程往往被分为划分（Partition) 、布图规划（Floorplanning) 、布局（Placement）和布线（Routing)等若干子步骤进行，每一步骤完成整个物理设计的一个子功能。物理设计阶段划分为上面几个子阶段，必然导致整个物理设计过程也是一个反复迭代求解的过程。随着工艺尺寸的不断减小和集成复杂度的增加，集成电路设计者面临全新的挑战，也给EDA研究人员提出了更高的要求。

本书对物理设计各个阶段的最新理论与算法进行了介绍，并将作者的研究成果融入到其中，可以使读者，特别是从事VLSI CAD领域的研究人员对集成电路物理设计领域的发展和研究趋势有一个全面的了解，从而为我国集成电路的发展做出应有的贡献。

作 者2009年5月

第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 BoxRouter194

8.5.3 MaizeRouter195

8.5.4 FastRoute195

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