超大规模集成电路布图理论与算法PDF电子书下载

第一章 超大规模集成电路布图问题、布图方法及版图设计自动化 1

1.1 VLSI设计流程 2

1.2 布图设计过程 4

1.3 芯片费用和电性能的估计 6

1.4 布图模式 7

1.4.1 全定制设计模式 8

1.4.2 标准单元设计模式 11

1.4.3 门阵列设计模式 13

1.4.4 门海设计模式 15

1.4.5 现场可编程门阵列 16

1.4.6 不同设计方法的比较 18

1.5 系统封装的物理设计 19

1.5.2 多芯片模块 20

1.5.1 印制电路板 20

1.5.3 圆片规模集成 21

1.5.4 各种封装方法的比较 21

参考文献 22

第二章 VLSI器件的设计和制造以及布图对象的描述 23

2.1 集成电路制造工艺 23

2.2 设计规则 25

2.3 基本器件的版图实例 27

2.3.1 非门 27

2.3.2 与非门 28

2.4 工艺制造中的其它因素 28

2.4.2 寄生效应 29

2.4.1 等比例缩小 29

2.4.3 延迟计算 30

2.4.4 噪声和串扰 31

2.4.5 功耗 32

2.5 集成电路版图的几何表示 32

2.5.1 CIF格式 33

2.5.2 EDIF格式 35

2.6 单元的拓扑描述和网表描述 40

参考文献 42

第三章 VLSI布图的数学基础及数据结构 43

3.1 图的基本术语及基本数据结构 43

3.1.1 基本术语 43

3.1.2 图的基本数据结构 45

3.2 算法及算法复杂性 47

3.2.1 算法问题及算法复杂性 47

3.2.2 几种求解NP-困难问题的方法 49

3.3 基本算法 53

3.3.1 图论算法 53

3.3.2 计算几何算法 73

3.3.3 基于运筹学的算法 75

3.4 基本数据结构 90

3.4.1 版图数据的基本操作 90

3.4.2 链表结构 91

3.4.3 基于Bin的结构 93

3.4.4 邻接指针 94

3.4.5 角勾链 95

3.4.6 四叉树 100

3.4.7 各种版图数据结构的比较 101

3.4.8 自动布图中模块和网表的数据结构 102

3.4.9 树的数据结构 105

参考文献 111

第四章 布局与布图规划 113

4.1 布局中的线长估计 114

4.1.1 最小斯坦纳树 115

4.1.2 最小生成树 115

4.1.3 最小链 115

4.1.6 边界框 116

4.1.7 半周长 116

4.1.4 源到漏端的最小连接 116

4.1.5 完全图 116

4.1.8 二次线长 117

4.1.9 单树干斯坦纳树 117

4.2 布局的目标函数 118

4.2.1 基于连线总长的目标 118

4.2.2 基于割线的目标 119

4.2.3 基于最大密度的目标 119

4.2.4 复合目标函数 120

4.2.5 实例与比较 120

4.3 初始布局 121

4.3.1 单元的安置 122

4.3.2 基于联结度的布局方法 125

4.3.3 基于结群的布局方法 128

4.4 改善布局 134

4.4.1 改善布局的目标函数 135

4.4.2 基于对交换的迭代改善 136

4.4.3 基于最小割的交换 139

4.5 BBL模式下的布局改善 143

4.5.1 布局结果的图表示 143

4.5.2 迭代改善 146

4.6 基于数学规划方法的布局迭代改善 147

4.6.1 问题定义 148

4.6.2 求解方法 150

4.6.3 算法分析 152

4.6.4 划分策略的进一步讨论 154

4.6.5 最终布局 157

4.7 基于模拟退火方法的布局算法 159

4.8 布图规划 161

4.8.1 布图规划、布局与分级设计 161

4.8.2 布图规划问题定义 163

4.8.3 布图规划过程 164

4.8.4 布图规划算法 165

参考文献 180

第五章 线网布线 182

5.1 迷宫算法 183

5.1.1 基本的迷宫算法 184

5.1.2 迷宫算法的改进 188

5.1.3 迷宫算法的比较 191

5.1.4 迷宫算法中提高布线效率的方法 192

5.1.5 多端线网布线 197

5.1.6 多层布线 198

5.2 线探索法 198

5.3 布线顺序的影响及其处理 201

5.3.1 布线顺序的影响 201

5.3.2 布线顺序的处理方法 203

5.4 整体布线 204

参考文献 207

6.1.1 总体布线图 209

第六章 总体布线 209

6.1 总体布线问题 209

6.1.2 总体布线问题定义 211

6.2 总体布线算法的分类 213

6.2.1 串行算法 215

6.2.2 并行算法 216

6.3 总体布线图上的斯坦纳树算法 216

6.3.1 基于最短路径的算法 217

6.3.2 基于最小代价生成树的算法 217

6.3.3 基于可分离性的算法 219

6.3.4 基于非矩形边斯坦纳树的算法 222

6.3.5 Dreyfus-Wagner算法 223

6.3.6 最小化最大权重边的斯坦纳树算法 225

6.4 总体布线算法 227

6.4.1 串行布线和拆线重布算法 227

6.4.2 基于加权的斯坦纳树算法 229

6.4.3 基于整数规划的方法 230

6.4.4 基于网络流的总体布线算法 234

6.4.5 基于拥挤度分析的并行层次迭代布线算法 243

参考文献 247

第七章 通道布线 250

7.1 通道布线问题 251

7.2 通道布线的定义和约束关系 253

7.2.1 通道布线 253

7.2.2 通道布线中的水平和垂直约束 254

7.3 常见的几种通道布线算法 257

7.3.1 左边算法 258

7.3.2 狗腿算法 259

7.3.3 合并算法 260

7.3.4 贪婪算法 264

7.3.5 层次式通道布线算法 266

7.3.6 双层布线算法的比较 269

7.4 开关盒布线问题 270

7.4.1 定向布线 271

7.4.2 最终布线 274

7.5 多层布线 276

7.5.1 三层布线 276

7.5.2 多层布线算法 279

7.6 其它布线问题 280

7.6.1 L形通道布线 280

7.6.2 单元上布线 281

参考文献 290

第八章 其它布图问题 293

8.1 通孔最少化算法 293

8.1.1 通孔最少化一般图模型 293

8.1.2 通孔秩及多度通孔 296

8.1.3 秩边权和图模型边权计算 298

8.1.4 通孔最少化算法 298

8.2.1 线长优化的一般方法 300

8.2 统一通孔最少化和线长最小化层分配算法 300

8.2.2 最少通孔和最小线长分层的无向图表示 301

8.2.3 若干工程实际中要考虑的问题 302

8.2.4 算法及实验结果 303

8.3 走线道分配算法 305

8.3.1 总体布线树的映射 307

8.3.2 多行走线道分配 308

8.3.3 单行走线道分配 312

8.4 过点分配算法 317

8.4.1 问题描述 318

8.4.2 线网分类 319

8.4.3 费用函数的构造 321

8.4.4 过点分配算法 323

参考文献 324

9.1 时延和功耗双重驱动布局算法 326

第九章 高性能布图算法 326

9.1.1 延迟模型 328

9.1.2 问题定义 329

9.1.3 求解拉格朗日问题 331

9.1.4 功耗和时延双重驱动布局 336

9.2 时延驱动斯坦纳树算法 336

9.2.1 基于Dreyfus-Wagner的斯坦纳树算法 337

9.2.2 构造性力指向斯坦纳树算法 341

9.3 时延驱动总体布线算法 343

9.3.1 基于线网时延驱动总体布线算法 344

9.3.2 基于关键路径时延驱动总体布线算法 345

9.4.1 时钟系统及其布线问题 348

9.4 同时到达的时钟线布线技术 348

9.4.2 时钟树的时延计算方法 351

9.4.3 时钟布线算法 353

9.5 减小关键路径延迟的回路布线法 357

9.5.1 互连线延迟模型 358

9.5.2 RC网孔电路延迟计算 360

9.5.3 回路布线延迟分析 360

9.5.4 实验结果 365

9.6 电源网与地网布线 367

9.6.1 电源／地线网的布线 367

9.6.2 约束条件及目标函数的规划 369

参考文献 373