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

第一章　绪论 1

1.1 引言 2

1.2　并行算法的硬件基础 3

1.2.1　并行计算机体系结构 3

1.2.2　并行计算机互连网络 11

1.2.3　并行计算机存储组织 22

1.3　并行计算模型 24

1.3.1　模型的定义、功能和分类 25

1.3.2　共享存储模型 25

1.3.3　分布存储模型 28

1.3.4　层次存储模型 34

1.3.5　其他并行计算模型 37

1.4　并行算法的基础知识 39

1.4.1　并行算法的定义 40

1.4.2　并行算法的表达 41

1.4.3　并行算法的复杂性 42

1.4.4　并行算法的同步和通信 45

1.5　并行算法的性能分析 47

1.5.1　算法的执行速度 47

1.5.2　算法使用的处理器数 48

1.5.3　并行算法的WT表示 50

1.5.4　并行算法的通信成本 53

习题 54

参考文献 59

第二章　设计技术 62

2.1　平衡树方法 63

2.1.1　求取最大值 63

2.1.2　计算前缀和 63

2.2　倍增技术 67

2.2.1　表序问题的计算 68

2.2.2　求森林的根 69

2.3　分治策略 70

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

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

2.4　划分原理 73

2.4.1　归并原理 74

2.4.2　划分算法与归并算法 74

2.5　流水线技术 75

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

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

2.6　加速级联策略 78

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

2.6.2　双对数时间算法 79

2.6.3　加速级联算法 80

2.7　破对称技术 81

2.7.1　基本着色算法 81

2.7.2　快速3-着色算法 82

2.7.3　最优3-着色算法 83

习题 84

参考文献 86

第三章　前缀计算 88

3.1 引言 89

3.1.1　前缀计算的定义 89

3.1.2　前缀计算的应用 90

3.2　并行前缀计算算法 90

3.2.1　组合网络上的前缀计算 91

3.2.2　互连网络上的前缀计算 95

3.2.3　PRAM模型上的前缀计算 98

3.3　线性递归方程求解 103

3.3.1　平易线性递归方程求解算法 103

3.3.2　更优线性递归方程求解算法 104

3.4　排序 107

3.4.1　基排序 107

3.4.2　快排序 109

3.5　最大和子序列 112

3.5.1　简单串行算法 112

3.5.2　易于并行化的串行算法 113

3.5.3　并行算法 116

习题 118

参考文献 119

第四章　排序和选择网络 120

4.1　Batcher归并和排序网络 121

4.1.1 比较操作和［0,1］原理 121

4.1.2　奇偶归并网络 122

4.1.3　双调归并网络 124

4.1.4　Batcher排序网络 125

4.2　（m,n）-选择网络 128

4.2.1　分组选择网络 128

4.2.2 平衡分组选择网络 132

4.3　AKS排序网络 133

4.3.1 扩展器 133

4.3.2　对分器 135

4.3.3　分离器 137

4.3.4　AKS排序网络的构造及分析 138

习题 142

参考文献 143

第五章　排序和选择算法 145

5.1　Stone双调排序算法 146

5.1.1　均匀洗牌函数及其性质 146

5.1.2　Stone的观察及其计算模型 146

5.1.3　Stone的并行排序算法 149

5.2　Thompson和Kung双调排序算法 151

5.2.1　处理器编号方式 151

5.2.2　Thompson和Kung的观察 152

5.2.3　Thompson和Kung的双调排序算法 153

5.3　Preparata和Vuilemin双调排序算法 156

5.3.1　算法原理 156

5.3.2　流水线技术 158

5.3.3　算法描述 159

5.4　Akl并行k-选择算法 160

5.4.1　算法原理及物理描述 161

5.4.2　并行k-选择算法 161

5.4.3　算法分析 163

5.5　Valiant并行归并算法 164

5.5.1 归并算法的基本原理 164

5.5.2 k=？」时Valiant归并 165

5.5.3 k=？」时Valiant归并 166

5.6　Hirschberg并行桶排序算法 167

5.6.1　并行桶排序算法原理 167

5.6.2　并行桶排序算法描述 168

5.7　Preparata并行枚举排序算法 169

5.7.1　枚举排序及其实现方法 169

5.7.2　排序算法的设计和分析 171

5.8　Cole并行归并排序算法 173

5.8.1　使用覆盖和位序的归并方法 173

5.8.2　Cole最佳排序算法 175

5.8.3　算法的正确性证明及分析 177

5.9　MIMD-CREW模型上的异步枚举排序算法 183

5.9.1　算法原理和描述 183

5.9.2　算法举例和分析 184

5.10　MIMD-TC模型上的异步快排序算法 185

5.10.1　算法原理和描述 185

5.10.2　算法举例和分析 187

习题 188

参考文献 189

第六章　分布式算法 191

6.1　分布式算法概述 192

6.1.1　分布式算法特点 192

6.1.2　计算模型 193

6.1.3　复杂性度量 195

6.2　构造生成树算法 195

6.2.1　广播和敛播算法 196

6.2.2　构造生成树 199

6.2.3　构造深度优先生成树 201

6.2.4　不指定根构造生成树 203

6.2.5　最小生成树 206

6.3　环上选举算法 210

6.3.1　LCR算法 211

6.3.2　改进算法 212

6.4　分布式k-选择算法 214

6.4.1　随机k-选择算法 214

6.4.2　确定k-选择算法 216

6.4.3　分布式求中值算法 218

6.5　定序与排序 220

6.5.1　定序算法 220

6.5.2　排序算法 224

习题 226

参考文献 226

第七章　并行搜索 228

7.1　单处理机上的搜索 229

7.1.1　单处理机上的顺序搜索 229

7.1.2　单处理机上有序表的对半搜索 229

7.2 SIMD共享存储模型上有序表的搜索 230

7.2.1 SIMD-EREW模型上的搜索 230

7.2.2 SIMD-CREW模型上的搜索 231

7.3 SIMD共享存储模型上随机序列的搜索 234

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

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

7.4 树连接的SIMD模型上随机序列的搜索 236

7.4.1　提问 236

7.4.2　维护 237

7.5 网孔连接的SIMD模型上随机序列的搜索 238

7.5.1　提问 239

7.5.2　维护 242

7.6　MIMD共享存储模型上有序表的搜索 242

7.6.1　AVL树及其顺序插入算法 242

7.6.2　Ellis并行搜索和插入算法 244

习题 247

参考文献 248

第八章　选路算法 249

8.1　引言 250

8.2　贪心选路算法 251

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

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

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

8.3　随机和确定选路算法 257

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

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

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

8.4　数据的分布和集中 262

8.4.1　数据的分布 262

8.4.2　多到一选路算法 266

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

8.5.1 阻塞网络中的竞争分析 267

8.5.2　阻塞网络中的自选路算法 270

8.5.3 可重排网络中的中级选路算法 273

习题 279

参考文献 280

第九章　串匹配 282

9.1　字符串精确匹配并行算法 283

9.1.1 KMP串匹配顺序算法 283

9.1.2　分布存储系统上精确串匹配并行算法 285

9.1.3　基于比较指纹函数值的串匹配算法及其并行化 289

9.1.4　串匹配的平均时间复杂度分析 291

9.1.5　后缀树上的串匹配 300

9.2　多模式匹配并行算法 310

9.2.1　多模式匹配问题 310

9.2.2 可重构网孔机器上多模式匹配并行算法 310

9.3　允许k-差别的近似串匹配并行算法 314

9.3.1 编辑距离与允许k-差别的近似串匹配问题 315

9.3.2　PRAM模型上允许k-差别的近似串匹配并行算法 317

9.4　允许k-误配的近似串匹配并行算法 324

9.4.1 汉明距离与允许k-误配的近似串匹配问题 324

9.4.2　LARPBS计算模型及其基本数据移动操作 325

9.4.3 LARPBS模型上允许k-误配的近似串匹配并行算法 327

9.5　最长公共子序列查找并行算法 331

9.5.1 求解最长公共子序列问题的顺序算法 332

9.5.2 BSR模型上求解最长公共子序列问题的并行算法 334

9.5.3　心动阵列处理器结构上求解最长公共子序列问题的并行算法 339

习题 347

参考文献 348

第十章　表达式求值 351

10.1　构造表达式树 352

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

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

10.1.3　计算match（i）的并行算法 355

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

10.2.1　二叉树上的填充游戏 356

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

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

10.4　一般表达式求值算法 363

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

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

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

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

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

10.5.1　基本概念和术语 370

10.5.2 正则表达式到非确定有限自动机的HU转换方法 371

10.5.3　有限自动机确定化并行算法 375

10.5.4　确定自动机的最小化并行算法 377

习题 380

参考文献 381

第十一章　上下文无关语言 383

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

11.1.1　基本概念和术语 384

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

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

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

11.2.1　基本概念和算法原理 391

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

11.3　任意上下文无关语言的并行语法分析 397

11.3.1　基本概念与算法原理 397

11.3.2　SIMD-LC模型上任意上下文无关语言的并行语法分析算法 399

11.4 括号语言的最优并行识别和语法分析 401

11.4.1　基本概念和算法原理 401

11.4.2　算法的具体实现 402

11.4.3　树的压缩技术 404

11.4.4 SIMD-CREW模型上括号语言的语法分析算法 407

习题 408

参考文献 409

第十二章　矩阵运算 410

12.1 矩阵转置 411

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

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

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

12.1.4 SIMD-CC模型上的矩阵转置 416

12.2　矩阵相乘 418

12.2.1　单处理机上的矩阵相乘 418

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

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

12.2.4 MIMD机器上的矩阵乘法 424

12.3　矩阵和向量相乘 427

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

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

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

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

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

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

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

习题 439

参考文献 443

第十三章　数值计算 444

13.1　三对角方程组的求解 445

13.1.1　三对角方程组直接求解法 445

13.1.2　三对角方程组奇偶归约求解法 447

13.2 n阶线性方程组的求解 449

13.2.1 SIMD-CREW模型上的Gauss-Jordan算法 450

13.2.2 MIMD-CREW模型上的Gauss-Seidel算法 452

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

13.3　非线性方程的求根 457

13.3.1 SIMD-CREW模型上的求根算法 457

13.3.2 MIMD-CREW模型上的牛顿求根法 459

13.3.3 Fibonacci分点法异步求根算法 461

13.4　偏微分方程的差分求解 463

13.4.1　偏微分方程的差分数值求解法 464

13.4.2 SIMD-MC2模型上的PDE求解方法 465

13.5　方阵的特征值与特征向量Jacobi方法 469

13.5.1　对称方阵对角化方法 469

13.5.2 SIMD-CC模型上的求特征值算法 471

习题 473

参考文献 475

第十四章　快速傅氏变换 476

14.1　快速傅里叶变换 477

14.1.1　顺序的FFT算法 477

14.1.2 FFT应用于多项式乘积 478

14.2 DFT直接并行计算法 480

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

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

14.3 并行FFT算法 484

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

14.3.2 SIMD-BF模型上的FF［算法 486

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

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

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

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

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

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

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

习题 501

参考文献 503

第十五章　图论算法 504

15.1　图的并行搜索 505

15.1.1 p-深度优先搜索 505

15.1.2 p-宽深优先搜索 506

15.1.3 p-宽度优先搜索 506

15.2　图的传递闭包 508

15.2.1　传递闭包问题 508

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

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

15.3　图的连通分量 513

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

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

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

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

15.4　图的最短路径 521

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

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

15.5　图的最小生成树 528

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

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

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

15.6　图的着色 538

15.6.1　二分图的边着色算法 538

15.6.2　外平面图最优顶点着色 540

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

15.6.4 Halin图最优边着色算法 549

习题 553

参考文献 556

第十六章　计算几何 558

16.1　判定问题 559

16.1.1 近邻问题 559

16.1.2　相交问题 563

16.1.3　包含问题 569

16.2　构造问题 574

16.2.1　求凸壳问题的下界 575

16.2.2　顺序求凸壳算法 575

16.2.3 SIMD-MT模型上的求凸壳算法 577

16.2.4 SIMD-EREW模型上的求凸壳算法 579

16.3 Voronoi图问题 585

16.3.1　基本概念 585

16.3.2　构造Voronoi图的串行分治算法 587

16.3.3 超立方模型上构造Voronoi图算法 588

16.3.4 SIMD-CREW模型上构造Voronoi图算法 593

16.4 平面点集的三角剖分 598

16.4.1　基本概念 598

16.4.2 Delaunay三角剖分串行算法 600

16.4.3 Delaunay三角剖分并行算法 604

习题 609

参考文献 610

第十七章 组合搜索 613

17.1　产生排列的算法 614

17.1.1　产生词典序的排列算法 614

17.1.2　串行排列算法的并行化 616

17.1.3 自适应排列产生器 621

17.2　产生组合的算法 623

17.2.1 产生组合的顺序算法 623

17.2.2 产生组合的并行算法 624

17.3　分支限界法的搜索 629

17.3.1 8-谜问题 630

17.3.2　串行分支限界算法 631

17.3.3 用串行分支限界法求TSP 633

17.3.4　并行TSP算法 637

17.4　串行的α-β搜索算法 639

17.4.1 博弈树与最小最大原理 639

17.4.2　串行的α-β算法 640

17.4.3 MIMD模型上α-β搜索算法 642

17.5　动态规划 648

17.5.1　矩阵链乘问题 649

17.5.2　最短路径问题 653

17.5.3 0/1背包问题 654

习题 656

参考文献 659

第十八章　随机算法 661

18.1 引言 662

18.1.1　概率论的基本知识 662

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

18.1.3　随机算法的设计方法 666

18.2　部分独立集 668

18.2.1　有向环图 669

18.2.2 平面图 670

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

18.3.1　细图层次 673

18.3.2　细图层次的构造算法 673

18.4　模式匹配 675

18.4.1　指纹函数 676

18.4.2　串匹配 679

18.4.3　二维数组的匹配 680

18.5　多项式恒等的验证 682

18.5.1 基本技术 682

18.5.2　矩阵乘积的验证 683

18.6　排序 685

18.6.1　随机采样与随机快排序 685

18.6.2　并行随机快排序算法 686

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

18.7　最大匹配和完备匹配 691

18.7.1　图的代数性质 692

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

习题 698

参考文献 699

第十九章　VLSI计算理论 701

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

19.1.1 VLSI电路模型 702

19.1.2 VLSI计算模型 704

19.2 VLSI面-时下界理论 706

19.2.1 几种基本的下界论点 706

19.2.2　信息流和穿越序列 708

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

19.3.1　树的布局 710

19.3.2　网孔和树网的布局 712

19.3.3　洗牌交换网的布局 713

19.3.4　立方环的布局 715

19.3.5　蝶形网的布局 717

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

19.4.1　树的布局下界 718

19.4.2　树网的布局下界 720

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

19.4.4　蝶形网的布局下界 724

19.5　分治布局法 724

19.5.1 分离集 725

19.5.2　强分离集 727

19.5.3 通道生成 728

19.5.4　分治布局法 729

19.6 VLSI布局理论 732

19.6.1 平面图的分离定理 732

19.6.2　图的交叉点数 733

19.6.3　布局下界定理 734

习题 736

参考文献 737

第二十章　并行计算理论 738

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

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

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

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

20.2 PRAM-CREW的下界 743

20.2.1　理想的PRAM模型 743

20.2.2　形式描述 744

20.2.3　特定问题的下界 746

20.3 PRAM-EREW的下界 747

20.3.1 工具和方法 747

20.3.2　主要下界 748

20.4 PRAM-CRCW的下界 750

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

20.4.2　无界扇入电路的下界 757

20.5　并行复杂性理论 762

20.5.1　串行复杂性理论简介 762

20.5.2　问题的可并行化 763

20.5.3 NC类和RNC类 766

20.5.4 P-完全问题范例 770

20.5.5　小结 778

习题 778

参考文献 779

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

A.1　大-O及其运算 781

A.2　大-Ω和大-Θ 781

A.3　小-ο和小-ω 782

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

附录C　专业术语中英文对照表及索引 797