并行计算 模型与算法PDF电子书下载

第1章 绪论 1

1.1 模型 1

1.1.1 白盒模型 1

1.1.2 黑盒模型 2

1.2 计算模型 3

1.2.1 计算能力模型 3

1.2.2 算法设计模型 7

1.3 并行计算模型 8

1.3.1 基本度量参数 9

1.3.2 基本并行计算模型 11

1.4 相关概念 13

1.4.1 系统结构模型 13

1.4.2 并行编程模型 18

1.4.3 并行编程模式 22

1.4.4 基准测试程序 23

1.4.5 数据一致性模型 25

1.4.6 并行、并发与分布式 27

1.5 并行算法设计 30

1.5.1 并行算法表示 30

1.5.2 算法复杂度 31

1.5.3 问题 31

1.6 小结 33

第2章 固定结构并行计算模型 34

2.1 逻辑电路 35

2.1.1 定义 35

2.1.2 加法器 35

2.2 比较器电路 39

2.2.1 定义 39

2.2.2 归并 39

2.2.3 排序 44

2.2.4 选择 46

2.3 代数电路 48

2.3.1 定义 48

2.3.2 FFT 48

2.3.3 前缀和 51

2.4 线性阵列 53

2.4.1 定义 53

2.4.2 排序 54

2.4.3 三角矩阵求解 57

2.5 混洗连接 59

2.5.1 定义 59

2.5.2 排序 60

2.5.3 FFT 62

2.5.4 矩阵转置 62

2.6 网格 64

2.6.1 定义 64

2.6.2 归并 64

2.6.3 排序 66

2.6.4 矩阵乘 68

2.6.5 迭代法 70

2.7 树形 71

2.7.1 定义 71

2.7.2 排序 73

2.7.3 前缀和 74

2.7.4 图的连通分量 75

2.8 超立方 76

2.8.1 定义 76

2.8.2 排序 77

2.8.3 通信 78

2.9 小结 79

2.10 习题 80

第3章 共享存储并行计算模型（计算复杂度） 83

3.1 PRAM模型 83

3.1.1 定义 83

3.1.2 模型的能力 84

3.1.3 算法设计技术 85

3.1.4 问题下界 85

3.2 PRAM变体 86

3.2.1 APRAM 86

3.2.2 分相PRAM 87

3.3 选择 88

3.3.1 EREW上的成本最优算法 88

3.3.2 CRCW上的常数时间算法 89

3.3.3 缩减处理器 90

3.3.4 算法级联 91

3.3.5 下界 92

3.4 归并 93

3.4.1 CREW上的常数时间算法 93

3.4.2 缩减处理器 94

3.5 查找 95

3.5.1 CREW上的最优时间算法 95

3.5.2 下界 95

3.6 排序 95

3.6.1 枚举排序 96

3.6.2 Preparata排序 96

3.6.3 下界 97

3.7 前缀和 98

3.7.1 倍增法 98

3.7.2 算法级联 98

3.8 图算法 99

3.8.1 分层倍增法 99

3.8.2 欧拉回路 101

3.8.3 Ear分解 103

3.8.4 破对称方法 104

3.9 小结 105

3.10 习题 106

第4章 分布式存储并行计算模型（通信复杂度） 107

4.1 通信复杂度模型 107

4.1.1 LPRAM模型 107

4.1.2 Yao模型 109

4.2 延迟带宽模型 110

4.2.1 LogP模型 110

4.2.2 Postal模型 111

4.2.3 LogGP模型 115

4.3 其他模型 116

4.3.1 BSP 116

4.3.2 QSM 116

4.3.3 BPRAM模型 117

4.4 小结 117

第5章 存储层次并行计算模型（存储复杂度） 118

5.1 单层存储层次 118

5.2 两层存储层次 121

5.2.1 红蓝卵石模型 121

5.2.2 分块传输模型 124

5.3 多层存储层次 126

5.3.1 多层卵石模型 127

5.3.2 HMM 128

5.3.3 分块HMM 131

5.3.4 RAM（h）模型 132

5.4 缓存无关模型 133

5.4.1 串行模型 134

5.4.2 并行模型 136

5.5 小结 138

5.6 习题 139

第6章 并行程序性能模型 141

6.1 性能模型与计算模型 141

6.2 加速比模型 142

6.2.1 Amdahl模型 142

6.2.2 Gustafson模型 142

6.2.3 Karp-Flatt模型 144

6.2.4 Sun-Ni模型 145

6.2.5 等效率模型 145

6.2.6 DAG模型 146

6.3 访存序列模型 147

6.3.1 缺失率 147

6.3.2 重用距离 148

6.3.3 平均足迹 149

6.3.4 多进程模型 150

6.4 软硬协同模型 151

6.4.1 计算密集度 151

6.4.2 串行平衡模型 152

6.4.3 并行平衡模型 152

6.4.4 Hill-Marty模型 153

6.5 算法优化模型 154

6.5.1 算法级联 154

6.5.2 参数优化 155

6.6 小结 156

第7章 并发与分布式算法 157

7.1 互斥算法 157

7.1.1 共享存储算法 157

7.1.2 分布式存储算法 164

7.1.3 基于硬件操作 170

7.1.4 基于信号量操作 172

7.2 锁算法 174

7.2.1 自旋锁 174

7.2.2 读写锁 177

7.3 同步算法 179

7.3.1 分布式存储算法 179

7.3.2 共享存储算法 181

7.4 队列算法 183

7.4.1 有界队列 184

7.4.2 无界队列 185

7.5 广播算法 188

7.5.1 洪水算法 188

7.5.2 生成树算法 188

7.6 小结 189

7.7 习题 189

参考文献 191