并行计算

本书系统介绍了三代并行计算模型，包括共享存储并行计算模型、分布式存储并行计算模型和存储层次并行计算模型，并介绍了大量针对并行计算模型的算法。此外，本书还介绍了并行程序性能模型以及并发和分布式算法。书中算法和语言力求精简明确，部分章节最后配备习题，并有注释和大量参考文献。

张云泉，博士，中科院计算所研究员，博导。2000年于中科院软件所获计算机软件与理论专业工学博士学位。主要研究方向为大数据并行处理、“并行程序没汁和性能评价、并行计算和并行编程模型等。已在国内外学术刊物上发表论文近二百篇，泽著三部。曾获国家科技进步奖二等奖一项，获中科院科技进步二等奖一项，获2000年度中科院院长奖学金优秀奖，获得中科院软件所首批杰出青年人才专项汁划支持。他是国家自然科学基金委第十四届信息科学部专家评审组成员，任中国汁算机学会Y0csEF学术委员会主席（2010～2011年）、中国软件行业协会常务理事/数学软件分会秘书长、中国汁算机学会常务理事，高性能汁算专业委员会秘书长、大数据专家委员会副秘书长。他还是中国高性能计算机TOP100排行榜创始人和发布者，果壳网科学顾问，《光明日报》科普专家委员会委员，青海省火数据与云计算咨询专家委员会委员。
袁良，博士，中科院计算所助研。主要研究方向为并行计算模型和并行数值算法优化。

前言
第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..2.2FFT
2.3.3前缀和
2.4线性阵列
2.4.1定义
2.4.2排序
2.4.3三角矩阵求解
2.5混洗连接
2.5.1定义
2.5.2排序
2.5.3FFT
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.1PRAM模型
3.1.1定义
3.1.2模型的能力
3.1.3算法设计技术
3.1.4问题下界
3.2PRAM变体
3.2.1APRAM
3.2.2分相PRAM
3.3选择
3.3.1EREW上的成本最优算法
3.3.2CRCW上的常数时间算法
3.3.3缩减处理器
3.3.4算法级联
3.3.5下界
3.4归并
3.4.1CREW上的常数时间算法
3.4.2缩减处理器
3.5查找
3.5.1CREW上的最优时间算法
3.5.2下界
3.6排序
3.6.1枚举排序
3.6.2Preparata排序
3.6.3下界
3.7前缀和
3.7.1倍增法
3.7.2算法级联
3.8图算法
3.8.1分层倍增法
3.8.2欧拉回路
3.8.3Ear分解
3.8.4破对称方法
3.9小结
3.10习题
第4章分布式存储并行计算模型(通信复杂度)
4.1通信复杂度模型
4.1.1LPRAM模型
4.1.2Yao模型
4.2延迟带宽模型
4.2.1LogP模型
4.2.2Postal模型
4.2.3LogGP模型
4.3其他模型
4.3.1BSP
4.3.2QSM
4.3.3BPRAM模型
4.4小结
第5章存储层次并行计算模型(存储复杂度)
5.1单层存储层次
5.2两层存储层次
5.2.1红蓝卵石模型
5.2.2分块传输模型
5.3多层存储层次
5.3.1多层卵石模型
5.3.2HMM
5.3.3分块HMM
5.3.4RAM(h)模型
5.4缓存无关模型
5.4.1串行模型
5.4.2并行模型
5.5小结
5.6习题
第6章并行程序性能模型
6.1性能模型与计算模型
6.2加速比模型
6.2.1Amdahl模型
6.2.2Gustafson模型
6.2.3Karp-Flatt模型
6.2.4Sun-Ni模型
6.2.5等效率模型
6.2.6DAG模型
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.4Hill-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习题
参考文献