并行算法的设计与分析PDF电子书下载

前言 1

第一章 导论 1

1.1 并行计算机的体系结构及分类 1

1.1.1 并行处理系统发展谱 1

1.1.2 并行计算机的分类 2

1.1.3 处理器互连网络 3

1.2 并行计算模型 9

1.2.1 SIMD互连网络模型 9

1.2.2 SIMD共享存储模型 10

1.2.3 MIMD共享存储模型 11

1.2.4 MIMD异步通信模型 11

1.2.5 专用并行计算模型 11

1.2.6 其他并行计算模型 12

1.3 并行算法的一般概念 13

1.3.1 并行算法的定义和术语 13

1.3.2 并行算法的复杂度 14

1.3.3 并行算法的表达 16

1.3.4 并行算法的WT表示 17

1.3.5 并行算法的同步和通信 20

习题 23

参考文献 24

第二章 并行算法的基本设计技术 26

2.1 平衡树方法 26

2.1.1 求取最大值 26

2.1.2 计算前缀和 27

2.2.1 表序问题的计算 30

2.2 倍增技术 30

2.2.2 求森林的根 31

2.3 分治策略 32

2.3.1 SIMD模型上分治算法的描述 32

2.3.2 SIMD共享存储模型上的FFT算法 33

2.4 划分原理 35

2.4.1 归并原理 35

2.4.2 划分算法与归并算法 36

2.5 流水线技术 37

2.5.1 一维阵列上的流水线归并排序原理 37

2.5.2 一维阵列上的流水线归并排序算法 37

2.6 加速级联策略 39

2.6.1 常数时间求最大值算法 39

2.6.2 双对数时间算法 40

2.6.3 加速级联算法 41

2.7 破对称技术 41

2.7.1 基本着色算法 41

2.7.2 快速3-着色算法 42

2.7.3 最优3-着色算法 43

习题 44

参考文献 46

第三章 比较器网络上的排序和选择算法 47

3.1 Batcher归并和排序网络 47

3.1.1 比较操作和［0，1］原理 47

3.1.2 奇偶归并网络 48

3.1.3 双调归并网络 49

3.1.4 Batcher排序网络 51

3.2.1 分组选择网络 53

3.2 (m，n)-选择网络 53

3.2.2 平衡分组选择网络 55

3.3 AKS排序网络 56

3.3.1 扩展图和划分网络 56

3.3.2 部分排序算法 59

3.3.3 完全排序算法 61

习题 65

参考文献 66

第四章 排序和选择的同步算法 67

4.1 Stone双调排序算法 67

4.1.1 均匀洗牌函数及其性质 67

4.1.2 Stone的观察及其计算模型 68

4.1.3 Stone的并行排序算法 69

4.2.1 处理器编号方式 71

4.2 Thompson和Kung双调排序算法 71

4.2.2 Thompson和Kung的观察 72

4.2.3 Thompson和Kung的双调排序算法 73

4.3 Preparata和Vuilemin双调排序算法 75

4.3.1 算法原理 75

4.3.2 流水线技术 76

4.3.3 算法描述 77

4.4 Akl并行k-选择算法 79

4.4.1 算法原理及物理描述 79

4.4.2 并行k-选择算法 79

4.4.3 算法分析 81

4.5.1 归并算法的基本原理 82

4.5.2 ？时Valiant归并 82

4.5 Valiant并行归并算法 82

4.5.3 ？时Valiant归并 83

4.6 Hirschberg并行桶排序算法 84

4.6.1 并行桶排序算法原理 84

4.6.2 并行桶排序算法描述 85

4.7 Preparat？并行枚举排序算法 86

4.7.1 枚举排序及其实现方法 86

4.7.2 排序算法的设计和分析 87

4.8 Cole并行归并排序算法 89

4.8.1 使用覆盖和位序的归并方法 89

4.8.2 Cole最佳排序算法 91

4.8.3 算法的正确性证明及分析 95

习题 98

参考文献 99

第五章 排序和选择的异步和分布式算法 100

5.1 MIMD-CREW模型上的异步枚举排序算法 100

5.1.1 算法原理和描述 100

5.1.2 算法举例和分析 101

5.2 MIMD-TC模型上的异步快排序算法 102

5.2.1 算法原理和描述 102

5.2.2 算法举例和分析 103

5.3 分布式k-选择算法 104

5.3.1 随机k-选择算法 104

5.3.2 确定k-选择算法 106

5.4 分布式求中值算法 107

5.4.1 分布式中值 107

5.4.2 分布式求中值算法 108

5.5 分布式定序算法 109

5.5.2 分布式定序算法 110

5.5.1 分布式计算模型 110

5.5.3 算法复杂度分析 112

5.6 分布式排序算法 113

5.6.1 模型和定义 113

5.6.2 静态排序算法 114

5.6.3 算法复杂度分析 114

习题 115

参考文献 116

第六章 并行搜索 118

6.1 单处理机上的搜索 118

6.1.1 单处理机上的顺序搜索 118

6.2.1 SIMD-EREW模型上的搜索 119

6.1.2 单处理机上有序表的对半搜索 119

6.2 SIMD共享存储模型上有序表的搜索 119

6.2.2 SIMD-CREW模型上的搜索 120

6.3 SIMD共享存储模型上随机序列的搜索 123

6.3.1 SIMD-SM模型上的随机序列搜索算法描述 123

6.3.2 SIMD-SM模型上的随机序列搜索算法分析 124

6.4 树连接的SIMD模型上随机序列的搜索 124

6.4.1 提问 124

6.4.2 维护 125

6.5 网孔连接的SIMD模型上随机序列的搜索 126

6.5.1 提问 127

6.6 MIMD共享存储模型上有序表的搜索 130

6.6.1 AVL树及其顺序插入算法 130

6.5.2 维护 130

6.6.2 Ellis并行搜素和插入算法 132

习题 134

参考文献 134

第七章 排列和组合 135

7.1 产生排列的顺序算法 135

7.1.1 排列和组合 135

7.1.2 产生词典序的排列算法 136

7.1.3 产生排列的计数方法 138

7.2 产生组合的顺序算法 140

7.2.1 产生词典序的组合算法 140

7.2.2 产生组合的计数方法 142

7.3.1 串行排列算法的并行化 144

7.3 产生排列的并行算法 144

7.3.2 自适应排列产生器 148

7.3.3 全排列产生器 149

7.4 产生组合的并行算法 150

7.4.1 非自适应组合产生器 151

7.4.2 自适应组合产生器 154

习题 155

参考文献 156

第八章 数据传输与选路 157

8.1 引言 157

8.2 贪心选路算法 158

8.2.1 一维阵列上的贪心选路算法 158

8.2.2 二维阵列上贪心选路算法的分析 159

8.2.3 蝶形网络上的贪心选路算法 161

8.3.1 二维阵列上的随机选路算法 162

8.3 随机和确定选路算法 162

8.3.2 超立方网络上的随机选路算法 164

8.3.3 二维阵列上的确定选路算法 165

8.4 数据的分布和集中 167

8.4.1 数据的分布 167

8.4.2 多到一选路算法 169

8.5 线路交换模式下的选路算法 171

习题 173

参考文献 174

第九章 并行串匹配 176

9.1 引言 176

9.1.1 基本概念和研究现状 176

9.1.2 基本定义和术语 177

9.2.1 SIMD-CREW模型上的非周期串的匹配算法 178

9.2 正文分析 178

9.2.2 SIMD-CREW模型上的周期串的匹配算法 181

9.3 模式预处理 183

9.8.1 求WIT表的一般方法 183

9.3.2 完全非周期串的WIT表求法 184

9.3.3 SIMD-CREW模型上任意串的WIT表求法 187

9.3.4 模式匹配算法的复杂度 188

9.4 后缀树上的串匹配 188

9.4.1 数字搜索树与后缀树 189

9.4.2 子串的编码 190

9.4.3 后缀树的构造 192

9.4.4 后缀树上的并行串匹配 195

习题 196

参考文献 198

第十章 表达式求值 199

10.1 构造表达式树 199

10.1.1 全括号表达式的表达式树 199

10.1.2 表达式树上的括号操作 200

10.1.3 计算match(i)的并行算法 201

10.2 填充游戏用于表达式求值 202

10.2.1 二叉树上的填充游戏 202

10.2.2 填充游戏用于算术表达式求值 203

10.3 最优的并行表达式求值算法 205

10.4 一般表达式求值算法 208

10.4.1 一般表达式与直线程序 208

10.4.3 仅有加法操作符的dag的计算 209

10.4.2 仅有乘法操作符的dag的计算 209

10.4.4 gbdag图和直线程序的计算 210

10.5 正则表达式到非确定自动机的最优并行转换 213

10.5.1 基本概念和术语 213

10.5.2 SIMD-CREW模型上的HU转换方法 215

习题 217

参考文献 218

第十一章 上下文无关语言的并行识别与语法分析 219

11.1 一般的上下文无关语言的并行识别 219

11.1.1 基本概念和术语 219

11.1.2 残缺部分语法树及其合成规则 221

11.1.3 共享存储模型上歧义性上下文无关语言并行识别算法 223

11.2 一般上下文无关语言的并行语法分析 226

11.2.1 基本概念和算法原理 226

11.2.2 SIMD-CREW模型上一般上下文无关语言的语法分析算法 227

11.3 括号语言的最优并行识别和语法分析 230

11.3.1 基本概念和算法原理 230

11.3.2 算法的具体实现 231

11.3.3 树的压缩技术 233

11.3.4 SIMD-CREW模型上括号语言的语法分析算法 236

习题 236

参考文献 237

第十二章 矩阵运算 238

12.1 矩阵转置 238

12.1.1 单处理机上的矩阵转置算法 238

12.1.2 SIMD-MC2模型上的矩阵转置 238

12.1.3 SIMD-PS模型上的矩阵转置 241

12.1.4 SIMD-EREW模型上的矩阵转置 242

12.2 矩阵相乘 243

12.2.1 单处理机上的矩阵乘法 243

12.2.2 SIMD-MC2模型上的矩阵乘法 244

12.2.3 SIMD-CC模型上的矩阵乘法 245

12.2.4 MIMD机器上的矩阵乘法 248

12.3 矩阵和向量相乘 251

12.3.1 树连接的机器上的矩阵和向量乘法 251

12.3.2 树网结构上的矩阵和向量乘法 253

12.4 心动阵列上的矩阵运算 253

12.4.1 二维六角形阵列上的矩阵乘法 253

12.4.2 二维六角形阵列上方阵的LU分解 255

12.4.3 六角形阵列上的方阵求逆 258

12.4.4 一维阵列上求解三角形线性系 259

习题 261

参考文献 264

第十三章 数值计算 265

13.1 n阶线性代数方程组的求解 265

13.1.1 SIMD-CREW模型上的Gauss-Jor？an算法 266

13.1.2 MIMD-CREW模型上的Gauss-Seidel算法 268

13.1.3 紧耦合多处理机系统中LU算法的效率分析 270

13.2 非线性方程的求根 272

13.2.1 SIMD-CREW模型上的求根算法 272

13.2.2 MIMD-CREW模型上的牛顿求根法 274

13.2.3 Fibonacci分点法异步求根算法 275

13.3 偏微分方程的求解 278

13.3.1 偏微分方程的差分数值求解法 278

13.3.2 SIMD-MC2模型上的PDE求解方法 279

13.4.1 对称方阵对角化方法 282

13.4 方阵的特征值与特征向量Jacobi求法 282

13.4.2 SIMD-CC模型上的求特征值算法 284

习题 286

参考文献 287

第十四章 FFT和卷积与滤波 289

14.1 快速富立叶变换 289

14.1.1 离散富立叶变换 289

14.1.2 顺序的FFT算法 290

14.1.3 FFT应用于多项式乘积 291

14.2 DFT直接并行计算法 292

14.2.1 SIMD模型上系数矩阵的计算 292

14.2.2 SIMD-MT模型上的DFT算法 292

14.3.1 SIMD-MC2模型上的FFT算法 295

14.3 并行FFT算法 295

14.3.2 SIMD-BF模型上的FFT算法 298

14.3.3 SIMD-PS模型上的FFT计算 299

14.3.4 SIMD-CC模型上的FFT计算 301

14.3.5 一维心动阵列上的DFT计算 305

14.4 心动阵列上的卷积与滤波计算 306

14.4.1 一维卷积在线性阵列上的实现 306

14.4.2 无限冲激滤波在线性阵列上的实现 308

14.4.3 中值滤波在线性阵列上的实现 309

习题 311

参考文献 312

15.1 图的并行搜索 313

15.1.1 算法原理 313

第十五章 图论算法 313

15.1.2 p-深度优先搜索 314

15.1.3 p-宽深优先搜索 314

15.1.4 p-宽度优先搜索 314

15.2 图的传递闭包 316

15.2.1 传递闭包问题 316

15.2.2 SIMD-CC模型上的传递闭包算法 316

15.2.3 二维心动阵列上的传递闭包算法 317

15.3 图的连通分量 320

15.3.1 SIMD-CC模型上的连通分量算法 320

15.3.2 SIMD-SM模型上的连通分量算法 322

15.3.3 SIMD-TC模型上的连通分量算法 324

15.3.4 SIMD-MT模型上的连通分量算法 325

15.4 图的最短路径 327

15.4.1 所有顶点对间的最短路径算法 328

15.4.2 MIMD-SM模型上单源最短路径算法 330

15.5 图的最小生成树 333

15.5.1 SIMD-EREW模型上最小生成树算法 333

15.5.2 MIMD-SM模型上最小生成树算法 336

15.5.3 树机模型上最小生成树算法 339

15.6 图的着色 342

15.6.1 二分图的边着色算法 342

15.6.2 外平面图最优顶点着色算法 343

15.6.3 外平面图最优边着色算法 349

15.6.4 Halin图最优边着色算法 351

习题 355

参考文献 358

第十六章 图象分析和计算几何 360

16.1 分量标定 360

16.1.1 二维阵列上分量标定平易算法 360

16.1.2 二维阵列上Levialdi分量标定算法 362

16.1.3 二维阵列上递归的分量标定算法 364

16.2 Hough变换 365

16.2.1 二维图象的Hough变换 365

16.2.2 二维阵列上象素Hough变换的计算 366

16.3 近邻问题 367

16.4 包含问题 368

16.4.1 判断点在多边形中 369

16.4.2 判断点在平面细图中 371

16.5 相交问题 373

16.6.1 求凸壳问题的下界 374

16.6 构造问题 374

16.6.2 顺序求凸壳算法 375

16.6.3 SIMD-MT模型上求凸壳算法 376

16.6.4 SIMD-EREW模型上求凸壳算法 378

习题 383

参考文献 384

第十七章 组合搜索 385

17.1 基于分治法的与树搜索 385

17.1.1 搜素树 385

17.1.2 SIMD模型上的与树搜索 386

17.2 基于分枝限界法的或树搜索 386

17.2.1 8-谜问题 387

17.2.2 串行分枝限界算法 388

17.2.3 用串行分枝限界法求TSP 389

17.2.4 并行TSP算法 393

17.3 串行的α-β搜索算法 394

17.3.1 博弈树与最大最小原理 394

17.3.2 串行的α-β算法 395

17.4 树机上的并行搜索算法 396

17.4.1 树分裂算法 397

17.4.2 主变量分裂算法 398

17.5 MIMD模型上α-β搜索算法 400

17.5.1 基本设计原理 400

17.5.2 算法的形式描述 401

习题 401

17.5.3 算法讨论和分析 405

参考文献 408

第十八章 随机算法 409

18.1 引言 409

18.1.1 概率论的基本知识 409

18.1.2 随机算法的模型及其度量 412

18.2 部分独立集 413

18.2.1 有向环图 414

18.2.2 平面图 415

18.3 三角形平面细图中点的位置 416

18.3.1 细图层次 417

18.3.2 细图层次的构造算法 417

18.4 模式匹配 419

18.4.1 指纹函数 420

18.4.2 串匹配 423

18.4.3 二维数组的匹配 424

18.5 多项式恒等的验证 425

18.5.1 基本技术 425

18.5.2 矩阵乘积的验证 426

18.6 排序 427

18.6.1 随机采样及随机快排序 427

18.6.2 并行随机快排序算法 428

18.6.3 快速随机并行排序算法 430

18.7 最大匹配和完备匹配 432

18.7.1 图的代数性质 433

18.7.2 测试完备匹配存在的随机算法 435

习题 438

参考文献 439

19.1.1 VLSI电路模型 441

19.1 VLSI电路模型和计算模型 441

第十九章 VLSI计算理论 441

19.1.2 VLSI计算模型 443

19.2 VLSI面-时下界理论 444

19.2.1 几种基本的下界论点 444

19.2.2 信息流和穿越序列 446

19.3 典型计算图的结构布局法 448

19.3.1 树的布局 448

19.3.2 网孔和树网的布局 449

19.3.3 洗牌交换网的布局 449

19.3.4 立方环的布局 452

19.4 典型计算图的布局下界 453

19.4.1 树的布局下界 453

19.3.5 蝶形网的布局 453

19.4.2 树网的布局下界 455

19.4.3 洗牌交换网的布局下界 458

19.4.4 蝶形网的布局下界 458

19.5 分治布局法 459

19.5.1 分离集 459

19.5.2 强分离集 461

19.5.3 通道生成 462

19.5.4 分治布局法 463

19.6 VLSI布局理论 466

19.6.1 平面图的分离定理 466

19.6.2 图的交叉点数 467

19.6.3 布局下界定理 468

习题 468

参考文献 469

第二十章 模型与下界 471

20.1 不同PRAM模型的相互模拟 471

20.1.1 在PRAM-EREW上模拟PPRAM-CRCW 471

20.1.2 在CPRAM-CRCW上模拟PPRAM-CRCW 472

20.1.3 在APRAM-CRCW上模拟PPRAM-CRCW 474

20.2 PRAM-CREW的下界 475

20.2.1 理想的PRAM模型 475

20.2.2 形式描述 475

20.2.3 特定问题的下界 478

20.3 PRAM-EREW的下界 478

20.3.1 工具和方法 478

20.3.2 主要下界 479

20.4 PRAM-CRCW的下界 480

20.4.1 PRAM-CRCW与无界扇入电路 481

20.4.2 无界扇入电路的下界 487

20.5 P-完全导论 490

20.5.1 问题的可并行化 490

20.5.2 NC类和RNC类 492

20.5.3 P-完全问题范例 496

20.5.4 小结 502

习题 503

参考文献 504

附录A 复杂度表示及其符号 506

A.1 大-O及其运算 506

A.2 大-Ω和大-Θ 506

A.3 小-O和小-ω 507

附录B 算法复杂界一览表 508