可扩展并行算法的设计与分析

第1章 并行计算机
1. 1 并行计算机的分类
1. 1. 1 SISD型计算机
1. 1. 2 SIMD型并行机
1. 1. 3 共享存储MIMD并行多处理机
1. 1. 4 分布存储MIMD并行多处理机
1. 1. 5 分布共享存储MIMD并行机
1. 2 并行计算机的发展
1. 2. 1 应用需求的推动作用
1. 2. 2 70年代
1. 2. 3 80年代早期
1. 2. 4 80年代中期
1. 2. 5 80年代后期
1. 2. 6 90年代早期
1. 2. 7 90年代中期至今
1. 3 并行程序设计
1. 3. 1 向量程序设计
1. 3. 2 共享存储并行程序设计
1. 3. 3 数据并行程序设计
1. 3. 4 消息传递并行程序设计
1. 4 并行算法的分类
1. 5 并行算法的发展
第2章 并行计算模型
2. 1 计算模型位置与准则
2. 2 PRAM模型
2. 2. 1 SIMD-PRAM模型
2. 2. 2 MIMD-PRAM模型
2. 2. 3 PRAM模型的特点
2. 3 H-PRAM模型
2. 4 LogP模型
2. 5 C3模型
2. 6 BDM模型
2. 7 5种模型比较
第3章 并行算法性能度量
3. 1 若干概念与性能参数
3. 1. 1 并行算法的运行时间
3. 1. 2 问题的规模与分类
3. 1. 3 并行机规模,
3. 1. 4 并行度与粒度
3. 1. 5 加速比与效率
3. 2 并行算法运行时间模型
3. 2. 1 共享存储环境下的运行时间模型
3. 2. 2 分布式存储环境下的运行时间模型
3. 3 并行算法性能评价准则
3. 3. 1 共享存储环境下的性能评价准则
3. 3. 2 分布式存储环境下的性能评价准则
第4章 并行算法可扩展性分析
4. 1 可扩展性定义. 指标和基本特征
4. 1. 1 可扩展性定义
4. 1. 2 并行系统可扩展性指标及其基本特征
4. 1. 3 并行算法及其实现的可扩展性
4. 1. 4 并行算法--体系结构组合可扩展性
4. 2 常用的可扩展性度量方法
4. 2. 1 并行算法可扩展性的等效率度量方法
4. 2. 2 并行算法--机器组合的等速度度量方法
4. 2. 3 并行算法--体系结构的等计算时间／通信开销比率度量方法
4. 3 实用例子可扩展性分析
4. 3. 1 矩阵乘并行算法可扩展性分析
4. 3. 2 Navier-Stokes偏微分方程组并行算法与YH-3组合的可扩展性分析
第5章 线性代数方程组的并行计算
5. 1 三对角线性方程组的直接解法
5. 1. 1 Michielse＆Vorst算法
5. 1. 2 双向并行分裂算法(DPP算法)
5. 1. 3 对角占优三对角线性方程组的并行算法(PPD算法)
5. 1. 4 周期三对角线性方程组的直接解法
5. 2 求解稀疏线性方程组的Krylov子空间迭代法
5. 2. 1 Krylov子空间迭代法
5. 2. 2 预条件技术
5. 2. 3 Krylov子空间迭代法的并行计算
5. 3 ScaLAPACK简介及一般线性方程组求解
5. 3. 1 线性代数软件的发展
5. 3. 2 ScaLAPACK的数据布局与分布
5. 3. 3 LU分解的并行计算与实现
第6章 特征值与特征值向量的并行计算
6. 1 对称三对角特征值矩阵特征值问题的并行计算
6. 1. 1 分而治之算法
6. 1. 2 同伦连续算法
6. 2 对称带状矩阵特征值问题的并行计算
6. 2. 1 二分法及其改进
6. 2. 2 基于二分迭代的分而治之算法
6. 3 非对称矩阵特征值问题的并行计算
6. 3. 1 分而治之算法
6. 3. 2 谱分解算法
6, 4 算法可扩展性分析
第7章 多重网格与区域分解算法的并行计算
7. 1 多重网格算法的并行计算
7. 1. 1 算法原理
7. 1. 2 简单应用规则
7. 1. 3 内在并行度
7. 1. 4 网格划分与通信结构
7. 1. 5 可扩展分析
7. 1. 6 算法并行的内在瓶颈
7. 1. 7 算法改进
7. 2 两层加性Schwarz区域分解算法的并行计算
7. 2. 1 算法原理
7. 2. 2 并行实现与数值实验
7. 2. 3 可扩展分析
第8章 离散变换与离散卷积的并行算法
8. 1 一维DFT的并行算法
8. 1. 1 并行快速傅里叶变换
8.
1.
2 一维DFT的分裂并行算法
8.
1.
3 实序列DFT的计算
8.
2 二维及多维DFT的并行算法
8.
2.
1 并行行列算法
8.
2.
2 并行矩阵转置
8.
2.
3 通信和计算的重叠
8.
2.
4 多维实序列DFT的计算
8. 3 并行多项式变换算法
8.
3.
1 并行多项式变换
8.
3.
2 DFT的并行多项式变换算法
8.
4 离散余弦变换的并行算法
8.
4.
1 用DFT计算DCT
8.
4.
2 二维离散余弦变换的并行算法
8.
5 离散W变换的并行算法
8.
5.
1 用DFT计算DWT
8.
5.
2 多维DWT的并行多项式变换算法
8.
6 离散卷积的计算
第9章 小波分析的并行算法
9.
1 小波变换导论
9.
1.
1 连续小波变换
9.
1.
2 小波级数
9.
1.
3 多尺度分析和离散小波变换
9.
1.
4 高维多尺度分析和mallat算法
9.
1.
5 小波包变换
9.
2 小波函数值的计算
9.
2.
1 迭代方法
9.
2.
2 逐点方法
9.
2.
3 高维小波函数的计算
9.
3 小波变换的并行计算
9.
3.
1 周期离散小波变换
9.
3.
2 离散小波变换的并行算法
9.
3.
3 离散小波变换计算的傅里叶变换方法
9.
3.
4 小波级数和连续小波变换的计算
9.
4 小波包最优基选取的并行算法
9.
4.
1 小波包和最优基
9.
4.
2 并行小波包分解和最优基选取
9.
5 离散小波变换算法的可扩展性分析
第10章 分布式存储环境下并行程序实例
10.
1 消息传递环境
10.
1.
1 可移植的异构编程环境PVM
10.
1.
2 消息传递标准平台MPI
10.
2 PVM应用程序实例
10.
2.
1 矩阵乘积PVM程序
10.
2.
2 对称矩阵特征值问题并行求解PVM程序
参考文献