多核程序設(shè)計第二章并行程序設(shè)計基礎(chǔ)并行計算基礎(chǔ)課件

第二章并行計算基礎(chǔ)并行計算：并行計算就是將一個大規(guī)模的計算問題分解成若干小的任務(wù)，通過運行在多個運算部件上的這些小任務(wù)的合作來求解一個規(guī)模很大的計算問題的一種方法。強并行計算：如果一個計算由若干子計算構(gòu)成，若各子計算之間不存在依賴關(guān)系，可以并行計算，那么這種計算可以稱為強并行計算。弱并行計算：如果一個計算由若干子計算構(gòu)成，若各子計算之間存在依賴關(guān)系，不能并行計算，但是單個的子計算內(nèi)又可以分解為若干更小粒度的子計算，且這些更小粒度的子計算是可以并行執(zhí)行的，這種并行計算可以稱為弱并行計算。第二章并行計算基礎(chǔ)并行計算：1并行計算的應(yīng)用預(yù)測模型的構(gòu)造和模擬、工程設(shè)計和自動化、能源勘探、醫(yī)學(xué)、軍事以及基礎(chǔ)理論研究等領(lǐng)域中都對計算提出了極高的要求。并行計算三種主要的基本類型：計算密集型應(yīng)用，如大型科學(xué)工程計算與數(shù)值模擬；數(shù)據(jù)密集型應(yīng)用，如數(shù)字圖書館、數(shù)據(jù)倉庫、數(shù)據(jù)挖掘和計算可視化等；網(wǎng)絡(luò)密集型應(yīng)用，如協(xié)同工作、遙控和遠程醫(yī)療診斷等。第二章并行計算基礎(chǔ)并行計算的應(yīng)用第二章并行計算基礎(chǔ)2并行程序開發(fā)方法

并行層次與代碼粒度指令級并行：在多個并行層次中指令級并行是代碼粒度最小的并行，也稱為微粒度并行、甚細(xì)粒度并行；數(shù)據(jù)級并行：又稱為細(xì)粒度并行，它比指令級并行所執(zhí)行的代碼粒度要大一些，一般長度為幾百條指令，這類并行通常都是在編譯階段由編譯器來負(fù)責(zé)實現(xiàn)的；控制級并行：也叫中粒度并行，通常是面對過程、子過程，其代碼的長度一般為幾千條指令。這一級的并行通常需要程序員的參與，一般情況下必須由程序員先對過程間的數(shù)據(jù)依賴關(guān)系進行分析然后再開發(fā)出相應(yīng)的并行性；任務(wù)級并行：任務(wù)級并行也叫做作業(yè)級并行、粗粒度并行，其代碼的長度一般可高達數(shù)萬條指令，一般是由加載程序和操作系統(tǒng)來負(fù)責(zé)處理的。并行程序開發(fā)方法并行層次與代碼粒度3并行程序開發(fā)方法并行程序的開發(fā)策略第一種是采用將已有的串行程序進行自動并行化的方法來開發(fā)適合于并行計算機運行的并行程序；第二種是調(diào)用并行庫來實現(xiàn)并行程序的開發(fā)；第三種是使用并行語言重新編寫能運行于高性能并行計算機上的并行代碼。并行程序開發(fā)方法并行程序的開發(fā)策略4并行程序設(shè)計模式

并行程序設(shè)計模式的基本思路對數(shù)據(jù)進行分解，將大的數(shù)據(jù)塊分解成若干小塊，每個線程處理其中的某些小塊；對計算過程進行分解，將一個大的計算處理過程分解成若干可獨立運行的子過程，然后每個線程運行其中的一個或多個子過程；基于問題進行分解，將一個原問題分解為若干子問題，然后將子問題的解合并起來成為原問題的解。并行程序設(shè)計模式并行程序設(shè)計模式的基本思路5并行程序設(shè)計模式并行程序設(shè)計模式數(shù)據(jù)分解模式：將數(shù)據(jù)分解成若干獨立的子數(shù)據(jù)塊，每個線程處理其中的一個或多個子數(shù)據(jù)塊；分治模式：將一個原問題的求解分解為多個子問題的求解，然后再將多個子問題的解通過一定的計算方法合并為原問題的解；流水線模式：將一個計算過程分解成流水線式的多個步驟序列，對于每個步驟的處理使用一個或多個線程來實現(xiàn)；并行程序設(shè)計模式并行程序設(shè)計模式6并行程序設(shè)計模式并行程序設(shè)計模式任務(wù)并行模式：將一個大的靜態(tài)計算任務(wù)分解成若干獨立的小計算任務(wù)，讓這些小計算任務(wù)并行執(zhí)行；任務(wù)圖調(diào)度模式：將一個大的靜態(tài)任務(wù)分解成若干小的計算任務(wù)時，由于很多時候各個小任務(wù)在執(zhí)行時許多非獨立的小任務(wù)之間存在依賴關(guān)系，將這種依賴關(guān)系通過一個無環(huán)有向圖來描述，這個圖就是任務(wù)圖，對它的并行化方法是任務(wù)調(diào)度問題，這就是任務(wù)圖調(diào)度模式;動態(tài)任務(wù)調(diào)度模式:任務(wù)圖調(diào)度模式調(diào)度的是靜態(tài)的任務(wù)，但是在很多情況下任務(wù)不是靜態(tài)的而是在運行過程中動態(tài)產(chǎn)生的。運用共享資源分布式計算的知識實現(xiàn)的關(guān)于動態(tài)任務(wù)調(diào)度的并行模式就是動態(tài)任務(wù)調(diào)度模式，它的突出特點就是可以實現(xiàn)并行計算。并行程序設(shè)計模式并行程序設(shè)計模式7并行計算基礎(chǔ)組成并行計算機的各個部分：節(jié)點（node）：每個節(jié)點由多個處理器構(gòu)成，可以直接進行輸入輸出（I/O）操作；互聯(lián)網(wǎng)絡(luò)（interconnectnetwork）：所有節(jié)點通過互聯(lián)網(wǎng)絡(luò)相互連接通信；內(nèi)存（memory）：內(nèi)存由多個存儲模塊組成1、與節(jié)點對稱的分布在互聯(lián)網(wǎng)絡(luò)的兩側(cè)；2、位于各個節(jié)點的內(nèi)部。并行計算基礎(chǔ)組成并行計算機的各個部分：8并行計算基礎(chǔ)內(nèi)存模塊與節(jié)點分離內(nèi)存模塊位于節(jié)點內(nèi)部并行計算基礎(chǔ)內(nèi)存模塊與節(jié)點分離內(nèi)存模塊位于節(jié)點內(nèi)部9多級存儲體系結(jié)構(gòu)解決內(nèi)存墻（memorywall）性能瓶頸問題；節(jié)點內(nèi)部的cache稱為二級cache（L2cache）；處理器內(nèi)部更小的cache成為一級cache（L1cache）；L1cache連接CPU寄存器和L2cache，負(fù)責(zé)緩存L2cache中的數(shù)據(jù)到寄存器中。多級存儲體系結(jié)構(gòu)解決內(nèi)存墻（memorywall）性能瓶頸10多級存儲體系結(jié)構(gòu)并行計算機的多級存儲結(jié)構(gòu)主要包括兩個問題：Cache的映射策略，即cache如何從內(nèi)存中取得數(shù)據(jù)進行存儲；

節(jié)點內(nèi)部或者節(jié)點之間內(nèi)存的訪問模式。cache原理，cache以cache線為基本單位，每條cache包含L個字，每個字8個字節(jié)。例如，L=4，則表示cache線包含4*8=32個字節(jié)。內(nèi)存空間分割成塊（block），每個塊大小與cache線長度一致，數(shù)據(jù)在內(nèi)存和cache之間的移動以cache線為基本單位。Fori=1toM

A[i]=A[i]+2*B[i]

如果操作數(shù)存在cache中，稱該次訪問是命中的，否則，該次操作是“撲空”的。多級存儲體系結(jié)構(gòu)并行計算機的多級存儲結(jié)構(gòu)主要包括兩個問題：11多級存儲體系結(jié)構(gòu)cache的映射策略（內(nèi)存塊和cache線之間如何建立相互映射關(guān)系）：直接映射策略（directmappingstrategy）：每個內(nèi)存塊只能被唯一的映射到一條cache線中；

K－路組關(guān)聯(lián)映射策略（K-waysetassociationmappingstrategy）：Cache被分解為V個組，每個組由K條cache線組成，內(nèi)存塊按直接映射策略映射到某個組，但在該組中，內(nèi)存塊可以被映射到任意一條cache線；全關(guān)聯(lián)映射策略（fullassociationmappingstrategy）:內(nèi)存塊可以被映射到cache中的任意一條cache線。多級存儲體系結(jié)構(gòu)cache的映射策略（內(nèi)存塊和cache線之12訪存模型UMA（UniformMemoryAccess）模型：該模型內(nèi)存模塊與節(jié)點分離，分別位于互聯(lián)網(wǎng)絡(luò)的兩側(cè)物理存儲器被所有節(jié)點共享；所有節(jié)點訪問任意存儲單元的時間相同；發(fā)生訪存競爭時，仲裁策略平等對待每個節(jié)點，即每個節(jié)點機會均等；各節(jié)點的CPU可帶有局部私有高速緩存；外圍I/O設(shè)備也可以共享，且每個節(jié)點有平等的訪問權(quán)利。訪存模型UMA（UniformMemoryAccess）13訪存模型NUMA（Non-UniformMemoryAccess）模型：該模型內(nèi)存模塊分布在各個節(jié)點內(nèi)部，所有局部內(nèi)存模塊均構(gòu)成并行計算機的全局內(nèi)存模塊。內(nèi)存模塊在物理上是分布的，在邏輯上是全局共享的，這種模型也稱之為“分布式共享訪存模型” 物理存儲器被所有節(jié)點共享，任意節(jié)點可以直接訪問任意內(nèi)存模塊；節(jié)點訪問內(nèi)存模塊的速度不同，訪問本地存儲模塊的速度一般是訪問其他節(jié)點內(nèi)存模塊的3倍以上；發(fā)生訪存競爭時，仲裁策略對節(jié)點可能是不等價的；各節(jié)點的CPU可帶有局部私有高速緩存（cache）；外圍I/O設(shè)備也可以共享，但對各節(jié)點是不等價的。訪存模型NUMA（Non-UniformMemoryAc14訪存模型COMA（Cache-OnlyMemoryAccess）模型：全高速緩存存儲訪問模型各處理器節(jié)點中沒有存儲層次結(jié)構(gòu)，全部高速緩存組成了全局地址空間；利用分布的高速緩存目錄進行遠程高速緩存的訪問；COMA中的高速緩存容量一般都大于2級高速緩存容量；使用COMA時，數(shù)據(jù)開始時可以任意分配，因為在運行時它最終會被遷移到要用到它的地方。訪存模型COMA（Cache-OnlyMemoryAcc15并行計算模型

SIMD同步并行計算模型共享存儲的SIMD模型（PRAM模型）；分布存儲的SIMD模型（SIMD互聯(lián)網(wǎng)絡(luò)模型）MIMD異步并行計算模型異步PRAM模型BSP模型LogP模型C3模型并行計算模型SIMD同步并行計算模型16同步并行計算模型SIMD共享存儲模型假定存在著一個容量無限大的共享存儲器，有有限或無限個功能相同的處理器，且均具有簡單的算術(shù)運算和邏輯判斷功能，在任何時刻各處理器均可通過共享存儲單元相互交換數(shù)據(jù)。

SIMD共享存儲模型（PRAM模型）PRAM-EREW（Exclusive-ReadandExclusive-Write），不允許同時讀和同時寫；PRAM-CREW（Concurrent-ReadandExclusive-Write），允許同時讀但不允許同時寫；PRAM-CRCW（Concurrent-ReadandConcurrent-Write），允許同時讀和同時寫。優(yōu)點：適合于并行算法的表達、分析和比較；使用簡單，很多諸如處理器間通信、存儲管理和進程同步等并行計算機的低級細(xì)節(jié)均隱含于模型中；易于設(shè)計算法和稍加修改便可運行在不同的并行計算機上；且有可能加入一些諸如同步和通信等需要考慮的方面。同步并行計算模型SIMD共享存儲模型假定存在著一個容量無限大17同步并行計算模型SIMD分布存儲模型采用一維線性連接的SIMD模型，簡記為SIMD-LC采用網(wǎng)孔連接的SIMD模型，簡記為SIMD-MC采用樹形連接的SIMD模型，簡記為SIMD-TC采用樹網(wǎng)連接的SIMD模型，簡記為SIMD-MT采用立方連接的SIMD模型，簡記為SIMD-CC采用立方環(huán)連接的SIMD模型，簡記為SIMD-CCC采用洗牌交換連接的SIMD模型，簡記為SIMD-SE采用蝶形連接的SIMD模型，簡介為SIMD-BF采用多級互聯(lián)網(wǎng)絡(luò)連接的SIMD模型，簡記為SIMD-MIN同步并行計算模型SIMD分布存儲模型18MIMD異步計算模型——APRAM模型APRAM特點:每個處理器都有其本地存儲器、局部時鐘和局部程序處理器間的通信經(jīng)過共享全局存儲器無全局時鐘，各處理器異步地獨立執(zhí)行各自的指令處理器任何時間依賴關(guān)系需明確地在各處理器的程序中加入同步障（SynchronizationBarrier）一條指令可在非確定但有限的時間內(nèi)完成。MIMD異步計算模型——APRAM模型APRAM特點:19MIMD異步計算模型——PRAM模型APRAM模型中有四類指令:全局讀，將全局存儲單元中的內(nèi)容讀入本地存儲器單元中局部操作，對本地存儲器中的數(shù)執(zhí)行操作，其結(jié)果存入本地存儲器中全局寫，將本地存儲器單元中的內(nèi)容寫入全本地存儲器單元中同步，同步是計算中的一個邏輯點，在該點各處理器均需等待別的處理器到達后才能繼續(xù)執(zhí)行其局部程序MIMD異步計算模型——PRAM模型APRAM模型中有四類指20MIMD異步計算模型——BSP模型大同步并行BSP（BulkSynchronousParallel）模型

作為計算機語言和體系結(jié)構(gòu)之間的橋梁，由下述三個參數(shù)描述分布存儲的并行計算機模型：處理器/存儲器模塊（下文簡稱處理器）；處理器模塊之間點到點信息傳遞的路由器；執(zhí)行以時間間隔L為周期的路障同步器。MIMD異步計算模型——BSP模型大同步并行BSP（Bulk21MIMD異步計算模型——BSP模型特點：將處理器和路由器分開，強調(diào)了計算任務(wù)和通信任務(wù)的分開，而路由器僅施行點到點的消息傳遞，不提供組合、復(fù)制或廣播等功能，這樣做既掩蓋了具體的互聯(lián)網(wǎng)絡(luò)拓?fù)?，又簡化了通信協(xié)議；采用路障方式的以硬件實現(xiàn)的全局同步是在可控的粗粒度級，從而提供了執(zhí)行緊耦合同步式并行算法的有效方式，而程序員并無過分的負(fù)擔(dān)；在分析BSP模型的性能時，假定局部操作可在一個時間步內(nèi)完成，而在每一超級步中，一個處理器至多發(fā)送或接受h條消息（h-relation）MIMD異步計算模型——BSP模型特點：22MIMD異步計算模型——LogP,C3模型LogP模型一種分布存儲的、點到點通信的多處理機模型，其中通信網(wǎng)絡(luò)由一組參數(shù)來描述，但它并不涉及到具體的網(wǎng)絡(luò)結(jié)構(gòu)，也不假定算法一定要用顯式的消息傳遞操作進行描述。

C3（Computation,Communication,Congestion）是一個與體系結(jié)構(gòu)無關(guān)的粗粒度的并行計算模型，旨在能反映計算復(fù)雜度，通信模式和通信期間潛在的擁擠等因素對粗粒度網(wǎng)絡(luò)算法的影響。MIMD異步計算模型——LogP,C3模型LogP模型23并行編程環(huán)境比較流行的并行編程環(huán)境主要有3類：消息傳遞、共享存儲和數(shù)據(jù)并行，共享存儲并行編程基于線程級細(xì)粒度并行，可移植性不如消息傳遞并行編程，但是，由于他們支持?jǐn)?shù)據(jù)的共享存儲，所以并行編程的難度較小，但一般情況下，當(dāng)處理機個數(shù)較多時，其并行性能明顯不如消息傳遞編程；消息傳遞并行編程基于大粒度的進程級并行，具有最好的可擴展性，幾乎被所有當(dāng)前流行的各類并行計算機所支持，其具有較好的可擴展性，但是，消息傳遞并行編程只能支持進程間的分布式存儲模式，即各個進程只能支持訪問其局部內(nèi)存空間，而對其他進程的局部內(nèi)存空間的訪問只能通過消息傳遞來實現(xiàn)，因此，學(xué)習(xí)和使用消息傳遞并行編程的難度均大于共享存儲和數(shù)據(jù)并行這兩種編程模式。

并行編程環(huán)境比較流行的并行編程環(huán)境主要有3類：消息傳遞、共享24并行編程環(huán)境3類并行編程環(huán)境的主要特征的比較總結(jié)

特征消息傳遞共享存儲數(shù)據(jù)并行典型代表MPI,PVMOpenMPHPF可移植性所有主流并行計算機SMP,DSMSMP,DSM,MPP并行粒度進程級大粒度線程級細(xì)粒度進程級細(xì)粒度并行操作方式異步異步松散同步數(shù)據(jù)存儲模式分布式存儲共享存儲共享存儲數(shù)據(jù)分配方式顯式隱式半隱式學(xué)習(xí)入門難度較難容易偏易可擴展性好較差一般并行編程環(huán)境3類并行編程環(huán)境的主要特征的比較總結(jié)特征消息傳25并行計算性能評測加速比（Speedup）：用最優(yōu)串行算法的執(zhí)行時間除以并行程序的執(zhí)行時間所得到的比值，能夠準(zhǔn)確描述對程序并行化之后所獲得的性能收益。

最優(yōu)串行算法的執(zhí)行時間除以并行程序的執(zhí)行時間所得到的比值：并行加速比就是指對于一個給定的應(yīng)用，并行算法的執(zhí)行速度相對于串行算法的執(zhí)行速度加快了多少倍。并行計算性能評測加速比（Speedup）：用最優(yōu)串行算法的執(zhí)26并行計算性能評測并行程序執(zhí)行時間等于從并行程序開始執(zhí)行到所有進程執(zhí)行完畢，墻上時鐘走過的時間，也稱為墻上時間（wallclocktime）。對各個進程，墻上時間可進一步分解為計算CPU時間、通信CPU時間、同步開銷時間、同步導(dǎo)致的進程空閑時間；計算CPU時間：進程指令執(zhí)行所花費的CPU時間，包括程序本身的指令執(zhí)行占用的時間和系統(tǒng)指令花費的時間；通信CPU時間；同步開銷時間；進程空閑時間：當(dāng)一個進程阻塞式等待其他進程的消息時，CPU通常是空閑的，或者處于等待狀態(tài)。進程空閑時間是指并行程序執(zhí)行過程中，進程所有空閑時間總和。

并行計算性能評測并行程序執(zhí)行時間27并行計算性能評測加速比性能定律——Amdahl定律能夠計算并行程序相對于最優(yōu)串行算法在性能提升上的理論最大值——表述是一種直觀、清楚的表述，他將程序劃分為可加速與不可加速兩大部分，程序總的加速比是一個關(guān)于程序中這兩部分所占比例以及可加速部分性能加速程度的函數(shù)

如果只對50%的程序加速15%的話，整個程序總的加速比就是：

Amdahl定律:S表示執(zhí)行程序中串行部分的比例，n表示處理器核的數(shù)量。假設(shè)最優(yōu)串行算法的執(zhí)行時間為一個單位時間（也就是分子為1）。處理器核在數(shù)量上能夠無限制的增加，但是無限的