第一章 并行算法基础 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