結(jié)構(gòu)化并行程序設(shè)計(jì)：高效計(jì)算模式

目　　錄
Structured Parallel Programming: Patterns for Efficient Computation
譯者序
前言
寫在前面
第1章　導(dǎo)論 1
1.1　并行思維 2
1.2　性能 3
1.3　動(dòng)機(jī)：無(wú)處不在的并行 6
1.3.1　硬件發(fā)展推進(jìn)并行化 6
1.3.2　并行化的歷史趨勢(shì) 8
1.3.3　顯式并行編程的需求 12
1.4　基于模式的結(jié)構(gòu)化編程 15
1.5　并行編程模型 16
1.5.1　理想特征 16
1.5.2　用抽象代替具體 17
1.5.3　規(guī)則數(shù)據(jù)并行 18
1.5.4　可組合性 21
1.5.5　功能可移植性 21
1.5.6　性能可移植性 22
1.5.7　安全性、確定性和可維護(hù)性 22
1.5.8　編程模型概述 23
1.5.9　何時(shí)使用模型 28
1.6　本書的結(jié)構(gòu) 29
1.7　小結(jié) 29
第2章　背景知識(shí) 31
2.1　名詞和符號(hào) 31
2.2　策略 31
2.3　機(jī)制 33
2.4　計(jì)算機(jī)模型 35
2.4.1　計(jì)算機(jī)模型概述 35
2.4.2　影響性能的關(guān)鍵因素 39
2.4.3　Flynn分類法 41
2.4.4　革新 42
2.5　性能理論 43
2.5.1　延遲和吞吐量 44
2.5.2　加速比、效率和可擴(kuò)展性 44
2.5.3　功耗 45
2.5.4　Amdahl定律 46
2.5.5　Gustafson-Barsis定律 48
2.5.6　工作量–跨度模型 49
2.5.7　漸近復(fù)雜度 51
2.5.8　漸近加速比和漸近效率 52
2.5.9　Little公式 53
2.6　并行陷阱 54
2.6.1　競(jìng)態(tài)條件 54
2.6.2　互斥和鎖 55
2.6.3　死鎖 56
2.6.4　擴(kuò)展性抑制 57
2.6.5　局部性不足 57
2.6.6　負(fù)載不均衡 58
2.6.7　額外開銷 58
2.7　小結(jié) 59
第一部分　模式
第3章　模式概述 62
3.1　嵌套模式 63
3.2　結(jié)構(gòu)化串行控制流模式 64
3.2.1　序列 64
3.2.2　選擇 65
3.2.3　迭代 66
3.2.4　遞歸 68
3.3　并行控制模式 68
3.3.1　Fork-Join 68
3.3.2　映射 68
3.3.3　模板 69
3.3.4　歸約 70
3.3.5　掃描 71
3.3.6　遞推 73
3.4　串行數(shù)據(jù)管理模式 74
3.4.1　隨機(jī)讀寫 74
3.4.2　棧分配 74
3.4.3　堆分配 75
3.4.4　閉包 75
3.4.5　對(duì)象 75
3.5　并行數(shù)據(jù)管理模式 76
3.5.1　打包 76
3.5.2　流水線 76
3.5.3　幾何分解 77
3.5.4　聚合 78
3.5.5　散發(fā) 78
3.6　其他并行模式 79
3.6.1　超標(biāo)量序列 79
3.6.2　期貨 80
3.6.3　投機(jī)選擇 80
3.6.4　工作堆 81
3.6.5　搜索 81
3.6.6　切片 81
3.6.7　展開 81
3.6.8　分類歸約 82
3.6.9　項(xiàng)圖重寫 83
3.7　非確定性模式 83
3.7.1　分支限界 83
3.7.2　事務(wù) 84
3.8　編程模型對(duì)模式的支持 84
3.8.1　Cilk Plus 86
3.8.2　線程構(gòu)建塊 87
3.8.3　OpenMP 88
3.8.4　陣列構(gòu)建塊 89
3.8.5　OpenCL 90
3.9　小結(jié) 91
第4章　映射 92
4.1　概述 93
4.2　帶縮放系數(shù)的向量加法 94
4.2.1　問題描述 94
4.2.2　串行實(shí)現(xiàn) 95
4.2.3　TBB實(shí)現(xiàn) 96
4.2.4　Cilk Plus實(shí)現(xiàn) 96
4.2.5　使用數(shù)組符號(hào)的Cilk Plus實(shí)現(xiàn) 97
4.2.6　OpenMP實(shí)現(xiàn) 97
4.2.7　使用向量操作的ArBB實(shí)現(xiàn) 97
4.2.8　使用元素函數(shù)的ArBB實(shí)現(xiàn) 98
4.2.9　OpenCL實(shí)現(xiàn) 99
4.3　芒德布羅分形圖 100
4.3.1　問題描述 100
4.3.2　串行實(shí)現(xiàn) 100
4.3.3　TBB實(shí)現(xiàn) 101
4.3.4　Cilk Plus實(shí)現(xiàn) 101
4.3.5　使用數(shù)組符號(hào)的Cilk Plus實(shí)現(xiàn) 101
4.3.6　OpenMP實(shí)現(xiàn) 103
4.3.7　ArBB實(shí)現(xiàn) 103
4.3.8　OpenCL實(shí)現(xiàn) 104
4.4　映射的序列和序列的映射 105
4.5　并行模型的對(duì)比 107
4.6　相關(guān)模式 107
4.6.1　模板 107
4.6.2　工作堆 108
4.6.3　分治 108
4.7　小結(jié) 108
第5章　集合 109
5.1　歸約 109
5.1.1　計(jì)算重排序 110
5.1.2　向量化 111
5.1.3　分塊 112
5.1.4　精度 113
5.1.5　實(shí)現(xiàn) 113
5.2　映射和歸約的融合 114
5.2.1　TBB中的顯式融合 115
5.2.2　Cilk Plus中的顯式融合 115
5.2.3　ArBB中的自動(dòng)融合 115
5.3　點(diǎn)積 115
5.3.1　問題描述 115
5.3.2　串行實(shí)現(xiàn) 116
5.3.3　SEE內(nèi)聯(lián)函數(shù)實(shí)現(xiàn) 116
5.3.4　TBB實(shí)現(xiàn) 117
5.3.5　Cilk Plus實(shí)現(xiàn) 119
5.3.6　OpenMP實(shí)現(xiàn) 120
5.3.7　ArBB實(shí)現(xiàn) 121
5.4　掃描 122
5.4.1　Cilk Plus 123
5.4.2　TBB 124
5.4.3　ArBB 124
5.4.4　OpenMP 124
5.5　映射和掃描的融合 127
5.6　積分 127
5.6.1　問題描述 128
5.6.2　串行實(shí)現(xiàn) 128
5.6.3　Cilk Plus實(shí)現(xiàn) 130
5.6.4　OpenMP實(shí)現(xiàn) 130
5.6.5　TBB實(shí)現(xiàn) 131
5.6.6　ArBB實(shí)現(xiàn) 132
5.7　小結(jié) 134
第6章　數(shù)據(jù)重組 135
6.1　聚合 135
6.1.1　常規(guī)聚合 135
6.1.2　移位 137
6.1.3　拉合 137
6.2　散發(fā) 138
6.2.1　原子散發(fā) 139
6.2.2　排列散發(fā) 139
6.2.3　歸并散發(fā) 139
6.2.4　優(yōu)先散發(fā) 140
6.3　將散發(fā)轉(zhuǎn)換為聚合 140
6.4　打包 141
6.5　映射和打包的融合 142
6.6　幾何分解和分區(qū) 143
6.7　結(jié)構(gòu)的數(shù)組和數(shù)組的結(jié)構(gòu) 145
6.8　小結(jié) 148
第7章　模板和遞推 149
7.1　模板 149
7.2　用移位實(shí)現(xiàn)模板 151
7.3　針對(duì)緩存的分塊式模板 151
7.4　模板通信優(yōu)化 152
7.5　遞推 153
7.6　小結(jié) 155
第8章　Fork-Join