前言
第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

前言/序言

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

并行计算：模型与算法下载 mobi epub pdf txt 电子书格式