数字系统并行CAD技术PDF电子书下载

第1章 绪论 1

1.1 引言 1

1.2 数字系统并行CAD的研究意义 2

1.3 数字系统并行CAD研究发展概况 3

1.3.1 并行CAD专用机的研究发展 3

1.3.2 并行CAD算法的研究发展 4

1.3.3 并行CAD开发环境的研究发展 4

1.4 数字系统设计方法论 5

1.4.1 设计描述 5

1.4.2 设计流程 6

1.4.3 VLSI系统设计方法 7

1.5 并行体系结构基本知识 9

1.5.1 共享主存MIMD体系结构 10

1.5.2 分布主存MIMD体系结构 10

1.5.3 SIMD并行体系结构 10

1.5.4 工作站集群体系结构 11

1.6 并行程序设计基本知识 11

1.6.1 数据并行与功能并行 11

1.6.2 细粒度并行与粗粒度并行 12

1.6.3 SIMD和MIMD程序设计模型 12

1.6.4 共享主存MIMD程序设计基本知识 13

1.6.5 分布主存MIMD程序设计基本知识 14

1.6.6 SIMD程序设计基本知识 16

1.7 并行算法基本知识 16

1.7.1 加速比 17

1.7.2 Amdehl定律 17

1.7.3 负载平衡和调度 18

第2章 并行逻辑综合 20

2.1 引言 20

2.2 二级逻辑综合 20

2.2.1 二级逻辑极小化的优化目标 20

2.2.2 ESPRESSO极小化算法 21

2.3 共享主存的并行ESPRESSO算法 23

2.3.1 COMPLEMENT(F，D)求反过程的并行化 23

2.3.2 并行立方扩展 25

2.3.3 REDUCE过程的并行化 26

2.3.4 冗余项去除过程IRREDUNDANT()的并行化 27

2.3.5 并行ESPRESSO算法 27

2.4 多级逻辑综合的任务及主要方法 28

2.5 基于逻辑结构划分的并行综合方式 29

2.5.1 子逻辑结构划分原则 30

2.5.2 基于有向图的划分方式 31

2.5.3 基于无关项集合的划分 32

2.5.4 基于负载平衡的划分方式 32

2.5.5 分布主存的基于划分的并行综合算法 33

2.6 多级逻辑综合算法的并行化 35

2.6.1 基本定义 35

2.6.2 MIS综合算法的逻辑变换过程 36

2.6.3 MIS综合算法的并行比 37

2.7 小结 54

第3章 并行逻辑模拟 56

3.1 概述 56

3.2 功能并行模拟 57

3.3 数据并行模拟 57

3.4 结构划分映射方法 58

3.4.1 概述 58

3.4.2 利用预模拟信息的电路划分方法 59

3.5 并行编译模拟方法 61

3.6 同步事件驱动并行模拟方法 61

3.6.1 概述 61

3.6.2 共享主存MIMD并行同步事件驱动模拟算法 62

3.7 异步事件驱动并行模拟方法 64

3.7.1 概述 64

3.7.2 保守的异步并行模拟算法 68

3.7.3 分布主存优化的异步并行模拟算法 69

3.7.4 共享主存优化的异步并行模拟算法 71

3.8 结构并行模拟方法分析 72

3.9 VHDL并行模拟 74

3.9.1 概述 74

3.9.2 分布主存MIMD并行VHDL模拟算法 74

3.9.3 VHDL并行模拟器QuestⅡ 75

第4章 并行电路模拟 78

4.1 引言 78

4.2 电路模拟方法 78

4.2.1 电路模拟问题 78

4.2.2 电路模拟的直接求解法 79

4.3 并行模型求解方法 82

4.3.1 概述 82

4.3.2 共享主存MIMD并行算法 83

4.3.3 分布主存MIMD并行算法 85

4.4 基于行划分的线性方程并行求解方法 86

4.4.1 概述 86

4.4.2 共享主存MIMD并行算法 86

4.4.3 分布主存MIMD并行算法 88

4.5 非线性松弛并行电路模拟方法 90

4.5.1 概述 90

4.5.2 共享主存MIMD并行算法 91

4.5.3 分布主存MIMD并行算法 93

4.6 波形松弛并行电路模拟方法 95

4.6.1 概述 95

4.6.2 共享主存MIMD并行算法 97

4.6.3 分布主存MIMD并行算法 98

4.7 小结 100

第5章 并行测试生成 102

5.1 串行测试生成算法 102

5.1.1 组合电路串行测试生成算法 102

5.1.2 时序电路串行测试生成算法 107

5.1.3 降低自动测试生成(ATPG)时间复杂性的对策 111

5.2 并行测试生成理论概述 113

5.2.1 基于故障诊断目标划分的并行测试生成方法 113

5.2.2 基于ATPG过程分解的并行测试生成方法 115

5.2.3 ATPG算法并行化的困难 117

5.3 故障并行测试生成算法 119

5.3.1 关于故障并行的加速比 119

5.3.2 三种故障划分方法 120

5.3.3 实验结果及结论 123

5.4 电路并行测试生成算法 124

5.4.1 适于电路输出扇入锥划分的递归最小二分法 124

5.4.2 基于大功能块划分的并行算法 128

5.5 搜索空间并行ATPG算法 130

5.5.1 基于PODEM算法的搜索空间并行算法 130

5.5.2 基于G-F二值算法的搜索空间并行 131

第6章 并行故障模拟 134

6.1 经典故障模拟方法概述 134

6.1.1 字并行故障模拟 134

6.1.2 演绎故障模拟 136

6.1.3 同时故障模拟 137

6.2 经典故障模拟方法的可并行性分析 138

6.2.1 可能的基本并行模式 138

6.2.2 ATPG与FS紧耦合系统 138

6.2.3 ATPG与FS松耦合系统 139

6.3 基于故障并行的故障模拟算法 139

6.3.1 故障分类和划分方法 139

6.3.2 分布主存和共享主存MIMD并行故障模拟算法 140

6.4 测试模式并行的故障模拟算法 141

6.4.1 组合电路的测试模式并行 141

6.4.2 时序电路的测试模式并行 143

6.5 电路并行的故障模拟算法 143

6.5.1 概述 143

6.5.2 分布主存MIMD并行算法 143

6.5.3 共享主存MIMD并行算法 145

6.5.4 输出锥并行的故障模拟方法 146

6.5.5 大功能块并行的故障模拟方法 146

6.6 结论与展望 147

6.6.1 关于测试生成的并行化 147

6.6.2 关于故障模拟的并行化 148

6.6.3 展望 148

第7章 并行布局 150

7.1 概述 150

7.1.1 布局问题 150

7.1.2 串行布局方法 151

7.1.3 布局代价函数 151

7.1.4 定时驱动布局 152

7.1.5 并行布局方法 153

7.2 模拟退火并行布局算法 155

7.2.1 模拟退火法布局原理 155

7.2.2 模拟退火布局算法的并行方法 156

7.2.3 共享主存MIMD并行模拟退火布局算法 157

7.2.4 分布主存MIMD并行模拟退火布局算法 162

7.3 遗传并行布局算法 164

7.3.1 遗传布局原理 164

7.3.2 分布主存MIMD并行遗传布局算法 165

7.3.3 共享主存MIMD并行遗传布局算法 166

7.4 并行分级布局算法 167

7.4.1 分级布局原理 167

7.4.2 共享主存MIMD并行分级布局算法 167

7.4.3 分布主存MIMD并行分级布局算法 169

7.5 并行版图规划 170

7.5.1 概述 170

7.5.2 模拟退火并行版图规划算法 171

7.5.3 遗传并行版图规划算法 173

7.5.4 分枝限界并行版图规划算法 175

7.6 小结 178

第8章 并行布线与并行版图验证 179

8.1 引言 179

8.1.1 两点间布线 179

8.1.2 总体布线 179

8.1.3 通道布线 180

8.1.4 版图验证 181

8.2 并行迷路布线算法 181

8.2.1 基本思想 181

8.2.2 分布主存的MIMD并行算法 182

8.2.3 共享主存MIMD并行算法 184

8.3 通道并行布线 185

8.3.1 贪婪法 185

8.3.2 共享主存MIMD并行算法 185

8.3.3 共享主存MIMD开关盒并行布线迭代改善法 187

8.4 总体布线并行迭代法 188

8.4.1 基本思想 188

8.4.2 共享主存MIMD并行算法 189

8.4.3 分布主存MIMD并行算法 191

8.5 几何设计规则检验 192

8.5.1 基本算法 192

8.5.2 分布主存MIMD并行算法 193

8.5.3 共享主存MIMD并行算法 194

8.6 并行网表提取 194

8.6.1 问题描述 194

8.6.2 分布主存MIMD并行算法 195

8.6.3 共享主存MIMD并行算法 196

8.7 并行参数提取 197

8.7.1 问题描述 197

8.7.2 分布主存MIMD并行算法 198

8.7.3 共享主存MIMD并行算法 201

8.8 总结与展望 201

8.8.1 并行布线策略 202

8.8.2 并行版图验证策略 202

8.8.3 今后的研究方向 203

第9章 并行CAD研究发展方向 204

9.1 数字系统并行CAD技术发展的主要问题 204

9.2 并行CAD算法的可移植性研究进展 205

9.2.1 PVM和MPI 205

9.2.2 Proper CAD系统 206

9.2.3 几种方法的比较 207

9.3 并行CAD未来发展 208

参考文献 209