本书系统地介绍了三代并行计算模型，包括共享存储并行计算模型、分布式存储并行计算模型和存储层次并行计算模型，并讨论了大量针对并行计算模型的算法。此外，本书还介绍了并行程序性能模型以及并发和分布式算法。书中算法和语言力求精简明确，部分章节最后配备习题，有助于读者巩固所学知识，书中的注释和大量参考文献也便于读者进一步深入提高。

高性能计算专家潜心撰写，融合作者多年并行计算技术研究成果
计算模型丰富，计算复杂度、通信复杂度、存储复杂度面面俱到
直指算法设计精髓，综合考虑技术的先进性和实用性

本书系统介绍了三代并行计算模型及其并行算法、并行程序性能模型以及并发和分布式算法，书中算法均用精简的伪码实现，利于读者掌握最为精髓的并行算法设计思路。
本书特点
结合具体算法，展现并行计算技术的魅力，书中的许多内容来源于作者的科研和工作成果。
前沿、实用的内容，总结了并行算法的新技术和新理念，梳理了当前并行计算中的模型和算法。
清晰、严谨的叙述，针对并行计算中的主要方法，从原理、算法等多个角度进行阐述，讲解算法设计精髓。
作者简介
张云泉　博士，中科院计算所研究员，博导。2000年于中科院软件所获计算机软件与理论专业工学博士学位。主要研究方向为大数据并行处理、并行程序设计和性能评价、并行计算和并行编程模型等。已在国内外学术刊物上发表论文近二百篇，译著三部。曾获国家科技进步奖二等奖一项，获中科院科技进步二等奖一项，获2000年度中科院院长奖学金优秀奖，获得中科院软件所首批杰出青年人才专项计划支持。他是国家自然科学基金委第十四届信息科学部专家评审组成员，任中国计算机学会YOCSEF学术委员会主席(2010~2011年)、中国软件行业协会常务理事/数学软件分会秘书长、中国计算机学会常务理事/高性能计算专业委员会秘书长、大数据专家委员会副秘书长。他还是中国高性能计算机TOP100排行榜创始人和发布者，果壳网科学顾问，《光明日报》科普专家委员会委员，青海省大数据与云计算咨询专家委员会委员。
袁良　博士，中科院计算所助研。主要研究方向为并行计算模型和并行数值算法优化。

内容简介
第1章是绪论，首先对模型、计算模型和并行计算模型进行简要介绍，然后介绍并行计算领域中的一些相关概念，以及本书所用到的并行算法表述方法和问题定义；第2章介绍固定结构并行计算模型，抽象程度相对较低，是后续章节的基础，重点讨论处理器构成的固定结构网络的计算性能；第3章介绍共享存储并行计算模型，重点讨论计算复杂度；第4章介绍分布式存储并行计算模型，着重讨论通信复杂度；第5章介绍存储层次并行计算模型，重点关注存储复杂度；第6章综合讨论并行程序的性能模型；第7章讨论并发与分布式算法。

处理器是计算机系统的核心。由于摩尔定律的作用，对于体系结构的设计可以利用更多数量的晶体管来开发并行性，这使得处理器性能在2005年之前一直保持指数级增长，并且程序无须改变即可享用“免费的午餐”。但是，首先，时钟频率的提升已逼近物理极限，无法像以前一样从升级的高频单核处理器中获得免费的性能提升；其次，指令级并行，例如超标量发射和流水线技术对性能提升的潜力已基本发挥到极致，多年来没有更为显著的技术突破；最后，数据级并行，例如处理器的单指令多数据(SIMD)指令集，可以在一定程度上继续增加处理器的绝对峰值性能，但受限于带宽和片上硬件的资源，以及算法和编译的软件优化难度。总之，多核、众核处理器等利用线程级并行继续提升片上计算能力的方法已成为硬件发展的唯一道路。
算法是计算机科学的核心。由上所述，处理器体系结构的趋势是更多地利用线程级并行性，这一转变使得程序员必须设计过去只有在大型并行系统上才用到的并行算法，才能充分利用硬件计算能力。串行算法教科书通常使用RAM作为串行计算模型，并多以具体问题（排序、图算法、字符串等）或算法设计技巧（分而治之、动态规划、随机方法等）来组织内容。但并行算法的设计与底层并行机制紧密相关，因此我们以并行计算模型组织本书内容。首先，不同的模型适用于不同的问题；其次，对于同一问题在不同模型下从不同角度研究算法特征。
好算法不言自明，这是撰写本书时的核心思想。Knuth认为计算机程序设计是一门艺术而非科学，因此每个好算法都是一件精美的艺术品。相比于文字解释，作者相信使用精致优美的伪码表述的算法能进行自我说明，是艺术品最原始、最真实的展现。我们鼓励读者以算法伪码为中心阅读本书，而将文字看作对伪码的简要说明。然而，限于作者水平，加之时间仓促，书中定有不少欠妥和错误之处，恳请读者批评指正。

计算机\并行计算

本书系统介绍了三代并行计算模型及其并行算法、并行程序性能模型以及并发和分布式算法，书中算法均用精简的伪码实现，利于读者掌握最为精髓的并行算法设计思路。
本书特点：
　　·结合具体算法，展现并行计算技术的魅力，书中的许多内容来源于作者的科研和工作成果。
　　·前沿、实用的内容，总结了并行算法的新技术和新理念，梳理了当前并行计算中的模型和算法。
　　·清晰、严谨的叙述，针对并行计算中的主要方法，从原理、算法等多个角度进行阐述，讲解算法设计精髓。

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

袁良，博士，中科院计算所助研。主要研究方向为并行计算模型和并行数值算法优化。

前言
第1章绪论1
1.1模型1
1.1.1白盒模型1
1.1.2黑盒模型2
1.2计算模型3
1.2.1计算能力模型3
1.2.2算法设计模型7
1.3并行计算模型8
1.3.1基本度量参数9
1.3.2基本并行计算模型11
1.4相关概念13
1.4.1系统结构模型13
1.4.2并行编程模型18
1.4.3并行编程模式22
1.4.4基准测试程序23
1.4.5数据一致性模型25
1.4.6并行、并发与分布式27
1.5并行算法设计30
1.5.1并行算法表示30
1.5.2算法复杂度31
1.5.3问题31
1.6小结33
第2章固定结构并行计算模型34
2.1逻辑电路35
2.1.1定义35
2.1.2加法器35
2.2比较器电路39
2.2.1定义39
2.2.2归并39
2.2.3排序44
2.2.4选择46
2.3代数电路48
2.3.1定义48
2.3.2FFT48
2.3.3前缀和51
2.4线性阵列53
2.4.1定义53
2.4.2排序54
2.4.3三角矩阵求解57
2.5混洗连接59
2.5.1定义59
2.5.2排序60
2.5.3FFT62
2.5.4矩阵转置62
2.6网格64
2.6.1定义64
2.6.2归并64
2.6.3排序66
2.6.4矩阵乘68
2.6.5迭代法70
2.7树形71
2.7.1定义71
2.7.2排序73
2.7.3前缀和74
2.7.4图的连通分量75
2.8超立方76
2.8.1定义76
2.8.2排序77
2.8.3通信78
2.9小结79
2.10习题80
第3章共享存储并行计算模型(计算复杂度)83
3.1PRAM模型83
3.1.1定义83
3.1.2模型的能力84
3.1.3算法设计技术85
3.1.4问题下界85
3.2PRAM变体86
3.2.1APRAM86
3.2.2分相PRAM87
3.3选择88
3.3.1EREW上的成本最优算法88
3.3.2CRCW上的常数时间算法89
3.3.3缩减处理器90
3.3.4算法级联91
3.3.5下界92
3.4归并93
3.4.1CREW上的常数时间算法93
3.4.2缩减处理器94
3.5查找95
3.5.1CREW上的最优时间算法95
3.5.2下界95
3.6排序95
3.6.1枚举排序96
3.6.2Preparata排序96
3.6.3下界97
3.7前缀和98
3.7.1倍增法98
3.7.2算法级联98
3.8图算法99
3.8.1分层倍增法99
3.8.2欧拉回路101
3.8.3Ear分解103
3.8.4破对称方法104
3.9小结105
3.10习题106
第4章分布式存储并行计算模型(通信复杂度)107
4.1通信复杂度模型107
4.1.1LPRAM模型107
4.1.2Yao模型109
4.2延迟带宽模型110
4.2.1LogP模型110
4.2.2Postal模型111
4.2.3LogGP模型115
4.3其他模型116
4.3.1BSP116
4.3.2QSM116
4.3.3BPRAM模型117
4.4小结117
第5章存储层次并行计算模型(存储复杂度)118
5.1单层存储层次118
5.2两层存储层次121
5.2.1红蓝卵石模型121
5.2.2分块传输模型124
5.3多层存储层次126
5.3.1多层卵石模型127
5.3.2HMM128
5.3.3分块HMM131
5.3.4RAM(h)模型132
5.4缓存无关模型133
5.4.1串行模型134
5.4.2并行模型136
5.5小结138
5.6习题139
第6章并行程序性能模型141
6.1性能模型与计算模型141
6.2加速比模型142
6.2.1Amdahl模型142
6.2.2Gustafson模型142
6.2.3Karp-Flatt模型144
6.2.4Sun-Ni模型145
6.2.5等效率模型145
6.2.6DAG模型146
6.3访存序列模型147
6.3.1缺失率147
6.3.2重用距离148
6.3.3平均足迹149
6.3.4多进程模型150
6.4软硬协同模型151
6.4.1计算密集度151
6.4.2串行平衡模型152
6.4.3并行平衡模型152
6.4.4Hill-Marty模型153
6.5算法优化模型154
6.5.1算法级联154
6.5.2参数优化155
6.6小结156
第7章并发与分布式算法157
7.1互斥算法157
7.1.1共享存储算法157
7.1.2分布式存储算法164
7.1.3基于硬件操作170
7.1.4基于信号量操作172
7.2锁算法174
7.2.1自旋锁174
7.2.2读写锁177
7.3同步算法179
7.3.1分布式存储算法179
7.3.2共享存储算法181
7.4队列算法183
7.4.1有界队列184
7.4.2无界队列185
7.5广播算法188
7.5.1洪水算法188
7.5.2生成树算法188
7.6小结189
7.7习题189
参考文献191