高性能並行運行時系統：設計與實現

並行無處不在。從小的設備（例如支援物聯網的處理器）到大的超級電腦，幾乎所有設備都提供具有多個處理元件的執行環境。因此，這要求程式師編寫能夠充分利用硬體中多個處理單元的並行代碼。並行程式需要一個提供有效執行機制的軟體基礎設施（“並行運行時”），這些運行時必須考慮底層電腦架構的特定結構以及執行環境所提供的特性。

在《高性能並行運行時系統：設計與實現》中，我們將展示由現代處理器設計方式所帶來的有趣效果。程式師在實現高性能並行運行時系統的時候，需要考慮底層機器細節。我們將展示其中存在的（性能）陷阱，你將看到一些違反直覺的結論，它們很可能會誤導你對機器性能的思考及實現決策。通過閱讀本書，你將瞭解：

現代計算機架構的主要概念；
每種構造的合理性能指標是什麼；
根據底層硬體特性，理論性能極限是什麼；
如何測量硬體與程式碼兩者的性能；
如何使用硬體特性的度量設計性能良好的軟體；
用於實現並行編程模型的基本演算法，以及它們如何與現代處理器交互。

《高性能並行運行時系統：設計與實現》的目標讀者主要是正在學習編譯器構建、並行編程或系統編程的學生。對於那些想要編寫並行代碼，理解並行代碼的性能，深入理解代碼，以及想要實現並行運行時系統的人員，閱讀本書也大有裨益。

譯者序
序
前言
術語表

第1章 緒論
1.1 本書結構
1.2 探索設計空間
1.2.1 作為庫的並行
1.2.2 作為語言的並行
1.3 代碼示例
1.4 機器配置

第2章 並行編程模型與概念
2.1 多進程與多執行緒
2.1.1 執行緒基礎
2.1.2 執行緒親和性
2.1.3 基於執行緒編程的Open MP API
2.1.4 工作分享
2.1.5 0penMP執行緒親和性
2.2 基於任務的並行編程
2.3 同步構造
2.3.1 鎖與互斥
2.3.2 同步障、歸約和閉鎖
2.3.3 任務同步障
2.3.4 任務依賴
2.4 阿姆達爾定律
2.4.1 呈現性能結果
2.4.2 對性能的影響
2.4.3 將開銷映射到阿姆達爾定律中
2.4.4 阿姆達爾定律變體
2.5 總結

第3章 眾核與多核電腦架構
3.1 執行機制
3.1.1 馮·諾依曼架構與按序執行
3.1.2 按序流水線執行
3.1.3 亂序執行
3.1.4 分支預測
3.1.5 超標量執行
3.1.6 同步多執行緒
3.1.7 單指令多資料
3.2 現代記憶體子系統
3.2.1 記憶體層次結構
3.2.2 記憶體模型與記憶體一致性
3.2.3 緩存
3.2.4 快取一致性：概述
3.2.5 快取一致性：MESl協議
3.2.6 性能影響
3.2.7 非統一記憶體架構
3.3 總結

第4章 編譯器和運行時的交互
4.1 編譯器基礎
4.2 基於任務的並行模型的實現
4.2.1 lambda函數和閉包
4.2.2 TBB中的排隊任務
4.3 並行編程語言的編譯器
4.4 並行代碼生成模式
4.4.1 並行域的代碼生成
4.4.2 執行緒並行迴圈的代碼生成
4.4.3 SIMD並行迴圈的代碼生成
4.4.4 串列構造的代碼生成
4.4.5 靜態任務的代碼生成
4.4.6 動態任務的代碼生成
4.5 0penMP實現示例
4.5.1 GNU編譯器套件
4.5.2 Intel編譯器和LLVM編譯器
4.6 總結

第5章 並行運行時基本機制
5.1 管理並行性
5.1.1 生成並行性
5.1.2 等待
5.2 並行性管理與硬體結構
5.2.1 檢測硬體結構
5.2.2 執行緒固定
5.3 並行運行時系統中的記憶體管理
5.3.1 記憶體效率及緩存使用
5.3.2 單執行緒記憶體分配器
5.3.3 多執行緒記憶體分配器
5.3.4 並行運行時系統的專用記憶體分配器
5.3.5 執行緒本機存放區
5.3.6 執行緒物件的資料佈局
5.4 總結

寮6章 互斥和原子性
6.1 互斥問題
6.1.1 鎖的硬體支援：原子指令
6.1.2 ABA問題
6.2 我們應該寫鎖代碼嗎
6.3 鎖的類別
6.4 鎖演算法的特性
6.5 鎖演算法
6.5.1 測試並設置鎖
6.5.2 測試及測試並設置鎖
6.5.3 票鎖
6.5.4 排隊鎖
6.6 實際代碼性能
6.6.1 無爭用鎖開銷
6.6.2 爭用鎖的輸送量
6.6.3 性能總結
6.7 如何等待
6.8 事務同步
6.8.1 事務語義
6.8.2 MESI協議中的實現
6.8.3 事務指令
6.8.4 事務鎖
6.8.5 互斥和預測的比較
6.9 其他串列操作
6.9.1 master和masked構造
6.9.2 single構造
6.10 原子操作
6.10.1 原子指令映射
6.10.2 最小值和優選值的原子實現
6.11總結
6.11.1 鎖總結
6.11.2 原子操作總結

第7章 同步障和歸約
7.1 同步障基本原理
7.2 同步障性能測量
7.2.1 同步障微基準程式
7.2.2 同步障性能模型
7.3 同步障組件
7.3.1 計數器和標誌
7.3.2 廣播
7.4 同步障演算法分類
7.5 同步障演算法
7.5.1 計數同步障
7.5.2 多對多同步障
7.5.3 蝶形／超立方體同步障
7.5.4 傳播型同步障
7.5.5 樹形簽入同步障
7.6 歸約
7.7 其他優化
7.8 總結

第8章 調度並行迴圈
8.1 調度目標
8.2 調度效率的理論極限
8.3 基本調度萬法
8.3.1 靜態迴圈調度
8.3.2 動態迴圈調度
8.4 映射為規範形式
8.5 編譯器迴圈轉換
8.6 迴圈調度單調性
8.7 靜態迴圈調度實現
8.7.1 分塊式迴圈調度
8.7.2 塊迴圈式迴圈調度
8.8 動態迴圈調度實現
8.8.1 指導式調度
8.8.2 monotonic： dynamic
8.8.3 nonmonotonic： dynamic
8.9 迴圈調度評估
8.10 其他迴圈調度方案
8.10.1 使用歷史資訊
8.10.2 用戶控制調度
8.11 總結

第9章 任務並行模型的運行時支援
9.1 任務描述符
9.2 任務池實現
9.2.1 單任務池
9.2.2 多工池
9.3 任務同步
9.3.1 等待任務子集完成
9.3.2 等待直接子任務完成
9.3.3 任務依賴
9.4 任務調度
9.4.1 任務調度點
9.4.2 廣度優先調度和深度優先調度
9.4.3 任務竊取
9.5 任務調度約束
9.5.1 棧調度
9.5.2 迴圈調度
9.6 其他任務主題
9.6.1 任務優先順序
9.6.2 任務親和性
9.7 總結

第10章 總結和感想

附錄 技術縮略語
參考文獻