并行计算：结构、算法、编程

第一篇 并行计算硬件基础

第一章 并行计算机系统及其结构模型

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. 3. 1 并行计算机结构模型

1. 3. 2 并行计算机访存模型

*1. 3. 3 并行计算机存储组织

1. 4 小结和导读

习题

第二章 当代并行机系统：SMP. MPP和COW

2. 1 对称多处理机SMP

2. 1. 1 SMP和CC-NUMA结构特性

*2. 1. 2 SGI／Cray Origin 2000超级服务器

2. 2 大规模并行机MPP

2. 2. 1 MPP结构特性

*2. 2. 2 机群型大规模并行机SP2

2. 3 工作站机群COW

2. 3. 1 COW的基本原理与技术

*2. 3. 2 Berkeley的NOW计划

2. 4 国产曙光系列并行机系统

2. 4. 1 全对称共享存储多处理机系统：曙光l号

2. 4. 2 大规模并行处理系统：曙光-1000

*2. 4. 3 超级并行计算机系统：曙光-2000

2. 5 小结和导读

习题

第三章 并行计算性能评测

3. 1 加速比性能定律

3. 1. 1 Amdahl定律

3. 1. 2 Gustafson定律

3. 1. 3 Sun和Ni定律

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. 3. 3 并行测试程序

3. 4 小结和导读

习题

第二篇 并行算法的设计

第四章 并行算法的设计基础

*4. 1 并行算法的基础知识

4. 1. 1 并行算法的定义和分类

4. 1. 2 并行算法的表达

4. 1. 3 并行算法的复杂性度量

4. 1. 4 并行算法中的同步与通信

4. 2 并行计算模型

4. 2. 1 PRAM模型

4. 2. 2 异步PRAM模型

4. 2. 3 BSP模型

4. 2. 4 logP模型

4. 2. 5 C3模型

4. 2. 6 对BSP和logP的评注

4. 3 小结和导读

习题

第五章 并行算法的一般设计方法

5. 1 串行算法的直接并行化

5. 1. 1 设计方法描述

5. 1. 2 快排序算法的并行化

5. 2 从问题描述开始设计并行算法

5. 2. 1 串匹配算法

*5. 2. 2 KMP串行串匹配算法

5. 2. 3 并行串匹配算法的设计思路

5. 3 借用已有算法求解新问题

5. 3. 1 设计方法描述

5. 3. 2 利用矩阵乘法求所有点对间最短路径

5. 4 小结和导读

习题

第六章 并行算法的基本设计技术

6. 1 划分设计技术

6. 1. 1 均匀划分技术

6. 1. 2 方根划分技术

6. 1. 3 对数划分技术

6. 1. 4 功能划分技术

6. 2 分治设计技术

6. 2. 1 双调归并网络

6. 2. 2 凸壳问题

6. 3 平衡树设计技术

6. 3. 1 求取最大值

6. 3. 2 计算前缀和

6. 4 倍增设计技术

6. 4. 1 表序问题的计算

6. 4. 2 求森林的根

6. 5 流水线设计技术

6. 5. 1 一维心动阵列上的DFT计算

6. 5. 2 一维心动阵列上的卷积计算

6. 6 小结和导读

习题

第七章 并行算法的一般设计过程

7. 1 PCAM设计方法学

7. 2 划分

7. 2. 1 域分解

7. 2. 2 功能分解

7. 2. 3 划分判据

7. 3 通信

7. 3. 1 局部通信

7. 3. 2 全局通信

7. 3. 3 非结构化. 动态和异步通信

7. 3. 4 通信判据

7. 4 组合

7. 4. 1 增加粒度

7. 4. 2 保持灵活性和减少软件工程成本

7. 4. 3 组合判据

7. 5 映射

7. 5. 1 负载平衡算法

7. 5. 2 任务调度算法

7. 5. 3 映射判据

7. 6 小结和导读

习题

第三篇 并行数值算法

第八章 基本通信操作

8. 1 选路方法与开关技术

8. 1. 1 选路方法

8. 1. 2 开关技术

8. 2 单一信包一到一传输

8. 3 一到多播送

8. 3. 1 使用SF进行一到多播送

8. 3. 2 使用CT进行一到多播送

8. 4 多到多播送

8. 4. 1 使用SF进行多到多播送

8. 4. 2 使用CT进行多到多播送

8. 5 小结和导读

习题

第九章 稠密矩阵运算

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 Cannon乘法

9. 4. 3 Fox乘法

9. 4. 4 DNS乘法

9. 5 小结和导读

习题

第十章 线性方程组的求解

10. 1 三角形方程组的求解

10. 1. 1 基本术语

10. 1. 2 上三角方程组的求解

10. 2 三对角方程组的求解

10. 2. 1 三对角方程组直接求解法

10. 2. 2 三对角方程组奇偶归约求解法

10. 3 稠密线性方程组的求解

10. 3. 1 有回代的高斯消去法

10. 3. 2 无回代的高斯-约旦法

10. 3. 3 迭代求解的高斯-赛德尔法

10. 4 稀疏线性方程组的求解

10. 4. 1 稀疏矩阵的存储方式

10. 4. 2 雅可比迭代法

10. 4. 3 高斯-赛德尔迭代法

10. 4. 4 超松弛迭代法

10. 4. 5 多重网格法

10. 4. 6 共扼梯度法

10. 5 小结和导读

习题

第十一章 快速傅里时变换

11. 1 离散傅氏变换

*11. 1. 1 预备知识

11. 1. 2 离散傅里叶变换

11. 1. 3 离散傅里叶逆变换

11. 1. 4 离散傅氏变换的蝶式计算

*11. 2 快速傅氏变换串行算法

11. 2. 1 串行FFT迭代算法

11. 2. 2 串行FFT递归算法

11. 3 并行FFT算法

11. 3. 1 SIMD一MC2上FFT算法

11. 3. 2 SIMD-BF上FFT算法

11. 3. 3　SIMD-CC上FFT算法

11. 3. 4 MIMD-DM上FFT算法

11. 4　小结和导读

习题

第四篇 并行程序设计

第十二章 并行程序设计基础

12. 1　并行程序设计概述

12. 1. 1 串行程序设计与并行程序设计

12. 1. 2　并行程序设计环境

12. 1. 3　并行程序设计方法

*12. 2 进程

12. 2. 1　进程的基本概念

12. 2. 2　进程的并行执行

12. 2. 3　进程的相互作用

12. 3 线程

12. 3. 1 线程的基本概念

12. 3. 2　线程的管理

12. 3. 3　线程的同步

*12. 4 同步

12. 4. 1　原子与互斥

12. 4. 2　高级同步结构

12. 4. 3　低级同步原语

12. 5 通信

12. 5. 1 影响通信系统性能的因素

12. 5. 2　低级通信支持

12. 5. 3　TCP／IP通信协议组简介

12. 6　小结和导读

习题

第十三章 并行程序设计模型和共享存储系统编程

13. 1 并行编程风范和样本程序

13. 1. 1 五种并行编程风范

13. 1. 2　计算∏样本程序

13. 2　并行程序设计模型

13. 2. 1 隐式并行模型

13. 2. 2　数据并行模型

13. 2. 3　消息传递模型

13. 2. 4　共享变量模型

13. 2. 5　并行程序设计模型比较

13. 3　共享存储并行编程

13. 3. 1　ANSIX3H5共享存储模型

13. 3. 2　POSIX线程模型

13. 3. 3　OpenMP标准

13. 4　小结和导读

习题

第十四章 分布存储系统并行编程

14. 1 基于消息传递的并行编程

14. 1. 1　SPMD并行程序

14. 1. 2　MPMD并行程序

14. 2　MPI并行编程

14. 2. 1 最基本的MPI

14. 2. 2 群体通信

14. 2. 3 通信体

14. 2. 4　导出数据类型

14. 2. 5　点到点通信

*14. 3 PVM并行编程

14. 3. 1　PVM概貌

14. 3. 2　PVM消息传递库

14. 4　基于数据并行的并行编程

14. 4. 1　数据并行模型的特点

14. 4. 2　数据并行编程的基本问题

14. 5　HPF并行编程

14. 5. 1　HPF的语言特点

14. 5. 2　HPF的数据并行机制

14. 5. 3　HPF使用中的若干问题

14. 6　小结和导读

习题

附录一　MPI的函数的C语言说明

附录二　MPI的函数的Fortran语言说明

第十五章 并行程序设计环境与工具

*15. 1 软件工具与环境

15. 1. 1 编码工具

15. 1. 2　软件工程工具

15. 1. 3　集成工具

15. 1. 4　将来的工具与环境

15. 2　并行编译器

15. 2. 1　编译及其并行化

15. 2. 2 相关分析

15. 2. 3 代码优化

15. 2. 4 代码生成

15. 3　并行程序调试和性能分析

15. 3. 1 并行程序的调试

15. 3. 2　并行程序的性能分析

15. 3. 3 并行程序的可视化设计环境与工具

15. 4　小结和导读

习题

算法索引

表格索引

示范程序索引

参考文献

并行与分布计算Web网址

术语中-英对照及索引