多核計算與程序設(shè)計

前言

我的工作要求我跟蹤、了解軟件技術(shù)各領(lǐng)域的重要進(jìn)展。為此，除了頻繁閱讀最新的技術(shù)新聞，請教于各路高人，我還必須經(jīng)常留心市面上的技術(shù)圖書。大約是在2006年5月，我在中關(guān)村圖書大廈看到一本《多任務(wù)下的數(shù)據(jù)結(jié)構(gòu)與算法》，作者周偉明，這本書當(dāng)即引起了我的興趣。自從2005年初Herb Sutter發(fā)表名為《免費(fèi)午餐已經(jīng)結(jié)束》的著名文章以來，多核計算就一直是整個技術(shù)社群關(guān)注的熱點(diǎn)問題之一。不過，大家的注意力更多地集中在諸如Java．concurrent、MPI、OpenMP、Intel TBB等程序庫和Pipelining、MapReduce等編程模式上，希望能夠借助一些工具來規(guī)避并發(fā)程序設(shè)計所帶來的智力挑戰(zhàn)。毫無疑問，由于并發(fā)程序所具有的復(fù)雜性和各種“詭異”問題，在軟件項目實施中，應(yīng)盡可能利用現(xiàn)成的模式和工具，而要對“土法煉鋼”式的“創(chuàng)新”保持審慎。然而，這并不意味著開發(fā)者可以輕輕地“站在巨人肩膀上”；恰恰相反，如果沒有自下而上地對并發(fā)多任務(wù)程序設(shè)計下一番苦功進(jìn)行研究的話，這些模式和工具在我們手中反而可能成為無知和錯誤的放大器，貽害無窮?！抖嗳蝿?wù)下的數(shù)據(jù)結(jié)構(gòu)與算法》這本書的出發(fā)點(diǎn)，即是以并發(fā)和多任務(wù)的角度重新審視算法與數(shù)據(jù)結(jié)構(gòu)這樣最基本、最重要的知識，從根本上幫助讀者建立對多任務(wù)程序本質(zhì)的正確觀念、知識體系和關(guān)鍵技能，對此我是非常認(rèn)可的。

內(nèi)容概要

本書主要介紹適應(yīng)于多核（或多處理器）計算機(jī)系統(tǒng)的算法和程序，共分為五個部分進(jìn)行講解。    第1部分介紹多核編程的基礎(chǔ)知識，包括多核編程常見問題、鎖競爭、加速比、負(fù)載均衡等基本概念，多線程退出算法、讀寫鎖、旋轉(zhuǎn)鎖、原子操作等多線程編程基礎(chǔ)知識，基于OpenMP標(biāo)準(zhǔn)的并行程序設(shè)計基礎(chǔ)等；    第2部分介紹基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)與算法，包括數(shù)組、鏈表、哈希表、二叉樹、AVL樹、復(fù)合二叉樹等基本數(shù)據(jù)結(jié)構(gòu)，在鏈表那章中還講解了多線程并行遍歷的基本方法。    第3部分介紹多核并行計算方面的基礎(chǔ)知識，并行編程包括常用的編程模式如分治模式、流水線模式、任務(wù)圖分解與調(diào)度模式、動態(tài)任務(wù)調(diào)度模式等，并行搜索包括順序搜索及終止檢測算法，并行最短路徑搜索等，并行排序包括并行快速排序、并行歸并排序、并行基數(shù)排序等，并行數(shù)值計算包括并行矩陣乘法、并行前綴和計算等方面的內(nèi)容。本部分介紹的各種并行算法和程序中，重點(diǎn)介紹如何解決多核系統(tǒng)中的計算隨CPU核數(shù)的擴(kuò)展性，CPU Cache偽共享方面的問題。    第4部分介紹多核共享資源計算方面的內(nèi)容，也是本書中最重要的內(nèi)容，講解了分布式計算設(shè)計模式如線程分組競爭模式、條件同步模式、批量私有化處理模式、數(shù)據(jù)本地化模式等。這部分中講解了本書中幾個最重要的程序：分布式隊列中實現(xiàn)了自動讓每個線程帶有一個本地隊列、分布式查找中介紹了分段鎖的哈希表、動態(tài)負(fù)載平衡的分布式查找等，分布式內(nèi)存管理則介紹了適應(yīng)多核的內(nèi)存管理方案，尤其是基于搶奪式的分布式內(nèi)存管理算法，在分配和釋放共享內(nèi)存時也幾乎不需要使用鎖，性能優(yōu)異。    第5部分介紹任務(wù)分解與調(diào)度方面的知識，這也是本書中最重要的內(nèi)容，包括任務(wù)圖分解與調(diào)度的實現(xiàn)方法，動態(tài)任務(wù)分解與調(diào)度的實現(xiàn)方法等。其中還介紹了使用動態(tài)嵌套任務(wù)調(diào)度進(jìn)行并行計算的方法，給出了用動態(tài)嵌套任務(wù)調(diào)度實現(xiàn)ParallelForo、并行快速排序、并行歸并的實例。    最后一章中還介紹了Lock-Free編程（使用CAS原子操作進(jìn)行編程）的基礎(chǔ)知識，如ABA問題，內(nèi)存刪除問題等，并給出了一個Lock-Free的隊列的實現(xiàn)實例。

作者簡介

周偉明，1994年畢業(yè)于上海交通大學(xué)，曾就職于美國加州的DASCOM Inc．公司和華為技術(shù)有限公司等企業(yè)。擔(dān)任過網(wǎng)絡(luò)安全軟件、網(wǎng)絡(luò)服務(wù)器軟件、機(jī)器翻譯軟件、工具軟件、嵌入式系統(tǒng)軟件等研發(fā)工作，親自編寫過的源代碼逾40萬行。著有《多任務(wù)下的數(shù)據(jù)結(jié)構(gòu)與算法》（華中科技大學(xué)

書籍目錄

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

章節(jié)摘錄

插圖：第1部分 基礎(chǔ)知識1 多核計算概述 1.1 多核CPU概述 1.1.1 多核計算將成為發(fā)展趨勢 1.單核CPU的發(fā)展限制在過去的幾十年里，個人PC的CPU速度的發(fā)展一直按照摩爾定律進(jìn)行——半導(dǎo)體廠商能夠集成在芯片中的晶體管數(shù)量每l8～24個月翻一番，反映到實際使用中就是處理器的時鐘頻率每18～24個月增加一倍。因此，長期以來提高處理器的主頻成為提高CPU速度的不二法則。目前，單核CPU的速度已超過3 GHz。提高主頻會增加處理器的功耗和設(shè)計的復(fù)雜度，其中最大的困難就是提高主頻所帶來的高發(fā)熱問題；如果繼續(xù)提高主頻，高發(fā)熱問題將成為不可克服的障礙，它會導(dǎo)致芯片運(yùn)行不穩(wěn)定，因此目前主頻的提升空間已經(jīng)不大。在單核時代，提高性能的另一手段是用superscalar（超標(biāo)量）處理器的方式，讓處理器在一個時鐘周期內(nèi)執(zhí)行多條指令。超標(biāo)量處理器通常有兩個或多個處理單元，利用這些硬件資源，需要對軟件進(jìn)行精心設(shè)計；要適應(yīng)多流水線，需要對軟件進(jìn)行大量的修改，這些都會影響軟件的可移植性。

編輯推薦

《多核計算與程序設(shè)計》特色內(nèi)容：并行遍歷的基本方法，常見并行算法如并行搜索、并行排序、并行數(shù)值計算等在多核系統(tǒng)中的實現(xiàn)。共享資源分布式計算的基本編程模式和方法，分布式隊列，它能自動給每個線程賦予一個本地隊列，它是基于偷取的共享隊列和隊列池來實現(xiàn)的。分布式查找，包括分段鎖的哈希表，動態(tài)負(fù)載平衡的多級查找等。分布式內(nèi)存管理，它自動給每個線程生成一個本地的內(nèi)存管理器，并且?guī)缀醪恍枰褂面i進(jìn)行內(nèi)存分配和釋放（搶奪式內(nèi)存管理）。任務(wù)圖分解與調(diào)度及實現(xiàn)方法，非嵌套任務(wù)調(diào)度，可用于網(wǎng)絡(luò)服務(wù)器軟件等地方進(jìn)行任務(wù)調(diào)度。嵌套任務(wù)調(diào)度，是另一種更廣泛的任務(wù)調(diào)度方法，可以用它實現(xiàn)各種并行計算。各種程序和算法中的偽共享問題的處理，Lock-Free編程基礎(chǔ)知識。

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    多核計算與程序設(shè)計 PDF格式下載

---