平行程式設計導論（原書第2版） An Introduction to Parallel Programming, 2/e

目　　錄
An Introduction to Parallel Programming, Second Edition
譯者序
前言
第1章　為什麼需要並行計算 1
1.1　為什麼需要不斷提升效能 1
1.2　為什麼需要建立平行系統 2
1.3　為什麼需要寫並行程式 2
1.4　如何寫平行程式 5
1.5　我們將做什麼 6
1.6　並發、並行與分佈式 7
1.7　本書其餘部分 8
1.8　一點警告 8
1.9　排版慣例 9
1.10　小結 9
1.11　練習 10
第2章　平行硬體與平行軟體 12
2.1　背景知識 12
2.1.1　馮諾依曼體系結構 12
2.1.2　進程、多任務和執行緒 13
2.2　馮諾依曼模型的改良 14
2.2.1　快取基礎 14
2.2.2　快取映射 16
2.2.3　快取和程序：範例 17
2.2.4　虛擬記憶體 18
2.2.5　指令級並行 19
2.2.6　硬體多執行緒 21
2.3　並行硬體 22
2.3.1　平行計算機的分類 22
2.3.2　SIMD系統 22
2.3.3　MIMD系統 24
2.3.4　互連網路 26
2.3.5　高速緩存一致性 30
2.3.6　共享記憶體與分散式記憶體 32
2.4　平行軟體 33
2.4.1　注意事項 33
2.4.2　協調進程/執行緒 33
2.4.3　共享記憶體 34
2.4.4　分散式記憶體 37
2.4.5　GPU編程 40
2.4.6　混合系統程式設計 40
2.5　輸入與輸出 41
2.5.1　MIMD系統 41
2.5.2　GPU 41
2.6　性能 42
2.6.1　在MIMD系統中的加速比和
效率 42
2.6.2　阿姆達定律 44
2.6.3　MIMD系統的可擴展性 45
2.6.4　MIMD程式的計時 46
2.6.5　GPU效能 48
2.7　平行程序設計 49
2.7.1　範例 49
2.8　編寫和運行並行程式 53
2.9　假設 53
2.10　小結 54
2.10.1　串列系統 54
2.10.2　並行硬體 55
2.10.3　平行軟體 56
2.10.4　輸入與輸出 57
2.10.5　性能 57
2.10.6　平行程序設計 58
2.10.7　假設 58
2.11　練習 58
第3章　基於MPI的分佈式
記憶體程式設計 62
3.1　入門 62
3.1.1　編譯與執行 63
3.1.2　MPI程序 64
3.1.3　MPI_Init和
MPI_Finalize 64
3.1.4　通訊域、MPI_Comm_size和MPI_Comm_rank 65
3.1.5　SPMD程序 66
3.1.6　通信 66
3.1.7　MPI_Send 66
3.1.8　MPI_Recv 67
3.1.9　訊息匹配 68
3.1.10　status_p參數 69
3.1.11　MPI_Send和MPI_Recv的
語意 69
3.1.12　一些潛在的陷阱 70
3.2　MPI中的梯形法則 70
3.2.1　梯形法則 70
3.2.2　梯形法則的平行化 71
3.3　處理I/O 74
3.3.1　輸出 74
3.3.2　輸入 75
3.4　集合通信 76
3.4.1　樹形結構的通訊 76
3.4.2　MPI_Reduce 77
3.4.3　集合通訊與點對點通訊 78
3.4.4　MPI_Allreduce 79
3.4.5　廣播 80
3.4.6　資料分佈 82
3.4.7　分散 83
3.4.8　收集 84
3.4.9　綜合實例 85
3.5　MPI派生的資料型態 88
3.6　MPI程序的性能評估 91
3.6.1　計時 91
3.6.2　結果 93
3.6.3　加速比和效率 95
3.6.4　可擴展性 95
3.7　一種平行排序演算法 96
3.7.1　一些簡單的串列排序演算法 96
3.7.2　並行奇偶移項排序 98
3.7.3　MPI程序中的安全性 100
3.7.4　關於平行奇偶排序的一些
補充細節 102
3.8　小結 103
3.9　練習 106
3.10　程式設計作業 112
第4章　Pthreads共享記憶體程式設計 114
4.1　進程、執行緒與Pthreads 114
4.2　Hello, world 115
4.2.1　執行 116
4.2.2　預備 117
4.2.3　啟動線程 117
4.2.4　運行執行緒 119
4.2.5　停止線程 120
4.2.6　錯誤檢查 120
4.2.7　啟動執行緒的其他方法 120
4.3　矩陣-向量乘法 121
4.4　臨界區 123
4.5　忙等待 126
4.6　互斥鎖 128
4.7　生產者-消費者同步與信號量 131
4.8　柵欄與條件變數 135
4.8.1　忙等待與互斥鎖 135
4.8.2　信號量 136
4.8.3　條件變數 137
4.8.4　Pthreads柵欄 139
4.9　讀寫鎖 139
4.9.1　排序的鍊錶函數 140
4.9.2　多執行緒鍊錶 142
4.9.3　Pthreads的讀寫鎖 144
4.9.4　各種實現方案的性能 145
4.9.5　實作讀寫鎖定 146
4.10　快取、快取一致性與偽共享 147
4.11　線程安全 150
4.11.1　不正確的程序可以產生
正確的輸出 153
4.12　小結 153
4.13　練習 154
4.14　程式設計作業 159
第5章　OpenMP共享記憶體程式設計 161
5.1　入門 162
5.1.1　編譯並執行OpenMP程式 163
5.1.2　程序 163
5.1.3　錯誤檢查 165
5.2　梯形法則 166
5.2.1　第一個OpenMP版本 166
5.3　變數的作用域 170
5.4　歸約子句 170
5.5　parallel指令 173
5.5.1　注意事項 174
5.5.2　資料依賴性 175
5.5.3　尋找循環迭代相關 176
5.5.4　估算π 176
5.5.5　關於作用域的更多內容 178
5.6　關於OpenMP中的循環的更多
內容：排序 179
5.6.1　冒泡排序 179
5.6.2　奇偶移項排序 180
5.7　循環的調度 182
5.7.1　schedule子句 183
5.7.2　static調度類型 185
5.7.3　dynamic和guided調度
類型 185
5.7.4　runtime調度類型 186
5.7.5　哪一種調度 187
5.8　生產者與消費者 188
5.8.1　隊列 188
5.8.2　訊息傳遞 188
5.8.3　發送訊息 189
5.8.4　接收訊息 189
5.8.5　終止檢測 190
5.8.6　開始 190
5.8.7　atomic指令 191
5.8.8　臨界區與鎖 191
5.8.9　在訊息傳遞程式中使用鎖定 193
5.8.10　critical指令、atomic
指令或鎖 194
5.8.11　注意事項 194
5.9　快取、快取一致性與偽共享 195
5.10　任務化 199
5.11　線程安全 202
5.11.1　不正確的程序可以產生
正確的輸出 204
5.12　小結 204
5.13　練習 208
5.14　程式設計作業 211
第6章　用CUDA進行GPU程式設計 215
6.1　GPU和GPGPU 215
6.2　GPU架構 215
6.3　異構計算 217
6.4　CUDA hello 217
6.4.1　原始碼 218
6.4.2　編譯與運行程式 219
6.5　深入了解 219
6.6　線程、線程塊和線程網格 220
6.7　NVIDIA運算能力與設備架構 223
6.8　向量加法 223
6.8.1　核函數 224
6.8.2　Get_args函數 225
6.8.3　Allocate_vectors函數和
託管記憶體 226
6.8.4　main函數呼叫的其他函數 227
6.8.5　顯式記憶體傳輸 229
6.9　從CUDA核函數傳回結果 231
6.10　CUDA梯形法則I 233
6.10.1　梯形法則 233
6.10.2　一種CUDA實作 234
6.10.3　初始化、傳回值和最後
更新 235
6.10.4　使用正確的線程 236
6.10.5　更新回傳值和atomicAdd
函數 236
6.10.6　CUDA梯形法則的表現 237
6.11　CUDA梯形法則II：提升性能 238
6.11.1　樹形通訊 238
6.11.2　局部變數、暫存器、共享和
全域記憶體 239
6.11.3　線程束和線程束洗牌 240
6.11.4　使用線程束洗牌實現樹形
全局求和 241
6.11.5　共享記憶體和線程束洗牌的
替代方案 242
6.12　用warpSize個執行緒區塊實現
梯形法則 243
6.12.1　主機代碼 244
6.12.2　使用線程束洗牌的核函數 244
6.12.3　使用共享記憶體的核函數 244
6.12.4　性能 245
6.13　CUDA梯形法則III：使用具有
多個線程束的線程塊 245
6.13.1　__syncthreads函數 246
6.13.2　關於共享記憶體的更多內容 247
6.13.3　使用共享記憶體的線程束
求和 247
6.13.4　共享記憶體庫 248
6.13.5　收尾工作 249
6.13.6　性能 251
6.14　雙調排序 251
6.14.1　串列雙調排序 251
6.14.2　蝶式交換和二進位表示 254
6.14.3　並行雙調排序I 256
6.14.4　並行雙調排序II 258
6.14.5　CUDA雙調排序的效能 259
6.15　小結 260
6.16　練習 264
6.17　程式設計作業 267
第7章　平行程式開發 269
7.1　兩種n-body問題的解答 269
7.1.1　問題描述 269
7.1.2　兩種串列方案 270
7.1.3　並行化n-body求解方案 274
7.1.4　關於I/O的說明 276
7.1.5　使用OpenMP並行化基本
求解方案 277
7.1.6　使用OpenMP並行化簡化
求解方案 279
7.1.7　評估OpenMP代碼 283
7.1.8　使用Pthreads並行化求解
方案 284
7.1.9　使用MPI並行化解法 284
7.1.10　使用MPI並行化簡化求解
方案 286
7.1.11　MPI簡化求解的性能 291
7.1.12　使用CUDA並行化基本
求解方案 292
7.1.13　關於CUDA協同組的說明 294
7.1.14　基本CUDA n-body求解
方案的性能 295
7.1.15　提升CUDA n-body求解
方案性能的方法 295
7.1.16　在n-body求解方案中使用
共享記憶體技術 296
7.2　樣本排序 299
7.2.1　樣本排序與桶排序 299
7.2.2　選擇樣本資料 300
7.2.3　Map函數的簡單實作 301
7.2.4　Map的另一種實作方案 302
7.2.5　並行化樣本排序 305
7.2.6　使用OpenMP實作樣本
排序 308
7.2.7　使用Pthreads實現樣本
排序 312
7.2.8　使用MPI實作樣本排序 314
7.2.9　使用CUDA實現樣本排序 323
7.3　注意事項 331
7.4　使用哪一種API 331
7.5　小結 332
7.5.1　MPI 333
7.6　練習 334
7.7　程式設計作業 340
第8章　下一步該怎麼走 343
參考文獻 345