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

第一章 并行算法基础 1

1.1 并行算法的硬件基础 2

1.1.1 当代并行计算机体系结构 2

1.1.2 并行计算机互连网络 9

1.2 并行计算模型 16

1.2.1 SIMD同步并行计算模型 17

1.2.2 MIMD异步并行计算模型 19

1.2.3 其他并行计算模型 29

1.3 并行算法编程模型 31

1.3.1 数据并行模型 31

1.3.2 消息传递模型 33

1.3.3 共享变量模型 34

1.4.1 并行算法的定义和分类 36

1.4 并行算法的一般概念 36

1.4.2 并行算法的表达 37

1.4.3 并行算法的复杂性度量 38

1.4.4 并行算法的WT表示 41

1.4.5 并行算法的同步和通信 44

习题 47

参考文献 51

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

2.1 平衡树方法 55

2.1.1 求取最大值 55

2.1.2 计算前缀和 55

2.2 倍增技术 59

2.2.1 表序问题的计算 60

2.2.2 求森林的根 61

2.3 分治策略 62

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

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

2.4 划分原理 66

2.4.1 归并原理 66

2.4.2 划分算法与归并算法 66

2.5 流水线技术 68

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

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

2.6 加速级联策略 70

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

2.6.2 双对数时间算法 71

2.6.3 加速级联算法 72

2.7 破对称技术 73

2.7.1 基本着色算法 73

2.7.2 快速3-着色算法 75

2.7.3 最优3-着色算法 75

习题 77

参考文献 79

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

3.1 Batcher归并和排序网络 81

3.1.1 比较操作和[0，1]原理 81

3.1.2 奇偶归并网络 82

3.1.3 双调归并网络 84

3.1.4 Batcher排序网络 85

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

3.2.1 分组选择网络 88

3.2.2 平衡分组选择网络 91

3.3 AKS排序网络 92

3.3.1 扩展图和划分网络 92

3.3.2 部分排序算法 95

3.3.3 完全排序算法 98

习题 103

参考文献 104

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

4.1 Stone双调排序算法 107

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

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

4.1.3 Stone的并行排序算法 110

4.2.1 处理器编号方式 112

4.2 Thompson和Kung双调排序算法 112

4.2.2 Thompson和Kung的观察 113

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

4.3 Preparata和Vuilemin双调排序算法 117

4.3.1 算法原理 117

4.3.2 流水线技术 119

4.3.3 算法描述 120

4.4 Akl并行k-选择算法 121

4.4.1 算法原理及物理描述 122

4.4.2 并行k-选择算法 122

4.4.3 算法分析 124

4.5 Valiant并行归并算法 125

4.5.1 归并算法的基本原理 125

4.5.2 k=？时Valiant归并 126

4.5.3 k=？时Valiant归并 127

4.6 Hirschberg并行桶排序算法 128

4.6.1 并行桶排序算法原理 128

4.6.2 并行桶排序算法描述 129

4.7 Preparata并行枚举排序算法 130

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

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

4.8 Cole并行归并排序算法 134

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

4.8.2 Cole最佳排序算法 136

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

习题 144

参考文献 146

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

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

5.1.1 算法原理和描述 148

5.1.2 算法举例和分析 149

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

5.2.1 算法原理和描述 150

5.2.2 算法举例和分析 151

5.3 分布式k-选择算法 153

5.3.1 随机k-选择算法 153

5.3.2 确定k-选择算法 155

5.4 分布式求中值算法 157

5.4.1 分布式中值 157

5.4.2 分布式求中值算法 158

5.5.1 分布式计算模型 159

5.5 分布式定序算法 159

5.5.2 分布式定序算法 160

5.5.3 算法复杂度分析 162

5.6 分布式排序算法 163

5.6.1 模型和定义 163

5.6.2 静态排序算法 164

5.6.3 算法复杂度分析 165

习题 166

参考文献 167

第六章 并行搜索 169

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

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

6.1 单处理机上的搜索 170

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

6.2.1 SIMD-EREW模型上的搜索 171

6.2.2 SIMD-CREW模型上的搜索 172

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

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

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

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

6.4.1 提问 177

6.4.2 维护 178

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

6.5.1 提问 180

6.5.2 维护 183

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

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

6.6.2 Ellis并行搜索和插入算法 186

习题 189

参考文献 190

第七章 排列和组合 191

7.1 产生排列的顺序算法 192

7.1.1 排列和组合 192

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

7.1.3 产生排列的计数方法 195

7.2 产生组合的顺序算法 198

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

7.2.2 产生组合的计数方法 199

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

7.3 产生排列的并行算法 202

7.3.2 自适应排列产生器 207

7.3.3 全排列产生器 208

7.4 产生组合的并行算法 210

7.4.1 非自适应组合产生器 210

7.4.2 自适应组合产生器 212

习题 215

参考文献 216

第八章 数据传输与选路 217

8.1 引言 218

8.2 贪心选路算法 219

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

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

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

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

8.3 随机和确定选路算法 225

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

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

8.4 数据的分布和集中 230

8.4.1 数据的分布 230

8.4.2 多到一选路算法 233

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

习题 238

参考文献 240

第九章 并行串匹配 241

9.1 引言 242

9.1.1 基本概念和研究现状 242

9.1.2 基本定义和术语 243

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

9.2 正文分析 244

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

9.3 模式预处理 250

9.3.1 求WIT表的一般方法 250

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

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

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

9.4 后缀树上的串匹配 256

9.4.1 数字搜索树与后缀树 256

9.4.2 子串的编码 258

9.4.3 后缀树的构造 261

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

习题 266

参考文献 268

第十章 表达式求值 270

10.1 构造表达式树 271

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

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

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

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

10.2.1 二叉树上的填充游戏 275

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

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

10.4 一般表达式求值算法 282

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

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

习题 284

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

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

10.5.1 基本概念和术语 289

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

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

参考文献 295

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

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

11.1.1 基本概念和术语 297

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

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

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

11.2.1 基本概念和算法原理 304

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

11.3.1 基本概念和算法原理 310

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

11.3.2 算法的具体实现 311

11.3.3 树的压缩技术 313

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

习题 317

参考文献 318

第十二章 矩阵运算 319

12.1 矩阵转置 320

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

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

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

12.2 矩阵相乘 325

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

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

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

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

12.2.4 MIMD机器上的矩阵乘法 331

12.3 矩阵和向量相乘 335

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

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

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

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

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

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

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

习题 347

参考文献 350

第十三章 数值计算 351

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

13.1.1 SIMD-CREW模型上的Gauss-Jordan算法 352

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

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

13.2 非线性方程的求根 359

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

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

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

13.3 偏微分方程的求解 367

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

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

13.4.1 对称方阵对角化方法 372

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

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

习题 377

参考文献 378

第十四章 FFI和卷积与滤波 380

14.1 快速傅里叶变换 381

14.1.1 离散傅里叶变换 381

14.1.2 顺序的FFT算法 382

14.1.3 FFT应用于多项式乘积 382

14.2 DFT直接并行计算法 384

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

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

14.3 并行FFT算法 388

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

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

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

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

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

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

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

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

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

习题 407

参考文献 409

第十五章 图论算法 410

15.1.1 算法原理 411

15.1.2 p-深度优先搜索 411

15.1 图的并行搜索 411

15.1.3 p-宽深优先搜索 412

15.1.4 p-宽度优先搜索 412

15.2 图的传递闭包 414

15.2.1 传递闭包问题 414

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

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

15.3 图的连通分量 419

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

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

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

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

15.4 图的最短路径 428

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

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

15.5 图的最小生成树 434

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

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

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

15.6 图的着色 444

15.6.1 二分图的边着色算法 445

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

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

15.6.4 Halin图最优边着色算法 457

习题 461

参考文献 464

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

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

16.1 分量标定 467

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

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

16.2 Hough变换 473

16.2.1 二维图象的Hough变换 473

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

16.3 近邻问题 475

16.4 包含问题 476

16.4.1 判断点在多边形中 477

16.4.2 判断点在平面细图中 480

16.5 相交问题 482

16.6 构造问题 483

16.6.1 求凸壳问题的下界 484

16.6.2 顺序求凸壳算法 484

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

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

习题 495

参考文献 496

第十七章 组合搜索 497

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

17.1.1 搜索树 498

17.1.2 SIMD模型上的与树搜索 499

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

17.2.1 8-谜问题 500

17.2.2 串行分枝限界算法 501

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

17.2.4 并行TSP算法 507

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

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

17.3.2 串行的α-β算法 510

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

17.4.1 树分裂算法 512

17.4.2 主变量分裂算法 514

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

17.5.1 基本设计原理 516

17.5.2 算法的形式描述 518

17.5.3 算法讨论和分析 521

习题 523

参考文献 524

第十八章 随机算法 526

18.1.1 概率论的基本知识 527

18.1 引言 527

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

18.1.3 随机算法的设计方法 531

18.2 部分独立集 533

18.2.1 有向环图 534

18.2.2 平面图 535

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

18.3.1 细图层次 538

18.3.2 细图层次的构造算法 538

18.4 模式匹配 540

18.4.1 指纹函数 541

18.4.2 串匹配 544

18.4.3 二维数组的匹配 546

18.5 多项式恒等的验证 547

18.5.1 基本技术 548

18.5.2 矩阵乘积的验证 549

18.6 排序 550

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

18.6.2 并行随机快排序算法 551

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

18.7 最大匹配和完备匹配 556

18.7.1 图的代数性质 557

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

习题 563

参考文献 564

第十九章 VLSI计算理论 567

19.1.1 VLSI电路模型 568

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

19.1.2 VLSI计算模型 570

19.2 VLSI面-时下界理论 572

19.2.1 几种基本的下界论点 572

19.2.2 信息流和穿越序列 574

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

19.3.1 树的布局 576

19.3.2 网孔和树网的布局 578

19.3.3 洗牌交换网的布局 578

19.3.4 立方环的布局 581

19.3.5 蝶形网的布局 583

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

19.4.1 树的布局下界 584

19.4.2 树网的布局下界 585

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

19.4.4 蝶形网的布局下界 589

19.5 分治布局法 590

19.5.1 分离集 590

19.5.2 强分离集 593

19.5.3 通道生成 595

19.5.4 分治布局法 596

19.6 VLSI布局理论 599

19.6.1 平面图的分离定理 599

19.6.2 图的交叉点数 600

19.6.3 布局下界定理 601

习题 603

参考文献 604

第二十章 模型与下界 605

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

20,1.1 在PRAM-EREW上模拟PPRAM-CRCW 606

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

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

20.2 PRAM-CREW的下界 610

20.2.1 理想的PRAM模型 610

20.2.2 形式描述 611

20.2.3 特定问题的下界 614

20.3 PRAM-EREW的下界 614

20.3.1 工具和方法 614

20.3.2 主要下界 615

20.4 PRAM-CRCW的下界 617

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

20.4.2 无界扇入电路的下界 625

20.5 P-完全导论 629

20.5.1 问题的可并行化 629

20.5.2 NC类和RNC类 632

20.5.3 P-完全问题范例 636

20.5.4 小结 644

习题 645

参考文献 646

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

A.1 大-O及其运算 648

A.2 大-Ω和大-Θ 649

A.3 小-o和小-ω 649

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

附录C 索引 660