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