第一章 绪论 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