基本介紹
內容簡介,目錄,作者簡介,
內容簡介
第1部分介紹多核編程的基礎知識，包括多核編程常見問題、鎖競爭、加速比、負載均衡等基本概念，多執行緒退出算法、讀寫鎖、旋轉鎖、原子操作等多執行緒編程基礎知識，基於OpenMP標準的並行程式設計基礎等；
第2部分介紹基礎的數據結構與算法，包括數組、鍊表、哈希表、二叉樹、AVL樹、複合二叉樹等基本數據結構，在鍊表那章中還講解了多執行緒並行遍歷的基本方法。
第3部分介紹多核並行計算方面的基礎知識，並行編程包括常用的編程模式如分治模式、流水線模式、任務圖分解與調度模式、動態任務調度模式等，並行搜尋包括順序搜尋及終止檢測算法，並行最短路徑搜尋等，並行排序包括並行快速排序、並行歸併排序、並行基數排序等，並行數值計算包括並行矩陣乘法、並行前綴和計算等方面的內容。本部分介紹的各種並行算法和程式中，重點介紹如何解決多核系統中的計算隨CPU核數的擴展性，CPUCache偽共享方面的問題。
第4部分介紹多核共享資源計算方面的內容，也是《多核計算與程式設計》中最重要的內容，講解了分散式計算設計模式如執行緒分組競爭模式、條件同步模式、批量私有化處理模式、數據本地化模式等。這部分中講解了《多核計算與程式設計》中幾個最重要的程式：分散式佇列中實現了自動讓每個執行緒帶有一個本地佇列、分散式查找中介紹了分段鎖的哈希表、動態負載平衡的分散式查找等，分散式記憶體管理則介紹了適應多核的記憶體管理方案，尤其是基於搶奪式的分散式記憶體管理算法，在分配和釋放共享記憶體時也幾乎不需要使用鎖，性能優異。
第5部分介紹任務分解與調度方面的知識，這也是《多核計算與程式設計》中最重要的內容，包括任務圖分解與調度的實現方法，動態任務分解與調度的實現方法等。其中還介紹了使用動態嵌套任務調度進行並行計算的方法，給出了用動態嵌套任務調度實現ParallelForo、並行快速排序、並行歸併的實例。
最後一章中還介紹了Lock-Free編程（使用CAS原子操作進行編程）的基礎知識，如ABA問題，記憶體刪除問題等，並給出了一個Lock-Free的佇列的實現實例。
目錄
第1部分基礎知識
1多核計算概述
1.1多核CPU概述
1.1.1多核計算將成為發展趨勢
1.1.2多核CPU硬體架構介紹
1.1.3多核給程式設計師帶來的機遇和挑戰
1.2多核編程會遇到那些問題
1.2.1並發性問題
1.2.2CPU飢餓問題
1.2.3任務的分解與調度問題
1.2.4加速比性能問題
1.2.5節能環保問題
1.2.6擴展性問題
1.3多核編程與單核多執行緒編程的區別
1.3.1鎖競爭導致的串列化的區別
1.3.2執行緒分解與執行的區別
1.3.3CPU核負載平衡的區別
1.3.4任務調度策略的區別
1.3.5CPUCache存取的區別（偽共享問題）
1.3.6任務優先權搶占的區別
1.3.7串列計算與並行及分散式計算的區別
1.4多核編程與多機分散式編程的區別
1.4.1共享存儲與分散式存儲的區別
1.4.2分散式計算的區別
1.4.3編程環境上的區別
1.5加速比係數
1.5.1阿姆達爾定律
1.5.2Gustafson定律
1.5.3阿姆達爾定律和Gustafson定律的等價性
1.5.4Karp-Flatt度量
1.5.5實際情況中影響加速比係數的因素
1.5.6並行計算開銷情況下的加速比
1.6鎖競爭問題及對加速比的影響
1.6.1執行緒粒度因子與鎖粒度因子
1.6.2鎖競爭的性能情況
1.6.3集中式鎖競爭中的加速比分析
1.6.4隨機鎖競爭中的加速比分析
1.6.5分散式鎖競爭的加速比分析
1.6.6無鎖編程的加速比分析
1.7負載平衡問題對加速比的影響
1.7.1影響負載平衡的主要因素
1.7.2負載平衡的評價指標
1.7.3負載平衡情況下的加速比
1.8參考文獻
2多執行緒編程基礎
2.1多執行緒編程基本概念
2.1.1執行緒
2.1.2鎖
2.1.3各種系統中常用的鎖操作及信號量操作函式
2.1.4用C++實現鎖的自動釋放
2.1.5原子操作
2.1.6鎖與原子操作的區別
2.1.7有鎖計算、無鎖計算與本地計算的概念
2.2各種鎖性能比較
2.2.1各種鎖在單執行緒情況下的性能
2.2.2各種鎖在多執行緒集中式鎖競爭情況下的性能
2.2.3各種鎖在多執行緒分散式鎖競爭情況下的性能
2.3讀寫鎖算法
2.3.1讀寫鎖概念的引出
2.3.2讀寫鎖算法的分析和實現
2.3.3讀寫鎖的編碼實現
2.4多執行緒退出算法
2.4.1單個子執行緒退出算法
2.4.2多個執行緒訪問共享資源時的退出
2.4.3有鎖的多執行緒資源釋放退出算法實現
2.4.4無鎖的退出算法
2.4.5多執行緒退出算法的使用
2.5參考文獻
3OpenMP程式設計
3.1OpenMP基本概念
3.1.1fork/join並行執行模式的概念
3.1.2記憶體模型
3.1.3性能例子
3.1.4編譯器對OpenMP的支持
3.2OpenMP編程模型
3.2.1OpenMP編譯指導語句格式
3.2.2OpenMP主要命令
3.2.3OpenMP主要子句
3.2.4OpenMP主要庫函式
3.3執行緒創建與工作分攤
3.3.1parallel命令
3.3.2for和parallelfor命令
3.3.3if子句（條件執行並行）
3.3.4動態設定並行循環的執行緒數量
3.3.5循環並行化的問題
3.3.6sections和section命令
3.3.7single命令
3.3.8master命令
3.4數據處理
3.4.1private子句
3.4.2firstprivate子句
3.4.3lastprivate子句
3.4.4threadprivate子句
3.4.5shared子句
3.4.6default子句
3.4.7reduction子句
3.4.8copyin子句
3.4.9copyprivate子句
3.5任務調度
3.5.1Schedule子句用法
3.5.2靜態調度(static)
3.5.3動態調度(dynamic)
3.5.4guided調度（guided）
3.5.5runtime調度（rumtime）
3.5.6任務調度與偽共享問題
3.6執行緒間的同步
3.6.1barrier命令
3.6.2critical命令
3.6.3atomic命令
3.6.4ordered命令和子句
3.6.5nowait子句
3.6.6flush命令
3.7OpenMP庫函式詳解
3.7.1執行環境函式
3.7.2鎖操作函式
3.7.3時間操作函式
3.8OpenMP環境變數
3.8.1OMP_DYNAMIC
3.8.2OMP_NUM_THREADS
3.8.3OMP_NESTED
3.8.4OMP_SCHEDULE
3.9OpenMP內部控制變數及相關流程
3.9.1內部控制變數
3.9.2任務調度流程
3.9.3執行緒數量決定流程
3.10參考文獻
第2部份基礎數據結構與算法
4數組
4.1棧
4.1.1棧的基本概念
4.1.2棧的編碼實現
4.1.3多執行緒棧的實現
4.2對數組進行快速排序
4.2.1排序算法介紹
4.2.2串列快速排序基本思想
4.2.3串列快速排序的代碼實現
4.2.4非遞歸的快速排序算法
4.2.5快速排序算法的複雜度分析
4.3對數組進行查找
4.3.1順序查找
4.3.2二分查找
4.4實例：用數組管理一個HOOK功能
4.4.1單個函式的HOOK實現
4.4.2多個函式的HOOK實現
4.4.3HOOK功能的套用簡介
4.4.4HOOK使用的注意事項
4.5參考文獻
5鍊表
5.1單向鍊表
5.1.1存儲表示
5.1.2接口設計
5.1.3添加節點到鍊表頭部
5.1.4基本功能編碼實現
5.2單向鍊表的排序
5.2.1插入排序
5.2.2歸併插入排序
5.3雙向鍊表
5.3.1雙向鍊表的基本概念
5.3.2雙向鍊表的設計
5.3.3雙向鍊表的操作接口
5.3.4雙向鍊表的編碼實現
5.4鍊表的逐個節點遍歷
5.4.1逐個節點遍歷基本概念
5.4.2逐個節點遍歷編碼實現
5.5多執行緒遍歷算法
5.5.1多執行緒鍊表的設計和編碼實現
5.5.2多執行緒鍊表的4種遍歷方案
5.5.3多個執行緒同時遍歷的情況
5.6實例：使用鍊表管理簡訊息系統的CACHE
5.6.1簡訊息系統的CACHE管理基本概念
5.6.2簡訊息系統的傳送和接收分析
5.6.3簡訊息系統CACHE管理的編碼實現
6哈希表
6.1哈希表
6.1.1哈希表的基本概念
6.1.2哈希表的索引方法
6.1.3哈希表的衝突解決方法
6.1.4哈希表基本操作的原始碼
6.2哈希鍊表
6.2.1哈希表和數組、鍊表的效率比較
6.2.2時間效率和空間效率的關係
6.2.3哈希鍊表的基本概念
6.2.4哈希鍊表的操作
6.2.5哈希鍊表的編碼實現
6.3實例：WebServer的動態CACHE檔案管理
6.3.1WebServer的動態CACHE檔案管理基本概念
6.3.2CACHE檔案管理功能的設計
6.3.3CACHE檔案管理功能的編碼實現
6.4參考文獻
7普通樹與二叉樹
7.1普通樹
7.1.1普通樹的描述方法
7.1.2樹的操作接口設計
7.1.3樹的遍歷算法
7.1.4樹的編碼實現
7.1.5使用樹的遍歷算法來實現Xcopy功能
7.2二叉樹
7.2.1二叉樹的基本概念
7.2.2二叉樹的樹梢及二叉樹的高度
7.2.3二叉樹的描述方法
7.3二叉排序樹
7.3.1二叉排序樹的基本概念
7.3.2二叉排序樹的查找
7.3.3二叉排序樹的插入
7.3.4二叉排序樹的刪除
7.3.5二叉排序樹的遍歷
7.3.6二叉排序樹的旋轉操作
8AVL搜尋樹
8.1AVL搜尋樹的基本概念
8.2AVL搜尋樹的插入
8.2.1插入操作需要考慮的問題
8.2.2不存在不平衡節點的情況分析
8.2.3不平衡A節點的情況分析
8.2.4存在不平衡節點的四種情況分析
8.2.5LL型不平衡情況的調整
8.2.6LR型不平衡情況的調整
8.2.7插入操作的偽代碼描述
8.3AVL搜尋樹的刪除
8.3.1A節點的確定
8.3.2幾種不平衡情況的分析
8.3.3L0型調整分析
8.3.4L-1型調整分析
8.3.5L1型調整分析
8.3.6刪除操作的偽代碼描述
8.4負載平衡的AVL樹
8.4.1基本概念的引出
8.4.2插入操作中負載因子的調整
8.4.3刪除操作中負載因子的調整
8.4.4L0和L-1型調整分析
8.4.5L1型調整分析
8.5AVL樹的原始碼
8.5.1數據結構定義
8.5.2創建、釋放、查找等操作
8.5.3旋轉操作函式
8.5.4插入操作函式
8.5.5刪除操作函式
8.6參考文獻
9複合二叉樹
9.1哈希紅黑樹
9.1.1哈希紅黑樹的基本概念
9.1.1哈希紅黑樹的查找
9.1.3哈希紅黑樹的插入
9.1.4哈希紅黑樹的刪除
9.1.5哈希紅黑樹的釋放
9.1.6哈希紅黑樹的遍歷
9.1.7哈希紅黑樹的編碼實現
9.1.8哈希紅黑樹的效率分析
9.2哈希AVL樹
9.2.1哈希AVL樹的基本概念
9.2.2哈希AVL樹的查找
9.2.3哈希AVL樹的插入
9.2.4哈希AVL樹的刪除
9.2.5哈希AVL樹的釋放
9.2.6哈希AVL樹的遍歷
9.2.7哈希AVL樹的編碼實現
9.3複合數據結構的分類
9.4抗DoS/DdoS攻擊的實例
9.4.1DoS/DdoS攻擊的概念
9.4.2常見DoS/DdoS攻擊手段及防範策略
9.4.3抗DoS/DdoS攻擊的實現
9.4.4抗DoS/DdoS攻擊的編碼實現
9.5參考文獻
第3部分並行計算
10並行程式設計模式
10.1基本概念
10.1.1強並行計算與弱並行計算
10.1.2並行程式設計模式的基本思路
10.2模式數據分解模式
10.3分治模式
10.3.1子問題求解時的負載平衡問題
10.3.2子問題的解的合併可能引起的串列化問題
10.4流水線模式
10.5任務並行模式
10.6任務調度模式
10.6.1任務圖調度模式
10.6.2動態任務調度模式
11並行搜尋
11.1並行順序搜尋
11.1.1並行搜尋指定數據
11.1.2並行搜尋最大數
11.1.3終止檢測算法
11.2串列Dijkstra最短路徑搜尋
11.2.1Dijkstra最短路徑算法的描述
11.2.2Dijkstra最短路徑算法的過程圖解
11.2.3偽代碼描述
11.2.4算法流程圖
11.2.5C/C++代碼實現
11.3並行最短路徑算法
11.3.1Dijkstra算法的並行化
11.3.2並行Dijkstra算法的代碼實現
11.3.3其他並行最短路徑算法的介紹和分析
11.4參考文獻
12並行排序
12.1並行排序概述
12.2冒泡排序
12.2.1串列冒泡排序
12.2.2奇偶排序
12.3快速排序
12.3.1串列快速排序基本思想
12.3.2串列快速排序的代碼實現
12.3.3快速排序並行化方法
12.3.4開源項目mcstl中的並行快速排序
12.3.5基於任務竊取的快速排序
12.4並行歸併排序
12.4.1串列歸併算法
12.4.2Cole並行歸併算法
12.4.3並行快速歸併排序
12.5基數排序
12.5.1串列鏈式基數排序
12.5.2串列數組基數排序
12.5.3一步到位的分層排序
12.5.4負載平衡的並行基數排序
12.5.5分區的並行基數排序
13並行數值計算
13.1多核並行數值計算面臨的問題
13.1.1Cache的命中率問題
13.1.2偽共享問題
13.2求和及前綴求和
13.3矩陣相加
13.4矩陣相乘
13.4.1基本概念
13.4.2串列算法
13.4.3並行算法
13.5矩陣向量相乘
13.6並行隨機數生成
13.7參考文獻
第4部分共享資源分散式計算
14分散式計算設計模式
14.1基本概念
14.1.1共享資源的計算分解
14.1.2共享資源計算的負載均衡問題
14.1.3共享資源計算的算法設計思路與方法
14.2執行緒分組競爭模式
14.2.1標準的執行緒分組競爭模式
14.2.2執行緒分組競爭模式的變種
14.3執行緒隨機競爭模式
14.3.1基本概念
14.3.2加速比性能的保證
14.4數據本地化模式
14.4.1取得比單核多執行緒更好的性能
14.4.2數據本地化模式
14.4.3優缺點分析
14.5分散式數據結構設計
14.5.1複合數據結構設計方法
14.5.2分散式數據結構設計
14.5.3分散式數據結構主要問題
14.6參考文獻
15分散式佇列
15.1串列佇列
15.1.1簡單環形佇列
15.1.2STL中的Deque
15.1.3動態環形佇列
15.2佇列池
15.2.1共享佇列
15.2.2訊息佇列
15.2.3佇列池
15.2.4佇列池的幾種實現方案
15.2.5佇列池的使用實例
15.3帶本地計算的分散式佇列
15.3.1基本思想
15.3.2本地化佇列的實現
15.3.3任務偷取佇列的實現
15.3.4分散式佇列的實現
15.3.5執行緒池CThreadPool的實現
15.3.6執行緒池CThreadPool的代碼實現
15.3.7CDistributedQueue原始碼
15.3.8CDistributedQueue的使用實例
16分散式查找
16.1多核中查找的問題與主要思路
16.2靜態負載平衡的二級查找結構設計
16.2.1二級查找結構設計
16.2.2分散式哈希AVL樹
16.2.3分散式順序AVL樹
16.3動態負載平衡的多級查找結構設計
16.3.1分散式查找中的負載平衡問題
16.3.2多級查找結構設計方法
16.3.3多級查找表的查找算法
16.3.4多級查找表的插入操作算法
16.3.5多級查找表的刪除操作算法
16.3.6多級順序表
16.3.7多級索引AVL樹
16.3.8分散式哈希多級AVL樹
16.3.9分散式順序多級AVL樹
16.4多核環境中查找算法的選用方法
16.5動態WebCache設計實例
17分散式記憶體管理
17.1多核記憶體管理的基本思想
17.1.1記憶體管理方面的需求
17.1.2多核系統中的記憶體管理思路
17.2等尺寸記憶體管理
17.2.1Freelist記憶體管理基本概念
17.2.2Freelist編碼實現
17.2.3FreeLists記憶體管理
17.3Intel開源項目TBB中的記憶體管理
17.3.1偽共享問題
17.3.2Cache對齊的記憶體管理
17.3.3數據結構
17.3.4將記憶體管理器映射到執行緒
17.3.5分配和釋放算法
17.3.6執行緒退出時的記憶體回收
17.4搶奪式記憶體管理算法
17.4.1算法基本思想
17.4.2碎片重組回收利用技術
17.4.3搶奪式算法的詳細算法流程
17.4.4代碼實現
17.5偽共享問題的深入分析
17.5.1記憶體釋放時的偽共享問題
17.5.2偽共享問題的機率分析
17.5.3用戶程式使用記憶體過程中的偽共享問題
17.5.4分散式記憶體管理的進一步改進措施
17.6參考文獻
第5部分任務分解與調度
18任務圖分解與調度
18.1任務分解與調度的問題
18.1.1使用OpenMP調度的問題
18.1.2任務圖調度模型
18.1.3任務圖調度算法簡介
18.2任務組調度算法
18.2.1基本思路
18.2.2任務組調度算法
18.2.3算法流程圖
18.2.4數據結構與接口設計
18.2.5代碼實現
18.2.6任務組調度的套用分析
18.2.7誤差下降調度算法
18.3任務圖調度算法
18.3.1任務圖的分層算法
18.3.2分層算法過程圖解
18.3.3數據結構和接口設計
18.3.4分層算法的代碼實現
18.3.5任務調度器的代碼實現
18.3.6實例：任務圖調度器的使用
18.4手工任務分解的原則和方法
18.4.1任務間負載均衡的影響因素
18.4.2任務分解原則和方法
18.5參考文獻
19動態任務分解與調度
19.1動態任務分解的兩種類型
19.2非嵌套型動態任務調度
19.2.1網路伺服器軟體中的任務調度
19.2.2使用分散式佇列的調度方法
19.2.3CTaskScheduler的設計
19.2.4CTaskScheduler的代碼實現
19.3嵌套型動態任務調度
19.3.1基本思想
19.3.2CNestTaskScheduler的設計
19.3.3CNestTaskScheduler的代碼實現
19.3.4CNestTaskScheduler使用方法
19.4實例：用任務調度器實現parallel_for
19.4.1parallel_for的實現
19.4.2用parallel_for進行並行快速排序
19.4.3用parallel_for進行並行歸併
19.5參考文獻
20Lock-Free編程基礎
20.1Lock-Free編程基本概念和問題
20.1.1CAS原子操作
20.1.2ABA問題
20.1.3ABA問題的解決方法
20.1.4記憶體刪除問題
20.1.5數據競爭問題
20.2Lock-Free的佇列
20.2.1無鎖佇列的鏈式實現方法
20.2.2串列實現方法
20.2.3出隊操作的Lock-Free實現
20.2.4進隊操作的Lock-Free實現
20.2.5CLockFreeQueue的實現代碼
20.3Lock-Free程式的問題分析
20.4參考文獻
附錄1本書代碼和CAPI開源項目源檔案對照表
附錄2多核編程的四層境界
作者簡介
周偉明，1994年畢業於上海交通大學，曾就職於美國加州的DASCOMInc．公司和華為技術有限公司等企業。擔任過網路安全軟體、網路伺服器軟體、機器翻譯軟體、工具軟體、嵌入式系統軟體等研發工作，親自編寫過的原始碼逾40萬行。著有《多任務下的數據結構與算法》（華中科技大學出版社出版）、《軟體測試實踐》（電子工業出版社出版）。
