串行算法并行化基础PDF电子书下载

第0章　绪论 1

0.1　计算科学 1

0.2　为什么要并行计算 2

0.3　巨型机、高性能计算机本质特征：并行计算 3

0.4　巨型机、高性能计算机基本矛盾：台数与计算效率的矛盾 3

0.5　并行运算和并行数据传送 3

0.6　并行执行方式和重叠执行方式 4

0.7　并行算法与串行算法并行化 4

0.8　巨型机、高性能计算机的关键技术 4

0.9　数据相关和控制相关 5

第1章　串行算法并行化的基本概念 6

1.1　题目的规模与计算工作量N 6

1.2　题目的计算时间T 6

1.3　题目最快串行计算算法C0 7

1.4　题目在并行计算模型M（S）下并行计算算法B 7

1.5　题目在M（S）下并行计算算法B的计算速度：VB,M(s)(N) 7

1.6　在并行计算模型M（S）下题目并行计算算法B的加速比 8

1.7　在并行计算模型M（S）下题目并行计算算法B的效率 8

1.8　并行算法B的计算复杂性 8

1.9　常数效率并行算法 8

1.10　在某些讨论中的算法分类 8

1.11　并行计算台数S对并行计算速度的影响及串行算法并行化的意义 9

第2章　执行并行计算算法的并行计算机系统结构模型 10

2.1　并行算法实现的两要素之一：并行传送 11

2.2　单指令流-单数据流（SIMD）计算机 13

2.3　SIMD二维阵列机 14

2.4　流水线向量机 15

2.5　第二代巨型机：纵横加工（分段处理）流水线向量机 15

2.6　细胞结构化虚共存纵横加工向量机 17

2.7　多维立方体机 19

2.8　多指令流-多数据流系统MIMD 19

2.9　内部互联网络 19

2.10　通用或专用计算网络 19

2.11　PRAM并行随机访问计算机 21

2.12　可变总线结构 22

2.13　素数存储系统 24

2.14　分段线性变换存储系统 25

第3章　向量语言 29

3.1　数据类型与数据结构 29

3.2　向量基本运算 29

3.3　向量或者数组中的向量 32

3.4　可以用硬件实现的控制向量 33

3.5　变长向量运算 38

3.6　向量语言的扩充 40

3.7　向量高级语言 41

第4章　串行算法并行化方法综述与比较 42

4.1　串行算法并行化之一：多分法方法 42

4.2　串行算法并行化之二：倍增法 43

4.3　串行算法并行化之三：纵横加工法 43

4.4　串行算法并行化效率比较 44

4.5 串行算法并行化之四：利用软件、硬件和软件硬件结合的优化方法 44

4.6　串行算法并行化之五：利用硬件直接实现的控制向量 45

第5章　两路归并与分类串行算法并行化 47

5.1　归并与排序的快速串行算法 47

5.2　归并基本定义与定理 50

5.3　K E Batcher的Odd-even并行归并网络 53

5.4　根据归并基本定理所构造的快速并行归并算法 54

5.5　K E Batcher的Bitonic归并算法 55

5.6　利用并行归并来实现并行排序 59

5.7　归并与排序串行算法并行化的OPTIMAL并行算法之一：纵横并行归并算法 60

5.8　归并与分类串行算法并行化的OPTIMAL并行算法之二：k-维并行归并算法 61

5.9　在理论模型上的排序 63

第6章　多路归并串行算法并行化 65

6.1　多路归并与排序的纵横斜并行算法 65

6.2 多路归并的k-Bitonic及k-Bitonic并行算法：Odd-even并行算法与Bitonic并行算法的统一推广算法 65

第7章　一类一阶递推串行算法并行化 72

7.1　一类一阶递推的方程和最快串行算法 72

7.2　一类一阶递推方程的例子和应用背景 73

7.3　一阶递推和一类递推串行算法并行化的基本原理、思路和定理 74

7.4　一类一阶递推串行算法并行化的倍增（Doubling）算法 79

7.5　一类递推串行算法并行化的常数效率（OPTIMAL）并行算法之一：一类递推纵横并行算法 82

7.6　一类递推串行算法并行化的常数效率（OPTIMAL）并行算法之二：一类递推k-维并行算法 84

7.7　一类递推串行算法并行化的OPTIMAL并行算法之三：一类递推混合并行算法 88

7.8　几种算法的比较 91

7.9　一类递推的其他算法 92

第8章　一类广函数：纵横矩阵加工广函数 93

8.1　纵横矩阵加工广函数 93

8.2　纵横矩阵加工广算法的典型实例一：两路合并的Bitonic算法 100

8.3　纵横矩阵加工广算法的典型实例二：一类递推方程 102

8.4　纵横矩阵加工广函数的应用列举 107

8.5　结论 110

附录 （m,N）选择问题的纵横并行算法例子 111

参考文献 113