《并行计算方法 上》求取 ⇩

第一章并行机简介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 位阵列机 DAP11

1.2.3 相联阵列机13

1.2.4 数列处理机15

1.3 纵向加工向量机 STAR-10015

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 FFT205

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 计算多维 DFT269

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