第1章 并行计算介绍
1. 1 推动并行化
1. 1. 1 计算能力因素--从晶体管到
浮点运算速度
1. 1. 2 内存及磁盘速度的因素
1. 1. 3 数据通信因素
1. 2 并行计算适用范围
1. 2. 1 在工程及设计中的应用
1. 2. 2 科学计算中的应用
1. 2. 3 商业应用
1. 2. 4 计算机系统中的应用
1. 3 本书的组织及内容
1. 4 书目评注
习题
第2章 并行编程平台
2. 1 隐式并行：微处理器体系结构的
发展趋势*
2. 1. 1 流水线与超标量执行
2. 1. 2 超长指令字处理器
2. 2 内存系统性能的局限*
2. 2. 1 使用高速缓存改善有效内存延迟
2. 2. 2 内存带宽的影响
2. 2. 3 躲避内存延迟的其他方法
2. 2. 4 多线程与预取间的权衡
2. 3 并行计算平台剖析
2. 3. 1 并行平台的控制结构
2. 3. 2 并行平台的通信模型
2. 4 并行平台的物理组织
2. 4. 1 理想并行计算机的体系结构
2. 4. 2 并行计算机互连网络
2. 4. 3 网络拓扑结构
2. 4. 4 静态互连网络评价
2. 4. 5 动态互连网络评价
2, 4. 6 多处理器系统中的高速
缓存一致性
2. 5 并行计算机的通信成本
2. 5. 1 并行计算机的消息传递成本
2. 5. 2 共享地址空间计算机的通信成本
2. 6 互连网络的路由选择机制
2. 7 进程-处理器映射的影响和映射技术
2. 7. 1 图的映射技术
2. 7. 2 成本-性能平衡
2. 8 书目评注
习题
第3章 并行算法设计原则
3. 1 预备知识
3. 1. 1 分解. 任务与依赖图
3. 1. 2 粒度. 并发性与任务交互
3. 1. 3 进程和映射
3. 1, 4 进程与处理器
3. 2 分解技术
3. 2. 1 递归分解
3. 2. 2 数据分解
3. 2. 3 探测性分解
3. 2. 4 推测性分解
3. 2. 5 混合分解
3. 3 任务和交互的特点
3. 3. 1 任务特性
3. 3. 2 任务间交互的特征
3. 4 负载平衡的映射技术
3. 4. 1 静态映射方案
3. 4. 2 动态映射方案
3. 5 包含交互开销的方法
3. 5. 1 最大化数据本地性
3. 5. 2 最小化争用与热点
3. 5. 3 使计算与交互重叠
3. 5. 4 复制数据或计算
3. 5. 5 使用最优聚合交互操作
3. 5. 6 一些交互与另一些交互的重叠
3. 6 并行算法模型
3. 6. 1 数据并行模型
3. 6. 2 任务图模型
3. 6. 3 工作池模型
3. 6. 4 主-从模型
3. 6. 5 流水线模型或生产者-消费者
模型
3. 6. 6 混合模型
3. 7 书目评注
习题
第4章 基本通信操作
4. 1 一对多广播以及多对一归约
4. 1. 1 环或线性阵列
4. 1. 2 格网
4. 1. 3 超立方体
4. 1. 4 平衡二叉树
4. 1. 5 算法细节
4. 1. 6 成本分析
4. 2 多对多广播和归约
4. 2. 1 线性阵列和环
4. 2. 2 格网
4. 2. 3 超立方体
4. 2. 4 成本分析
4. 3 全归约与前缀和操作
4. 4 散发和收集
4. 5 多对多私自通信
4. 5. 1 环
4. 5. 2 格网
4. 5. 3 超立方体
4. 6 循环移位
4. 6. 1 格网
4. 6. 2 超立方体
4. 7 提高某些通信操作的速度
4. 7. 1 消息分裂和路由选择
4. 7. 2 全端口通信
4. 8 小结
4. 9 书目评注
习题
第5章 并行程序的解析建模
5. 1 并行程序中的开销来源
5. 2 并行系统的性能度量
5. 2. 1 执行时间
5. 2. 2 总并行开销
5. 2. 3 加速比
5. 2. 4 效率
5. 2. 5 成本
5. 3 粒度对性能的影响
5. 4 并行系统的可扩展性
5. 4. 1 并行程序的扩展特性
5. 4. 2 可扩展性的等效率度量
5. 4. 3 成本最优性和等效率函数
5. 4. 4 等效率函数的下界
5. 4. 5 并发度和等效率函数
5. 5 最小执行时间和最小成本
最优执行时间
5. 6 并行程序渐近分析
5. 7 其他可扩展性的度量
5. 8 书目评注
习题
第6章 使用消息传递模式编程
6. 1 消息传递编程的原理
6. 2 操作构件：发送和接收操作
6. 2. 1 阻塞式消息传递操作
6. 2. 2 无阻塞式消息传递操作
6. 3 MPI：消息传递接口
6. 3. 1 启动和终止MPI库
6. 3. 2 通信器
6. 3. 3 获取信息
6. 3. 4 发送和接收消息
6. 3. 5 实例：奇偶排序
6. 4 拓扑结构与嵌入
6. 4. 1 创建和使用笛卡儿拓扑结构
6. 4. 2 实例：Cannon的矩阵与矩阵相乘
6. 5 计算与通信重叠
6. 6 聚合的通信和计算操作
6. 6. 1 障碍
6. 6. 2 广播
6. 6. 3 归约
6. 6. 4 前缀
6. 6. 5 收集
6. 6. 6 散发
6. 6. 7 多对多
6. 6. 8 实例：一维矩阵与向量相乘
6. 6. 9 实例：单源最短路径
6. 6. 10 实例：样本排序
6. 7 进程组和通信器
6. 8 书目评注
习题
第7章 共享地址空间平台的编程
7. 1 线程基础
7. 2 为什么要用线程
7. 3 POSIX线程API
7. 4 线程基础：创建和终止
7. 5 Pthreads中的同步原语
7. 5. 1 共享变量的互斥
7. 5. 2 用于同步的条件变量
7. 6 控制线程及同步的属性
7. 6. 1 线程的属性对象
7. 6. 2 互斥锁的属性对象
7. 7 线程注销
7. 8 复合同步结构
7. 8. 1 读-写锁
7. 8. 2 障碍
7. 9 设计异步程序的技巧
7. 10 OpenMP：基于命令的并行
编程标准
7. 10. 1 OpenMP编程模型
7. 10. 2 在OpenMP中指定并发任务
7. 10. 3 OpenMP中的同步结构
7. 10. 4 OpenMP中的数据处理
7. 10. 5 OpenMP库函数
7. 10. 6 OpenMP中的环境变量
7. 10. 7 显式线程与基于OpenMP编程
的比较
7. 11 书目评注
习题
第8章 稠密矩阵算法
8. 1 矩阵向量乘法
8. 1. 1 一维行划分
8. 1. 2 二维划分
8. 2 矩阵与矩阵的乘法
8. 2. 1 简单的并行算法
8. 2. 2 Cannon算法
8. 2. 3 DNS算法
8. 3 线性方程组求解
8. 3. 1 简单高斯消元算法
8. 3. 2 带部分主元选择的高斯消元算法
8. 3. 3 求解三角系统：回代法
8. 3. 4 求解线性方程组时的数值因素
8. 4 书目评注
习题
第9章 排序
9. 1 并行计算机中的排序问题
9. 1. 1 输入输出序列的存放位置
9. 1. 2 如何进行比较
9. 2 排序网络
9. 2. 1 双调排序
9. 2. 2 将双调排序映射到超立方体
和格网
9. 3 冒泡排序及其变体
9. 3. 1 奇偶转换
9. 3. 2 希尔排序
9. 4 快速排序
9. 4. 1 并行快速排序
9. 4. 2 用于CRCWPRAM的并行形式
9. 4. 3 用于实际体系结构的并行形式
9. 4. 4 主元选择
9. 5 桶和样本排序
9. 6 其他排序算法
9. 6. 1 枚举排序
9. 6. 2 基数排序
9. 7 书目评注
习题
第10章 图算法
10. 1 定义和表示
10. 2 最小生成树：Prim算法
10. 3 单源最短路径：Dijkstra算法
10. 4 全部顶点对间的最短路径
10. 4. 1 Dijkstra算法
10. 4. 2 Floyd算法
10. 4. 3 性能比较
10. 5 传递闭包
10. 6 连通分量
10. 7 稀疏图算法
10. 7. 1 查找最大独立集
10. 7. 2 单源最短路径
10. 8 书目评注
习题
第11章 离散优化问题的搜索算法
11. 1 定义与实例
11. 2 顺序搜索算法
11. 2. 1 深度优先搜索算法
11. 2. 2 最佳优先搜索算法
11. 3 搜索开销因子
11. 4 并行深度优先搜索
11. 4. 1 并行DFS的重要参数
11. 4. 2 并行DFS分析的一般框架
11. 4. 3 负载平衡方案分析
11. 4. 4 终止检测
11. 4. 5 试验结果
11. 4. 6 深度优先分支定界搜索的
并行形式
11. 4. 7 IDA*的并行形式
11. 5 并行最佳优先搜索
11. 6 并行搜索算法的加速比异常
11. 7 书目评注
习题
第12章 动态规划
12. 1 动态规划概述
12. 2 串行一元DP形式
12. 2. 1 最短路径问题
12. 2. 2 0／1背包问题
12. 3 非串行一元DP形式
12. 4 串行多元DP形式
12. 5 非串行多元DP形式
12. 6 综述与讨论
12. 7 书目评注
习题
第13章 快速傅里叶变换
13. 1 串行算法
13. 2 二进制交换算法
13. 2. 1 全带宽网络
13. 2. 2 有限带宽网络
13. 2. 3 并行快速傅里叶变换中的
额外计算
13. 3 转置算法
13. 3. 1 二维转置算法
13. 3. 2 转置算法的推广
13. 4 书目评注
习题
附录A 函数的复杂度与阶次分析
索引
鄂公网安备 42010302001612号 