並行計算與高性能計算 Parallel and High Performance Computing

主要內容 ●規劃新的並行項目 ●瞭解CPU和GPU架構上的差異 ●找到性能不佳的內核和循環 ●使用批處理調度來管理應用程序

第Ⅰ部分 並行計算介紹

第1 章 為什麽使用並行計算     3

1.1 為什麽要學習並行計算   5

1.1.1 並行計算的潛在優勢是什麽    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 應用程序示例      13

1.3.2 當今異構並行系統的硬件模型  18

1.3.3 當今異構並行系統的應用程序模型及軟件模型     21

1.4 對並行方法進行分類    24

1.5 並行策略       25

1.6 並行加速與比較加速：兩種不同的衡量標準     26

1.7 你將在本書中學到哪些內容    27

1.7.1 擴展閱讀    27

1.7.2 練習      28

1.8 本章小結       28

第2 章 規劃並行化      29

2.1 處理新項目：準備工作  30

2.1.1 版本控制：為並行代碼創建一個安全的存儲庫      31

2.1.2 測試套件：創建健壯、可靠的應用程序的第一步   32

2.1.3 查找和修復內存問題  40

2.1.4 提高代碼的可移植性  41

2.2 概要分析：探測系統功能和應用程序性能之間的差距   42

2.3 計劃：成功的基礎     42

2.3.1 探索benchmark 和mini-apps   43

2.3.2 核心數據結構和代碼模塊化設計      43

2.3.3 算法：重新設計並行  44

2.4 實施     44

2.5 提交：高質量的打包過程 45

2.6 進一步探索     46

2.6.1 擴展閱讀    46

2.6.2 練習      46

2.7 本章小結      46

第3 章 性能極限與分析   49

3.1 瞭解應用程序的潛在性能限制  49

3.2 瞭解硬件性能：基準測試 52

3.2.1 用於收集系統特徵的工具    52

3.2.2 計算浮點運算的最大理論值   55

3.2.3 內存層級和理論內存帶寬    55

3.2.4 帶寬和浮點運算的實證測量   56

3.2.5 計算flop 和帶寬之間的機器平衡      59

3.3 描述你的應用程序：分析 59

3.3.1 分析工具    60

3.3.2 處理器時鐘頻率和能耗的實證測量    69

3.3.3 在運行時跟蹤內存   70

3.4 進一步探索     71

3.4.1 擴展閱讀    71

3.4.2 練習      71

3.5 本章小結      71

第4 章 數據設計和性能模型     73

4.1 數據結構與性能：面向數據的設計     74

4.1.1 多維數組    76

4.1.2 結構數組(AoS)與數組結構(SoA)  80

4.1.3 數組結構的數組(AoSoA)     85

4.2 緩存未命中的3C：強制、容量與沖突     86

4.3 簡單性能模型：案例研究 90

4.3.1 全矩陣數據表示     92

4.3.2 壓縮稀疏存儲表示   95

4.4 高級性能模型    98

4.5 網絡消息      101

4.6 進一步探索    103

4.6.1 擴展閱讀   104

4.6.2 練習      104

4.7 本章小結      104

第5 章 並行算法與模式      105

5.1 並行計算應用的算法分析    105

5.2 性能模型與算法復雜性 106

5.3 什麽是並行算法  109

5.4 什麽是哈希函數  110

5.5 空間哈希：一種高並行度算法 111

5.5.1 使用完美哈希進行空間網格操作   113

5.5.2 使用緊湊哈希進行空間網格操作   126

5.6 prefix sum(掃描)模式及其在並行計算中的重要性   132

5.6.1 Step-efficient 並行掃描操作   133

5.6.2 Work-efficient 並行掃描操作  134

5.6.3 用於大型數組的並行掃描操作 135

5.7 並行全局和：解決關聯性問題 135

5.8 並行算法研究的未來   141

5.9 進一步探索    141

5.9.1 擴展閱讀   141

5.9.2 練習      142

5.10 本章小結     142

第II 部分 CPU：並行的主力第6 章 向量化：免費的flop   145

6.1 向量及單指令多數據流(SIMD)概要    145

6.2 向量化的硬件趨勢    146

6.3 向量化方法    147

6.3.1 使用優化軟件庫可以輕松提高性能      148

6.3.2 自動向量化：向量化加速的簡單方法(大多數情況下)   148

6.3.3 通過提示來指導編譯器：pragma和指令    152

6.3.4 使用向量本徵庫處理無法向量化的循環    157

6.3.5 大膽嘗試：使用匯編代碼進行向量化    162

6.4 實現更好向量化的編程風格   163

6.5 與編譯器向量化相關的編譯器標志    164

6.6 使用OpenMP SIMD 指令實現更好的移植性   170

6.7 進一步探索    172

6.7.1 擴展閱讀   172

6.7.2 練習      172

6.8 本章小結      173

第7 章 使用OpenMP 實現並行計算  175

7.1 OpenMP 介紹   175

7.1.1 OpenMP 概念     176

7.1.2 OpenMP 簡單程序示例     179

7.2 典型的OpenMP 用例：循環級OpenMP、高級OpenMP 和MPI +OpenMP      183

7.2.1 使用循環級OpenMP 進行快速並行化    184

7.2.2 使用高級OpenMP 獲得更好的並行度   184

7.2.3 使用MPI + OpenMP 獲得極限可擴展性   185

7.3 標準循環級OpenMP 示例    185

7.3.1 循環級OpenMP：向量加法示例   186

7.3.2 stream triad 示例    189

7.3.3 循環級OpenMP：stencil 示例 190

7.3.4 循環級示例的性能   191

7.3.5 使用OpenMP 線程的global sum的約減示例  192

7.3.6 循環級OpenMP 的潛在問題  193

7.4 OpenMP 中變量範圍對結果準確性的重要性   193

7.5 函數級OpenMP：使整個函數實現線程並行   194

7.6 使用高級OpenMP 改進並行可伸縮性      196

7.6.1 如何實現高級OpenMP      197

7.6.2 實現高級OpenMP 的示例   199

7.7 使用OpenMP 混合線程及向量化   201

7.8 使用OpenMP 的高級示例    204

7.8.1 在x 和y 方向單獨傳遞的stencil示例      204

7.8.2 使用OpenMP 線程實現kahan求和      208

7.8.3 通過線程實現的prefix scan算法      209

7.9 線程工具對健壯程序的重要性 210

7.9.1 使用Allinea/ARM MAP快速獲得應用程序的高層概要文件  211

7.9.2 使用Intel Inspector 查找線程競態條件      212

7.10 基於任務的支持算法示例    213

7.11 進一步探索    214

7.11.1 擴展閱讀  214

7.11.2 練習     215

7.12 本章小結     215

第8 章 MPI：並行骨乾  217

8.1 MPI 程序基礎   217

8.1.1 為每個MPI 程序進行基本MPI函數調用   218

8.1.2 簡單MPI 程序的編譯器包裝器 219

8.1.3 使用並行啟動命令   219

8.1.4 MPI 程序的最小工作示例   219

8.2 用於進程間通信的發送和接收命令    221

8.3 聚合通信：MPI 的強大組件   227

8.3.1 使用barrier 來同步計時器   228

8.3.2 使用廣播處理小文件輸入   228

8.3.3 使用約減從所有進程中獲取單個值    230

8.3.4 使用gather 在調試打印輸出中排序    233

8.3.5 使用scatter 和gather 將數據發送到工作進程    234

8.4 數據並行示例   236

8.4.1 使用stream triad 來測量節點上的帶寬    236

8.4.2 二維網格中的ghost cell 交換  238

8.4.3 三維stencil 計算中的ghost cell交換      244

8.5 使用高級MPI 功能來簡化代碼和啟用優化    245

8.5.1 使用自定義MPI 數據類型來簡化代碼並提升性能 245

8.5.2 MPI 中的笛卡兒拓撲 250

8.5.3 ghost cell 交換變體的性能測試 255

8.6 通過聯合使用MPI 和OpenMP實現極高的可擴展性   257

8.6.1 混合MPI 和OpenMP 的優勢  257

8.6.2 MPI 與OpenMP 混合示例   258

8.7 進一步探索    259

8.7.1 擴展閱讀   260

8.7.2 練習      260

8.8 本章小結      261

第III 部分 GPU：加速應用程序運行

第9 章 GPU 架構及概念     265

9.1 作為加速計算平臺的CPU-GPU

系統    266

9.1.1 集成GPU：商業化系統中沒有被充分使用的資源   267

9.1.2 獨立GPU：高性能計算的主力 267

9.2 GPU 和線程引擎     268

9.2.1 使用流多處理器(或子片)作為計算單元   270

9.2.2 作為獨立處理器的處理單元  270

9.2.3 每個處理單元進行多個數據操作   270

9.2.4 計算最新GPU flop 的理論峰值 270

9.3 GPU 內存空間的特點   272

9.3.1 計算內存帶寬的理論峰值   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 之間的數據傳輸橋梁   278

9.4.1 PCI 總線的理論帶寬  279

9.4.2 PCI 帶寬benchmark 應用程序 281

9.5 多GPU 平臺和MPI    284

9.5.1 優化網絡中GPU 之間的數據移動   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 練習      293

9.9 本章小結      293

第10 章 GPU 編程模型      295

10.1 GPU 編程抽象：通用框架   296

10.1.1 大規模並行處理   296

10.1.2 無法在任務之間進行協調  297

10.1.3 GPU 並行性的術語 297

10.1.4 將數據分解成獨立的工作單元：NDRange 或網格  297

10.1.5 為工作組提供大小合適的工作塊   300

10.1.6 通過lockstep 執行子工作組、warp 與wavefront  300

10.1.7 工作項：操作的基本單元  301

10.1.8 SIMD 或向量硬件  301

10.2 GPU 編程模型的代碼結構   302

10.2.1 “Me”編程：並行kernel的概念   302

10.2.2 線程索引：將本地tile 映射到全局中  303

10.2.3 索引集   304

10.2.4 如何在GPU 編程模型中對內存資源進行尋址 305

10.3 優化GPU 資源利用   306

10.3.1 kernel 將使用多少寄存器  307

10.3.2 利用率：提高工作組的負載率   307

10.4 約減模式需要跨工作組進行同步   309

10.5 通過隊列(流)進行異步計算   310

10.6 為GPU 定製並行化應用程序的策略    311

10.6.1 場景1：三維大氣環境模擬 311

10.6.2 場景2：非結構化網格應用 312

10.7 進一步探索    312

10.7.1 擴展閱讀  313

10.7.2 練習    314

10.8 本章小結     314

第11 章 基於指令的GPU 編程 315

11.1 為GPU 實現應用編譯指令和pragma 的過程      316

11.2 OpenACC：在GPU 上運行的最簡單方法    317

11.2.1 編譯OpenACC 代碼     319

11.2.2 OpenACC 中用於加速計算的並行計算區域    320

11.2.3 使用指令減少CPU 和GPU之間的數據移動   325

11.2.4 優化GPU kernel   329

11.2.5 stream triad 性能結果的總結 334

11.2.6 高級OpenACC 技術     335

11.3 OpenMP：加速器領域的重量級選手    337

11.3.1 編譯OpenMP 代碼 337

11.3.2 使用OpenMP 在GPU 上生成並行工作  339

11.3.3 使用OpenMP 創建數據區域來控制到GPU 的數據移動  342

11.3.4 為GPU 優化OpenMP    346

11.3.5 用於GPU 的高級OpenMP  350

11.4 進一步探索    353

11.4.1 擴展閱讀  353

11.4.2 練習     354

11.5 本章小結     355

第12 章 GPU 語言：深入瞭解基礎知識    357

12.1 原生GPU 編程語言的特性   358

12.2 CUDA 和HIP GPU 語言：底層性能選項  359

12.2.1 編寫和構建第一個CUDA應用程序  360

12.2.2 CUDA 的約減kernel：事情變得復雜  367

12.2.3 Hipifying CUDA 代碼    372

12.3 OpenCL：用於可移植的開源GPU 語言     375

12.3.1 編寫和構建第一個OpenCL應用程序  376

12.3.2 OpenCL 中的約減  381

12.4 SYCL：一個成為主流的實驗性C++實現     384

12.5 性能可移植性的高級語言    387

12.5.1 Kokkos：性能可移植性生態系統  387

12.5.2 RAJA 提供更具適應性的性能可移植性層     390

12.6 進一步探索    392

12.6.1 擴展閱讀  392

12.6.2 練習    393

12.7 本章小結     393

第13 章 GPU 配置分析及工具 395

13.1 分析工具概要  395

13.2 如何選擇合適的工作流 396

13.3 問題示例：淺水模擬  397

13.4 分析工作流的示例    400

13.4.1 運行淺水應用程序 400

13.4.2 分析CPU 代碼來制定行動計劃  402

13.4.3 為實施步驟添加OpenACC計算指令  403

13.4.4 添加數據移動指令 405

13.4.5 通過引導分析獲取改進建議 406

13.4.6 強大的輔助開發工具：NVIDIA Nsight 工具套件   408

13.4.7 用於AMD GPU 生態系統的CodeXL   409

13.5 專註於重要指標     409

13.5.1 利用率：是否有足夠的工作量   410

13.5.2 發布效率：你的warp 是否經常停滯？     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 練習    416

13.9 本章小結     416

第Ⅳ部分 高性能計算生態系統

第14 章 關聯性：與kernel 休戰     419

14.1 為什麽關聯性很重要  420

14.2 探索架構     421

14.3 OpenMP 的線程關聯  422

14.4 進程關聯性與MPI    429

14.4.1 OpenMPI 的默認進程放置  429

14.4.2 進行控制：在OpenMPI 中指定進程放置的基本技術     430

14.4.3 關聯性不僅僅是進程綁定：全面討論  434

14.5 MPI+OpenMP 的關聯性     436

14.6 從命令行控制關聯性  440

14.6.1 使用hwloc-bind 分配關聯性 440

14.6.2 使用likwid-pin: likwid 工具套件中的關聯工具  441

14.7 展望未來：在運行時設置和更改關聯性    443

14.7.1 在可執行文件中設置關聯性 443

14.7.2 在運行時更改進程關聯性  445

14.8 進一步探索    447

14.8.1 擴展閱讀  447

14.8.2 練習    448

14.9 本章小結     449

第15 章 批處理調度器：為混亂帶來秩序    451

15.1 無管理系統所帶來的混亂    452

15.2 如何順利地在繁忙的集群中部署任務     452

15.2.1 繁忙集群中的批處理系統佈局    453

15.2.2 如何合理地在繁忙的集群和HPC 站點上運行任務：HPC 中的推薦做法     453

15.3 提交第一個批處理腳本 454

15.4 為長時間運行的作業設定自動重啟     459

15.5 在批處理腳本中指定依賴項  463

15.6 進一步探索    465

15.6.1 擴展閱讀  465

15.6.2 練習    465

15.7 本章小結     466

第16 章 並行環境的文件操作  467

16.1 高性能文件系統的組成部分  467

16.2 標準文件操作：並行到串行(parallel-to-serial)接口  468

16.3 在並行環境中使用MPI

文件操作(MPI-IO)    469

16.4 HDF5 具有自我描述功能，可更好地管理數據   477

16.5 其他並行文件軟件包  485

16.6 並行文件系統：硬件接口    485

16.6.1 並行文件設置    485

16.6.2 適用於所有文件系統的通用提示    489

16.6.3 特定文件系統的提示    490

16.7 進一步探索    493

16.7.1 擴展閱讀  493

16.7.2 練習    494

16.8 本章小結     494

第17 章 用於編寫優質代碼的工具和資源    495

17.1 版本控制系統：一切從這里開始    497

17.1.1 分佈式版本控制更適合全局協作    498

17.1.2 通過集中版本控制來簡化操作並提高代碼安全   498

17.2 用於跟蹤代碼性能的計時器例程    499

17.3 分析器：不去衡量就無法提升 500

17.3.1 日常使用的基於文本的分析器   501

17.3.2 用於快速識別瓶頸的高級分析器   502

17.3.3 使用中級分析器來指導應用程序開發  502

17.3.4 通過詳細分析器瞭解硬件性能的細節信息     504

17.4 benchmark 和mini-apps：瞭解系統性能的窗口     504

17.4.1 使用benchmark 測量系統性能特徵  504

17.4.2 通過mini-apps 提供應用程序的視角   505

17.5 為健壯的應用程序檢測及修復內存錯誤     507

17.5.1 valgrind Memcheck：備用開源方案  507

17.5.2 使用Dr. Memory 診斷內存問題  507

17.5.3 對於要求嚴苛的應用程序使用商業內存檢測工具   509

17.5.4 使用基於編譯器的內存工具來簡化操作  509

17.5.5 通過Fence-post 檢查器來檢測越界內存訪問    510

17.5.6 GPU 應用程序所使用的內存工具  511

17.6 用於檢測競態條件的線程檢查器      512

17.6.1 Intel Inspector：帶有GUI 的競態條件檢測工具 512

17.6.2 Archer：一個基於文本的檢測競態條件的工具   512

17.7 Bug-busters：用於消除bug 的調試器      514

17.7.1 在HPC 站點中廣泛使用的TotalView 調試器  514

17.7.2 DDT：另一種在HPC 站點廣泛使用的調試器    514

17.7.3 Linux 調試器：為本地開發需求提供免費的替代方案  515

17.7.4 通過GPU 調試器消除GPU bug  515

17.8 文件操作分析  516

17.9 包管理器：你的個人系統管理員      519

17.9.1 macOS 的包管理器 519

17.9.2 Windows 包管理器 519

17.9.3 Spack 包管理器：用於高性能計算的包管理器  519

17.10 模塊：加載專門的工具鏈   520

17.10.1 TCL modules：用於加載軟件工具鏈的原始模塊系統  522

17.10.2 Lmod：基於Lua 的替代模塊實現   523

17.11 思考與練習   523

17.12 本章小結    523

附錄A 參考資料     (可從配書網站下載)

附錄B 習題答案     (可從配書網站下載)