《超大规模集成电路布图理论与算法》求取 ⇩

第一章超大规模集成电路布图问题、布图方法及版图设计自动化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