第1章 绪论

1.1 模型

1.1.1 白盒模型

1.1.2 黑盒模型

1.2 计算模型

1.2.1 计算能力模型

1.2.2 算法设计模型

1.3 并行计算模型

1.3.1 基本度量参数

1.3.2 基本并行计算模型

1.4 相关概念

1.4.1 系统结构模型

1.4.2 并行编程模型

1.4.3 并行编程模式

1.4.4 基准测试程序

1.4.5 数据一致性模型

1.4.6 并行、并发与分布式

1.5 并行算法设计

1.5.1 并行算法表示

1.5.2 算法复杂度

1.5.3 问题

1.6 小结

第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 FFT

2.3.3 前缀和

2.4 线性阵列

2.4.1 定义

2.4.2 排序

2.4.3 三角矩阵求解

2.5 混洗连接

2.5.1 定义

2.5.2 排序

2.5.3 FFT

2.5.4 矩阵转置

2.6 网格

2.6.1 定义

2.6.2 归并

2.6.3 排序

2.6.4 矩阵乘

2.6.5 迭代法

2.7 树形

2.7.1 定义

2.7.2 排序

2.7.3 前缀和

2.7.4 图的连通分量

2.8 超立方

2.8.1 定义

2.8.2 排序

2.8.3 通信

2.9 小结

2.10 习题

第3章 共享存储并行计算模型（计算复杂度）

3.1 PRAM模型

3.1.1 定义

3.1.2 模型的能力

3.1.3 算法设计技术

3.1.4 问题下界

3.2 PRAM变体

3.2.1 APRAM

3.2.2 分相PRAM

3.3 选择

3.3.1 EREW上的成本最优算法

3.3.2 CRCW上的常数时间算法

3.3.3 缩减处理器

3.3.4 算法级联

3.3.5 下界

3.4 归并

3.4.1 CREW上的常数时间算法

3.4.2 缩减处理器

3.5 查找

3.5.1 CREW上的最优时间算法

3.5.2 下界

3.6 排序

3.6.1 枚举排序

3.6.2 Preparata排序

3.6.3 下界

3.7 前缀和

3.7.1 倍增法

3.7.2 算法级联

3.8 图算法

3.8.1 分层倍增法

3.8.2 欧拉回路

3.8.3 Ear分解

3.8.4 破对称方法

3.9 小结

3.10 习题

第4章 分布式存储并行计算模型（通信复杂度）

4.1 通信复杂度模型

4.1.1 LPRAM模型

4.1.2 Yao模型

4.2 延迟带宽模型

4.2.1 LogP模型

4.2.2 Postal模型

4.2.3 LogGP模型

4.3 其他模型

4.3.1 BSP

4.3.2 QSM

4.3.3 BPRAM模型

4.4 小结

第5章 存储层次并行计算模型（存储复杂度）

5.1 单层存储层次

5.2 两层存储层次

5.2.1 红蓝卵石模型

5.2.2 分块传输模型

5.3 多层存储层次

5.3.1 多层卵石模型

5.3.2 HMM

5.3.3 分块HMM

5.3.4 RAM（h）模型

5.4 缓存无关模型

5.4.1 串行模型

5.4.2 并行模型

5.5 小结

5.6 习题

第6章 并行程序性能模型

6.1 性能模型与计算模型

6.2 加速比模型

6.2.1 Amdahl模型

6.2.2 Gustafson模型

6.2.3 Karp-Flatt模型

6.2.4 Sun-Ni模型

6.2.5 等效率模型

6.2.6 DAG模型

6.3 访存序列模型

6.3.1 缺失率

6.3.2 重用距离

6.3.3 平均足迹

6.3.4 多进程模型

6.4 软硬协同模型

6.4.1 计算密集度

6.4.2 串行平衡模型

6.4.3 并行平衡模型

6.4.4 Hill-Marty模型

6.5 算法优化模型

6.5.1 算法级联

6.5.2 参数优化

6.6 小结

第7章 并发与分布式算法

7.1 互斥算法

7.1.1 共享存储算法

7.1.2 分布式存储算法

7.1.3 基于硬件操作

7.1.4 基于信号量操作

7.2 锁算法

7.2.1 自旋锁

7.2.2 读写锁

7.3 同步算法

7.3.1 分布式存储算法

7.3.2 共享存储算法

7.4 队列算法

7.4.1 有界队列

7.4.2 无界队列

7.5 广播算法

7.5.1 洪水算法

7.5.2 生成树算法

7.6 小结

7.7 习题

参考文献