并行計算：模型與算法

目錄
前言
第1章緒論1
1.1模型1
1.1.1白盒模型1
1.1.2黑盒模型2
1.2計算模型3
1.2.1計算能力模型3
1.2.2算法設(shè)計模型7
1.3并行計算模型8
1.3.1基本度量參數(shù)9
1.3.2基本并行計算模型11
1.4相關(guān)概念13
1.4.1系統(tǒng)結(jié)構(gòu)模型13
1.4.2并行編程模型18
1.4.3并行編程模式22
1.4.4基準測試程序23
1.4.5數(shù)據(jù)一致性模型25
1.4.6并行、并發(fā)與分布式27
1.5并行算法設(shè)計30
1.5.1并行算法表示30
1.5.2算法復雜度31
1.5.3問題31
1.6小結(jié)33
第2章固定結(jié)構(gòu)并行計算模型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代數(shù)電路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矩陣轉(zhuǎn)置62
2.6網(wǎng)格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小結(jié)79
2.10習題80
第3章共享存儲并行計算模型(計算復雜度)83
3.1PRAM模型83
3.1.1定義83
3.1.2模型的能力84
3.1.3算法設(shè)計技術(shù)85
3.1.4問題下界85
3.2PRAM變體86
3.2.1APRAM86
3.2.2分相PRAM87
3.3選擇88
3.3.1EREW上的成本最優(yōu)算法88
3.3.2CRCW上的常數(shù)時間算法89
3.3.3縮減處理器90
3.3.4算法級聯(lián)91
3.3.5下界92
3.4歸并93
3.4.1CREW上的常數(shù)時間算法93
3.4.2縮減處理器94
3.5查找95
3.5.1CREW上的最優(yōu)時間算法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算法級聯(lián)98
3.8圖算法99
3.8.1分層倍增法99
3.8.2歐拉回路101
3.8.3Ear分解103
3.8.4破對稱方法104
3.9小結(jié)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小結(jié)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緩存無關(guān)模型133
5.4.1串行模型134
5.4.2并行模型136
5.5小結(jié)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軟硬協(xié)同模型151
6.4.1計算密集度151
6.4.2串行平衡模型152
6.4.3并行平衡模型152
6.4.4Hill-Marty模型153
6.5算法優(yōu)化模型154
6.5.1算法級聯(lián)154
6.5.2參數(shù)優(yōu)化155
6.6小結(jié)156
第7章并發(fā)與分布式算法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小結(jié)189
7.7習題189
參考文獻191