并行計算與高性能計算

第Ⅰ部分 并行計算介紹
第1 章 為什么使用并行計算     3
1.1 為什么要學(xué)習(xí)并行計算   5
1.1.1 并行計算的潛在優(yōu)勢是什么    7
1.1.2 并行計算的注意事項   9
1.2 并行計算的基本定律    9
1.2.1 并行計算的極限：Amdahl 定律  9
1.2.2 突破并行極限：Gustafson-Barsis定律      10
1.3 并行計算如何工作     12
1.3.1 應(yīng)用程序示例      13
1.3.2 當(dāng)今異構(gòu)并行系統(tǒng)的硬件模型  18
1.3.3 當(dāng)今異構(gòu)并行系統(tǒng)的應(yīng)用程序模型及軟件模型     21
1.4 對并行方法進行分類    24
1.5 并行策略       25
1.6 并行加速與比較加速：兩種不同的衡量標(biāo)準(zhǔn)     26
1.7 你將在本書中學(xué)到哪些內(nèi)容    27
1.7.1 擴展閱讀    27
1.7.2 練習(xí)      28
1.8 本章小結(jié)       28
第2 章 規(guī)劃并行化      29
2.1 處理新項目：準(zhǔn)備工作  30
2.1.1 版本控制：為并行代碼創(chuàng)建一個安全的存儲庫      31
2.1.2 測試套件：創(chuàng)建健壯、可靠的應(yīng)用程序的第一步   32
2.1.3 查找和修復(fù)內(nèi)存問題  40
2.1.4 提高代碼的可移植性  41
2.2 概要分析：探測系統(tǒng)功能和應(yīng)用程序性能之間的差距   42
2.3 計劃：成功的基礎(chǔ)     42
2.3.1 探索benchmark 和mini-apps   43
2.3.2 核心數(shù)據(jù)結(jié)構(gòu)和代碼模塊化設(shè)計      43
2.3.3 算法：重新設(shè)計并行  44
2.4 實施     44
2.5 提交：高質(zhì)量的打包過程 45
2.6 進一步探索     46
2.6.1 擴展閱讀    46
2.6.2 練習(xí)      46
2.7 本章小結(jié)      46
第3 章 性能極限與分析   49
3.1 了解應(yīng)用程序的潛在性能限制  49
3.2 了解硬件性能：基準(zhǔn)測試 52
3.2.1 用于收集系統(tǒng)特征的工具    52
3.2.2 計算浮點運算的最大理論值   55
3.2.3 內(nèi)存層級和理論內(nèi)存帶寬    55
3.2.4 帶寬和浮點運算的實證測量   56
3.2.5 計算flop 和帶寬之間的機器平衡      59
3.3 描述你的應(yīng)用程序：分析 59
3.3.1 分析工具    60
3.3.2 處理器時鐘頻率和能耗的實證測量    69
3.3.3 在運行時跟蹤內(nèi)存   70
3.4 進一步探索     71
3.4.1 擴展閱讀    71
3.4.2 練習(xí)      71
3.5 本章小結(jié)      71
第4 章 數(shù)據(jù)設(shè)計和性能模型     73
4.1 數(shù)據(jù)結(jié)構(gòu)與性能：面向數(shù)據(jù)的設(shè)計     74
4.1.1 多維數(shù)組    76
4.1.2 結(jié)構(gòu)數(shù)組(AoS)與數(shù)組結(jié)構(gòu)(SoA)  80
4.1.3 數(shù)組結(jié)構(gòu)的數(shù)組(AoSoA)     85
4.2 緩存未命中的3C：強制、容量與沖突     86
4.3 簡單性能模型：案例研究 90
4.3.1 全矩陣數(shù)據(jù)表示     92
4.3.2 壓縮稀疏存儲表示   95
4.4 高級性能模型    98
4.5 網(wǎng)絡(luò)消息      101
4.6 進一步探索    103
4.6.1 擴展閱讀   104
4.6.2 練習(xí)      104
4.7 本章小結(jié)      104
第5 章 并行算法與模式      105
5.1 并行計算應(yīng)用的算法分析    105
5.2 性能模型與算法復(fù)雜性 106
5.3 什么是并行算法  109
5.4 什么是哈希函數(shù)  110
5.5 空間哈希：一種高并行度算法 111
5.5.1 使用完美哈希進行空間網(wǎng)格操作   113
5.5.2 使用緊湊哈希進行空間網(wǎng)格操作   126
5.6 prefix sum(掃描)模式及其在并行計算中的重要性   132
5.6.1 Step-efficient 并行掃描操作   133
5.6.2 Work-efficient 并行掃描操作  134
5.6.3 用于大型數(shù)組的并行掃描操作 135
5.7 并行全局和：解決關(guān)聯(lián)性問題 135
5.8 并行算法研究的未來   141
5.9 進一步探索    141
5.9.1 擴展閱讀   141
5.9.2 練習(xí)      142
5.10 本章小結(jié)     142
第II 部分 CPU：并行的主力第6 章 向量化：免費的flop   145
6.1 向量及單指令多數(shù)據(jù)流(SIMD)概要    145
6.2 向量化的硬件趨勢    146
6.3 向量化方法    147
6.3.1 使用優(yōu)化軟件庫可以輕松提高性能      148
6.3.2 自動向量化：向量化加速的簡單方法(大多數(shù)情況下)   148
6.3.3 通過提示來指導(dǎo)編譯器：pragma和指令    152
6.3.4 使用向量本征庫處理無法向量化的循環(huán)    157
6.3.5 大膽嘗試：使用匯編代碼進行向量化    162
6.4 實現(xiàn)更好向量化的編程風(fēng)格   163
6.5 與編譯器向量化相關(guān)的編譯器標(biāo)志    164
6.6 使用OpenMP SIMD 指令實現(xiàn)更好的移植性   170
6.7 進一步探索    172
6.7.1 擴展閱讀   172
6.7.2 練習(xí)      172
6.8 本章小結(jié)      173
第7 章 使用OpenMP 實現(xiàn)并行計算  175
7.1 OpenMP 介紹   175
7.1.1 OpenMP 概念     176
7.1.2 OpenMP 簡單程序示例     179
7.2 典型的OpenMP 用例：循環(huán)級OpenMP、高級OpenMP 和MPI OpenMP      183
7.2.1 使用循環(huán)級OpenMP 進行快速并行化    184
7.2.2 使用高級OpenMP 獲得更好的并行度   184
7.2.3 使用MPI OpenMP 獲得極限可擴展性   185
7.3 標(biāo)準(zhǔn)循環(huán)級OpenMP 示例    185
7.3.1 循環(huán)級OpenMP：向量加法示例   186
7.3.2 stream triad 示例    189
7.3.3 循環(huán)級OpenMP：stencil 示例 190
7.3.4 循環(huán)級示例的性能   191
7.3.5 使用OpenMP 線程的global sum的約減示例  192
7.3.6 循環(huán)級OpenMP 的潛在問題  193
7.4 OpenMP 中變量范圍對結(jié)果準(zhǔn)確性的重要性   193
7.5 函數(shù)級OpenMP：使整個函數(shù)實現(xiàn)線程并行   194
7.6 使用高級OpenMP 改進并行可伸縮性      196
7.6.1 如何實現(xiàn)高級OpenMP      197
7.6.2 實現(xiàn)高級OpenMP 的示例   199
7.7 使用OpenMP 混合線程及向量化   201
7.8 使用OpenMP 的高級示例    204
7.8.1 在x 和y 方向單獨傳遞的stencil示例      204
7.8.2 使用OpenMP 線程實現(xiàn)kahan求和      208
7.8.3 通過線程實現(xiàn)的prefix scan算法      209
7.9 線程工具對健壯程序的重要性 210
7.9.1 使用Allinea/ARM MAP快速獲得應(yīng)用程序的高層概要文件  211
7.9.2 使用Intel Inspector 查找線程競態(tài)條件      212
7.10 基于任務(wù)的支持算法示例    213
7.11 進一步探索    214
7.11.1 擴展閱讀  214
7.11.2 練習(xí)     215
7.12 本章小結(jié)     215
第8 章 MPI：并行骨干  217
8.1 MPI 程序基礎(chǔ)   217
8.1.1 為每個MPI 程序進行基本MPI函數(shù)調(diào)用   218
8.1.2 簡單MPI 程序的編譯器包裝器 219
8.1.3 使用并行啟動命令   219
8.1.4 MPI 程序的最小工作示例   219
8.2 用于進程間通信的發(fā)送和接收命令    221
8.3 聚合通信：MPI 的強大組件   227
8.3.1 使用barrier 來同步計時器   228
8.3.2 使用廣播處理小文件輸入   228
8.3.3 使用約減從所有進程中獲取單個值    230
8.3.4 使用gather 在調(diào)試打印輸出中排序    233
8.3.5 使用scatter 和gather 將數(shù)據(jù)發(fā)送到工作進程    234
8.4 數(shù)據(jù)并行示例   236
8.4.1 使用stream triad 來測量節(jié)點上的帶寬    236
8.4.2 二維網(wǎng)格中的ghost cell 交換  238
8.4.3 三維stencil 計算中的ghost cell交換      244
8.5 使用高級MPI 功能來簡化代碼和啟用優(yōu)化    245
8.5.1 使用自定義MPI 數(shù)據(jù)類型來簡化代碼并提升性能 245
8.5.2 MPI 中的笛卡兒拓撲 250
8.5.3 ghost cell 交換變體的性能測試 255
8.6 通過聯(lián)合使用MPI 和OpenMP實現(xiàn)極高的可擴展性   257
8.6.1 混合MPI 和OpenMP 的優(yōu)勢  257
8.6.2 MPI 與OpenMP 混合示例   258
8.7 進一步探索    259
8.7.1 擴展閱讀   260
8.7.2 練習(xí)      260
8.8 本章小結(jié)      261
第III 部分 GPU：加速應(yīng)用程序運行
第9 章 GPU 架構(gòu)及概念     265
9.1 作為加速計算平臺的CPU-GPU
系統(tǒng)    266
9.1.1 集成GPU：商業(yè)化系統(tǒng)中沒有被充分使用的資源   267
9.1.2 獨立GPU：高性能計算的主力 267
9.2 GPU 和線程引擎     268
9.2.1 使用流多處理器(或子片)作為計算單元   270
9.2.2 作為獨立處理器的處理單元  270
9.2.3 每個處理單元進行多個數(shù)據(jù)操作   270
9.2.4 計算最新GPU flop 的理論峰值 270
9.3 GPU 內(nèi)存空間的特點   272
9.3.1 計算內(nèi)存帶寬的理論峰值   273
9.3.2 測量GPU stream benchmark   274
9.3.3 GPU 的Roofline 性能模型   275
9.3.4 使用mixbench 性能工具為工作負載選擇最佳GPU  276
9.4 PCI 總線：CPU 與GPU 之間的數(shù)據(jù)傳輸橋梁   278
9.4.1 PCI 總線的理論帶寬  279
9.4.2 PCI 帶寬benchmark 應(yīng)用程序 281
9.5 多GPU 平臺和MPI    284
9.5.1 優(yōu)化網(wǎng)絡(luò)中GPU 之間的數(shù)據(jù)移動   284
9.5.2 一種比PCI 總線性能更高的替代方案   285
9.6 GPU 加速平臺的潛在收益    286
9.6.1 縮短解決問題的時間  286
9.6.2 使用GPU 降低能耗  287
9.6.3 使用GPU 降低云計算成本   292
9.7 何時使用GPU   292
9.8 進一步探索    292
9.8.1 擴展閱讀   293
9.8.2 練習(xí)      293
9.9 本章小結(jié)      293
第10 章 GPU 編程模型      295
10.1 GPU 編程抽象：通用框架   296
10.1.1 大規(guī)模并行處理   296
10.1.2 無法在任務(wù)之間進行協(xié)調(diào)  297
10.1.3 GPU 并行性的術(shù)語 297
10.1.4 將數(shù)據(jù)分解成獨立的工作單元：NDRange 或網(wǎng)格  297
10.1.5 為工作組提供大小合適的工作塊   300
10.1.6 通過lockstep 執(zhí)行子工作組、warp 與wavefront  300
10.1.7 工作項：操作的基本單元  301
10.1.8 SIMD 或向量硬件  301
10.2 GPU 編程模型的代碼結(jié)構(gòu)   302
10.2.1 “Me”編程：并行kernel的概念   302
10.2.2 線程索引：將本地tile 映射到全局中  303
10.2.3 索引集   304
10.2.4 如何在GPU 編程模型中對內(nèi)存資源進行尋址 305
10.3 優(yōu)化GPU 資源利用   306
10.3.1 kernel 將使用多少寄存器  307
10.3.2 利用率：提高工作組的負載率   307
10.4 約減模式需要跨工作組進行同步   309
10.5 通過隊列(流)進行異步計算   310
10.6 為GPU 定制并行化應(yīng)用程序的策略    311
10.6.1 場景1：三維大氣環(huán)境仿真 311
10.6.2 場景2：非結(jié)構(gòu)化網(wǎng)格應(yīng)用 312
10.7 進一步探索    312
10.7.1 擴展閱讀  313
10.7.2 練習(xí)    314
10.8 本章小結(jié)     314
第11 章 基于指令的GPU 編程 315
11.1 為GPU 實現(xiàn)應(yīng)用編譯指令和pragma 的過程      316
11.2 OpenACC：在GPU 上運行的最簡單方法    317
11.2.1 編譯OpenACC 代碼     319
11.2.2 OpenACC 中用于加速計算的并行計算區(qū)域    320
11.2.3 使用指令減少CPU 和GPU之間的數(shù)據(jù)移動   325
11.2.4 優(yōu)化GPU kernel   329
11.2.5 stream triad 性能結(jié)果的總結(jié) 334
11.2.6 高級OpenACC 技術(shù)     335
11.3 OpenMP：加速器領(lǐng)域的重量級選手    337
11.3.1 編譯OpenMP 代碼 337
11.3.2 使用OpenMP 在GPU 上生成并行工作  339
11.3.3 使用OpenMP 創(chuàng)建數(shù)據(jù)區(qū)域來控制到GPU 的數(shù)據(jù)移動  342
11.3.4 為GPU 優(yōu)化OpenMP    346
11.3.5 用于GPU 的高級OpenMP  350
11.4 進一步探索    353
11.4.1 擴展閱讀  353
11.4.2 練習(xí)     354
11.5 本章小結(jié)     355
第12 章 GPU 語言：深入了解基礎(chǔ)知識    357
12.1 原生GPU 編程語言的特性   358
12.2 CUDA 和HIP GPU 語言：底層性能選項  359
12.2.1 編寫和構(gòu)建第一個CUDA應(yīng)用程序  360
12.2.2 CUDA 的約減kernel：事情變得復(fù)雜  367
12.2.3 Hipifying CUDA 代碼    372
12.3 OpenCL：用于可移植的開源GPU 語言     375
12.3.1 編寫和構(gòu)建第一個OpenCL應(yīng)用程序  376
12.3.2 OpenCL 中的約減  381
12.4 SYCL：一個成為主流的實驗性C 實現(xiàn)     384
12.5 性能可移植性的高級語言    387
12.5.1 Kokkos：性能可移植性生態(tài)系統(tǒng)  387
12.5.2 RAJA 提供更具適應(yīng)性的性能可移植性層     390
12.6 進一步探索    392
12.6.1 擴展閱讀  392
12.6.2 練習(xí)    393
12.7 本章小結(jié)     393
第13 章 GPU 配置分析及工具 395
13.1 分析工具概要  395
13.2 如何選擇合適的工作流 396
13.3 問題示例：淺水仿真  397
13.4 分析工作流的示例    400
13.4.1 運行淺水應(yīng)用程序 400
13.4.2 分析CPU 代碼來制定行動計劃  402
13.4.3 為實施步驟添加OpenACC計算指令  403
13.4.4 添加數(shù)據(jù)移動指令 405
13.4.5 通過引導(dǎo)分析獲取改進建議 406
13.4.6 強大的輔助開發(fā)工具：NVIDIA Nsight 工具套件   408
13.4.7 用于AMD GPU 生態(tài)系統(tǒng)的CodeXL   409
13.5 專注于重要指標(biāo)     409
13.5.1 利用率：是否有足夠的工作量   410
13.5.2 發(fā)布效率：你的warp 是否經(jīng)常停滯？     410
13.5.3 獲得帶寬  411
13.6 使用容器和虛擬機來提供備用工作流      411
13.6.1 將Docker 容器作為解決方案      411
13.6.2 使用VirtualBox 虛擬機   413
13.7 移入云端：提供靈活和可擴展能力     415
13.8 進一步探索    415
13.8.1 擴展閱讀  415
13.8.2 練習(xí)    416
13.9 本章小結(jié)     416
第Ⅳ部分 高性能計算生態(tài)系統(tǒng)
第14 章 關(guān)聯(lián)性：與kernel 休戰(zhàn)     419
14.1 為什么關(guān)聯(lián)性很重要  420
14.2 探索架構(gòu)     421
14.3 OpenMP 的線程關(guān)聯(lián)  422
14.4 進程關(guān)聯(lián)性與MPI    429
14.4.1 OpenMPI 的默認進程放置  429
14.4.2 進行控制：在OpenMPI 中指定進程放置的基本技術(shù)     430
14.4.3 關(guān)聯(lián)性不僅僅是進程綁定：全面討論  434
14.5 MPI OpenMP 的關(guān)聯(lián)性     436
14.6 從命令行控制關(guān)聯(lián)性  440
14.6.1 使用hwloc-bind 分配關(guān)聯(lián)性 440
14.6.2 使用likwid-pin: likwid 工具套件中的關(guān)聯(lián)工具  441
14.7 展望未來：在運行時設(shè)置和更改關(guān)聯(lián)性    443
14.7.1 在可執(zhí)行文件中設(shè)置關(guān)聯(lián)性 443
14.7.2 在運行時更改進程關(guān)聯(lián)性  445
14.8 進一步探索    447
14.8.1 擴展閱讀  447
14.8.2 練習(xí)    448
14.9 本章小結(jié)     449
第15 章 批處理調(diào)度器：為混亂帶來秩序    451
15.1 無管理系統(tǒng)所帶來的混亂    452
15.2 如何順利地在繁忙的集群中部署任務(wù)     452
15.2.1 繁忙集群中的批處理系統(tǒng)布局    453
15.2.2 如何合理地在繁忙的集群和HPC 站點上運行任務(wù)：HPC 中的推薦做法     453
15.3 提交第一個批處理腳本 454
15.4 為長時間運行的作業(yè)設(shè)定自動重啟     459
15.5 在批處理腳本中指定依賴項  463
15.6 進一步探索    465
15.6.1 擴展閱讀  465
15.6.2 練習(xí)    465
15.7 本章小結(jié)     466
第16 章 并行環(huán)境的文件操作  467
16.1 高性能文件系統(tǒng)的組成部分  467
16.2 標(biāo)準(zhǔn)文件操作：并行到串行(parallel-to-serial)接口  468
16.3 在并行環(huán)境中使用MPI
文件操作(MPI-IO)    469
16.4 HDF5 具有自我描述功能，可更好地管理數(shù)據(jù)   477
16.5 其他并行文件軟件包  485
16.6 并行文件系統(tǒng)：硬件接口    485
16.6.1 并行文件設(shè)置    485
16.6.2 適用于所有文件系統(tǒng)的通用提示    489
16.6.3 特定文件系統(tǒng)的提示    490
16.7 進一步探索    493
16.7.1 擴展閱讀  493
16.7.2 練習(xí)    494
16.8 本章小結(jié)     494
第17 章 用于編寫優(yōu)質(zhì)代碼的工具和資源    495
17.1 版本控制系統(tǒng)：一切從這里開始    497
17.1.1 分布式版本控制更適合全局協(xié)作    498
17.1.2 通過集中版本控制來簡化操作并提高代碼安全   498
17.2 用于跟蹤代碼性能的計時器例程    499
17.3 分析器：不去衡量就無法提升 500
17.3.1 日常使用的基于文本的分析器   501
17.3.2 用于快速識別瓶頸的高級分析器   502
17.3.3 使用中級分析器來指導(dǎo)應(yīng)用程序開發(fā)  502
17.3.4 通過詳細分析器了解硬件性能的細節(jié)信息     504
17.4 benchmark 和mini-apps：了解系統(tǒng)性能的窗口     504
17.4.1 使用benchmark 測量系統(tǒng)性能特征  504
17.4.2 通過mini-apps 提供應(yīng)用程序的視角   505
17.5 為健壯的應(yīng)用程序檢測及修復(fù)內(nèi)存錯誤     507
17.5.1 valgrind Memcheck：備用開源方案  507
17.5.2 使用Dr. Memory 診斷內(nèi)存問題  507
17.5.3 對于要求嚴(yán)苛的應(yīng)用程序使用商業(yè)內(nèi)存檢測工具   509
17.5.4 使用基于編譯器的內(nèi)存工具來簡化操作  509
17.5.5 通過Fence-post 檢查器來檢測越界內(nèi)存訪問    510
17.5.6 GPU 應(yīng)用程序所使用的內(nèi)存工具  511
17.6 用于檢測競態(tài)條件的線程檢查器      512
17.6.1 Intel Inspector：帶有GUI 的競態(tài)條件檢測工具 512
17.6.2 Archer：一個基于文本的檢測競態(tài)條件的工具   512
17.7 Bug-busters：用于消除bug 的調(diào)試器      514
17.7.1 在HPC 站點中廣泛使用的TotalView 調(diào)試器  514
17.7.2 DDT：另一種在HPC 站點廣泛使用的調(diào)試器    514
17.7.3 Linux 調(diào)試器：為本地開發(fā)需求提供免費的替代方案  515
17.7.4 通過GPU 調(diào)試器消除GPU bug  515
17.8 文件操作分析  516
17.9 包管理器：你的個人系統(tǒng)管理員      519
17.9.1 macOS 的包管理器 519
17.9.2 Windows 包管理器 519
17.9.3 Spack 包管理器：用于高性能計算的包管理器  519
17.10 模塊：加載專門的工具鏈   520
17.10.1 TCL modules：用于加載軟件工具鏈的原始模塊系統(tǒng)  522
17.10.2 Lmod：基于Lua 的替代模塊實現(xiàn)   523
17.11 思考與練習(xí)   523
17.12 本章小結(jié)    523
附錄A 參考資料     (可從配書網(wǎng)站下載)
附錄B 習(xí)題答案     (可從配書網(wǎng)站下載)