并行计算方法 上PDF电子书下载

第一章 并行机简介 1

1.1 基本概念 1

1.1.1 单指令流-单数据流 2

1.1.2 串行机 2

1.1.3 单指令流-多数据流 3

1.1.4 多指令流-多数据流 4

1.1.5 并行机 5

1.2.1 ILLIAC-Ⅳ机 7

1.2 阵列机 7

1.2.2 位阵列机 DAP 11

1.2.3 相联阵列机 13

1.2.4 数列处理机 15

1.3 纵向加工向量机 STAR-100 15

1.4 纵横加工向量机 20

1.4.1 757机 21

1.4.2 YH 机 23

1.5.1 整机系统 31

1.5 并行机的发展 31

1.5.2 结构的变化 34

1.5.3 数据流计算机 36

第二章 并行机的使用 39

2.1 数据调度问题之一——数组存储 39

2.1.1 等间距存储 40

2.1.2 非等间距存储 44

2.1.3 交叉问题 45

2.2 数据调度问题之二——数据流 48

2.2.1 一般概念 48

2.2.2 内加工计算问题 49

2.2.3 海存加工计算问题 56

2.3 指令流问题 57

2.4 运算流水线 59

2.4.1 无关化运算 59

2.4.2 提高并行度 61

2.5 程序优化 64

2.6 并行机的使用效率分析 68

第三章 并行算法的一般概念 75

3.1 数值问题分类 75

3.1.1 串行计算问题 75

3.1.2 并行计算问题 76

3.1.3 串并行混合计算问题 76

3.2 算法比较 77

3.2.1 SIMD 型并行算法 78

3.2.2 MIMD 型并行算法 82

3.3 算法并行性度量 85

3.4 并行算法复杂性 86

3.5 并行算法的收敛性和稳定性 89

3.5.1 收敛速度 89

3.5.2 舍入误差和格式稳定性 90

3.6 并行算法构造中的几个问题 92

4.1.1 内积算法 96

4.1 矩阵乘法 96

第四章 几个典型问题的并行计算法 96

4.1.2 外积算法 97

4.1.3 斯特拉森算法 98

4.1.4 威诺格拉德算法 100

4.1.5 n 阶方阵矩阵乘法实例 101

4.2 递归问题 104

4.2.1 一般概念 104

4.2.2 倍增法 106

4.2.3 分段法 117

4.2.4 循环加倍法 120

4.2.5 一类递归函数 122

4.2.6 并行效率分析与比较 128

4.3 多项式求值的并行算法 136

4.3.1 霍纳法及其推广 137

4.3.2 倍增法 139

4.3.3 分段法 143

4.3.4 分段-倍增法 146

4.3.5 直接向量法 147

4.3.6 比较与分析 147

4.4 叠加问题 150

4.4.1 循环加倍法 151

4.4.2 分段法 152

4.5 分类问题 154

4.6 求根问题的并行计算 158

5.1 下三角方程组 161

第五章 线代数并行计算 161

5.1.1 向量回代法 162

5.1.2 列扫描法 163

5.1.3 块回代法 163

5.1.4 并行乘积法 164

5.2 稠密方程组 166

5.2.1 主元高斯消去法 166

5.2.2 约当消去法 169

5.3.1 倍增法 170

5.3 三对角方程组 170

5.3.2 循环奇偶约化法 172

5.3.3 任意三对角方程组的求解 174

5.3.4 多重特解法 178

5.4 矩阵求逆 180

5.4.1 皮斯法求逆 180

5.4.2 刘易斯方法 181

5.4.3 任意三对角阵的求逆 184

5.5 拟块对角阵 186

5.6 迭代法梯度法 187

5.7 稀疏方程组 190

5.8 特征值问题的并行计算 192

5.8.1 雅可比算法 192

5.8.2 乘幂法和反幂法 196

5.8.3 豪斯赫尔德方法 198

5.8.4 QR 法 200

5.8.5 海曼方法 202

第六章 快速变换 205

6.1 快速富氏变换 205

6.1.1 FFT 205

6.1.2 并行的 FFT(PFFT) 210

6.1.3 PFFT 在循环卷积中的应用 221

6.2 数论变换 226

6.2.1 数论基础知识 226

6.2.2 数论变换 231

6.2.3 FNT 的快速算法和并行算法 239

6.2.4 PFNT 在循环卷积计算中的应用 244

6.3 快速多项式变换 248

6.3.1 多项式变换 248

6.3.2 多项式变换的快速算法(FPT) 253

6.3.3 数字循环卷积的计算 254

6.3.4 多维多项式变换及多维循环卷积 267

6.3.5 利用 FPT 计算多维 DFT 269

6.3.6 小结 272

第七章 最优化并行算法 275

7.1 一维优化的并行计算 275

7.1.1 应用导数的一维优化算法 276

7.1.2 黄金分割批寻找方法 277

7.1.3 偶数分批法 284

7.1.4 并行效率 287

7.2 利用导数的多维优化算法的并行计算 290

7.3 并行变尺度最优化算法 296

7.4 梯度投影并行拟牛顿算法 298

7.5 并行约克勃生-屋克斯曼最优化算法 312

7.6 求函数总极值的组合随机并行算法 316

7.7 鲍威尔算法和查赞-麦连科算法 322

7.7.1 鲍威尔算法 322

7.7.2 查赞-麦连科算法 328

7.8 斯洛波达算法和修梯算法 332

参考文献 335