《多核程序設(shè)計(jì)第二章并行程序設(shè)計(jì)基礎(chǔ)并行計(jì)算基礎(chǔ)課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《多核程序設(shè)計(jì)第二章并行程序設(shè)計(jì)基礎(chǔ)并行計(jì)算基礎(chǔ)課件（31頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、第二章 并行計(jì)算基礎(chǔ)l并行計(jì)算：并行計(jì)算就是將一個(gè)大規(guī)模的計(jì)算問(wèn)題分解成若干小的任務(wù)，通過(guò)運(yùn)行在多個(gè)運(yùn)算部件上的這些小任務(wù)的合作來(lái)求解一個(gè)規(guī)模很大的計(jì)算問(wèn)題的一種方法。強(qiáng)并行計(jì)算：如果一個(gè)計(jì)算由若干子計(jì)算構(gòu)成，若各子計(jì)算之間不存在依賴關(guān)系，可以并行計(jì)算，那么這種計(jì)算可以稱為強(qiáng)并行計(jì)算。弱并行計(jì)算：如果一個(gè)計(jì)算由若干子計(jì)算構(gòu)成，若各子計(jì)算之間存在依賴關(guān)系，不能并行計(jì)算，但是單個(gè)的子計(jì)算內(nèi)又可以分解為若干更小粒度的子計(jì)算，且這些更小粒度的子計(jì)算是可以并行執(zhí)行的，這種并行計(jì)算可以稱為弱并行計(jì)算。第二章 并行計(jì)算基礎(chǔ)并行計(jì)算：1l并行計(jì)算的應(yīng)用 預(yù)測(cè)模型的構(gòu)造和模擬、工程設(shè)計(jì)和自動(dòng)化、能源勘探、醫(yī)學(xué)、
2、軍事以及基礎(chǔ)理論研究等領(lǐng)域中都對(duì)計(jì)算提出了極高的要求。l并行計(jì)算三種主要的基本類型：計(jì)算密集型應(yīng)用，如大型科學(xué)工程計(jì)算與數(shù)值模擬；數(shù)據(jù)密集型應(yīng)用，如數(shù)字圖書(shū)館、數(shù)據(jù)倉(cāng)庫(kù)、數(shù)據(jù)挖掘和計(jì)算可視化等；網(wǎng)絡(luò)密集型應(yīng)用，如協(xié)同工作、遙控和遠(yuǎn)程醫(yī)療診斷等。第二章 并行計(jì)算基礎(chǔ)并行計(jì)算的應(yīng)用 第二章 并行計(jì)算基礎(chǔ)2并行程序開(kāi)發(fā)方法 l并行層次與代碼粒度 指令級(jí)并行：在多個(gè)并行層次中指令級(jí)并行是代碼粒度最小的并行，也稱為微粒度并行、甚細(xì)粒度并行；數(shù)據(jù)級(jí)并行：又稱為細(xì)粒度并行，它比指令級(jí)并行所執(zhí)行的代碼粒度要大一些，一般長(zhǎng)度為幾百條指令，這類并行通常都是在編譯階段由編譯器來(lái)負(fù)責(zé)實(shí)現(xiàn)的；控制級(jí)并行：也叫中粒度并行
3、，通常是面對(duì)過(guò)程、子過(guò)程，其代碼的長(zhǎng)度一般為幾千條指令。這一級(jí)的并行通常需要程序員的參與，一般情況下必須由程序員先對(duì)過(guò)程間的數(shù)據(jù)依賴關(guān)系進(jìn)行分析然后再開(kāi)發(fā)出相應(yīng)的并行性；任務(wù)級(jí)并行：任務(wù)級(jí)并行也叫做作業(yè)級(jí)并行、粗粒度并行，其代碼的長(zhǎng)度一般可高達(dá)數(shù)萬(wàn)條指令，一般是由加載程序和操作系統(tǒng)來(lái)負(fù)責(zé)處理的。并行程序開(kāi)發(fā)方法 并行層次與代碼粒度 3并行程序開(kāi)發(fā)方法l并行程序的開(kāi)發(fā)策略 第一種是采用將已有的串行程序進(jìn)行自動(dòng)并行化的方法來(lái)開(kāi)發(fā)適合于并行計(jì)算機(jī)運(yùn)行的并行程序；第二種是調(diào)用并行庫(kù)來(lái)實(shí)現(xiàn)并行程序的開(kāi)發(fā)；第三種是使用并行語(yǔ)言重新編寫(xiě)能運(yùn)行于高性能并行計(jì)算機(jī)上的并行代碼。并行程序開(kāi)發(fā)方法并行程序的開(kāi)發(fā)策略
4、 4并行程序設(shè)計(jì)模式 l并行程序設(shè)計(jì)模式的基本思路對(duì)數(shù)據(jù)進(jìn)行分解，將大的數(shù)據(jù)塊分解成若干小塊，每個(gè)線程處理其中的某些小塊；對(duì)計(jì)算過(guò)程進(jìn)行分解，將一個(gè)大的計(jì)算處理過(guò)程分解成若干可獨(dú)立運(yùn)行的子過(guò)程，然后每個(gè)線程運(yùn)行其中的一個(gè)或多個(gè)子過(guò)程；基于問(wèn)題進(jìn)行分解，將一個(gè)原問(wèn)題分解為若干子問(wèn)題，然后將子問(wèn)題的解合并起來(lái)成為原問(wèn)題的解。并行程序設(shè)計(jì)模式 并行程序設(shè)計(jì)模式的基本思路5并行程序設(shè)計(jì)模式l并行程序設(shè)計(jì)模式 數(shù)據(jù)分解模式：將數(shù)據(jù)分解成若干獨(dú)立的子數(shù)據(jù)塊，每個(gè)線程處理其中的一個(gè)或多個(gè)子數(shù)據(jù)塊；分治模式：將一個(gè)原問(wèn)題的求解分解為多個(gè)子問(wèn)題的求解，然后再將多個(gè)子問(wèn)題的解通過(guò)一定的計(jì)算方法合并為原問(wèn)題的解；流
5、水線模式：將一個(gè)計(jì)算過(guò)程分解成流水線式的多個(gè)步驟序列，對(duì)于每個(gè)步驟的處理使用一個(gè)或多個(gè)線程來(lái)實(shí)現(xiàn)；并行程序設(shè)計(jì)模式并行程序設(shè)計(jì)模式 6并行程序設(shè)計(jì)模式l并行程序設(shè)計(jì)模式任務(wù)并行模式：將一個(gè)大的靜態(tài)計(jì)算任務(wù)分解成若干獨(dú)立的小計(jì)算任務(wù)，讓這些小計(jì)算任務(wù)并行執(zhí)行；任務(wù)圖調(diào)度模式：將一個(gè)大的靜態(tài)任務(wù)分解成若干小的計(jì)算任務(wù)時(shí)，由于很多時(shí)候各個(gè)小任務(wù)在執(zhí)行時(shí)許多非獨(dú)立的小任務(wù)之間存在依賴關(guān)系，將這種依賴關(guān)系通過(guò)一個(gè)無(wú)環(huán)有向圖來(lái)描述，這個(gè)圖就是任務(wù)圖，對(duì)它的并行化方法是任務(wù)調(diào)度問(wèn)題，這就是任務(wù)圖調(diào)度模式;動(dòng)態(tài)任務(wù)調(diào)度模式:任務(wù)圖調(diào)度模式調(diào)度的是靜態(tài)的任務(wù)，但是在很多情況下任務(wù)不是靜態(tài)的而是在運(yùn)行過(guò)程中動(dòng)態(tài)產(chǎn)
6、生的。運(yùn)用共享資源分布式計(jì)算的知識(shí)實(shí)現(xiàn)的關(guān)于動(dòng)態(tài)任務(wù)調(diào)度的并行模式就是動(dòng)態(tài)任務(wù)調(diào)度模式，它的突出特點(diǎn)就是可以實(shí)現(xiàn)并行計(jì)算。并行程序設(shè)計(jì)模式并行程序設(shè)計(jì)模式7并行計(jì)算基礎(chǔ)l組成并行計(jì)算機(jī)的各個(gè)部分：節(jié)點(diǎn)（node）：每個(gè)節(jié)點(diǎn)由多個(gè)處理器構(gòu)成，可以直接進(jìn)行輸入輸出（I/O）操作；互聯(lián)網(wǎng)絡(luò)（interconnect network）：所有節(jié)點(diǎn)通過(guò)互聯(lián)網(wǎng)絡(luò)相互連接通信；內(nèi)存（memory）：內(nèi)存由多個(gè)存儲(chǔ)模塊組成1、與節(jié)點(diǎn)對(duì)稱的分布在互聯(lián)網(wǎng)絡(luò)的兩側(cè)；2、位于各個(gè)節(jié)點(diǎn)的內(nèi)部。并行計(jì)算基礎(chǔ)組成并行計(jì)算機(jī)的各個(gè)部分：8并行計(jì)算基礎(chǔ)內(nèi)存模塊與節(jié)點(diǎn)分離內(nèi)存模塊位于節(jié)點(diǎn)內(nèi)部并行計(jì)算基礎(chǔ)內(nèi)存模塊與節(jié)點(diǎn)分離內(nèi)存模塊位
7、于節(jié)點(diǎn)內(nèi)部9多級(jí)存儲(chǔ)體系結(jié)構(gòu)l解決內(nèi)存墻（memory wall）性能瓶頸問(wèn)題；l節(jié)點(diǎn)內(nèi)部的cache稱為二級(jí)cache（L2 cache）；l處理器內(nèi)部更小的cache成為一級(jí)cache（L1 cache）；lL1 cache連接CPU寄存器和L2 cache，負(fù)責(zé)緩存L2 cache中的數(shù)據(jù)到寄存器中。多級(jí)存儲(chǔ)體系結(jié)構(gòu)解決內(nèi)存墻（memory wall）性能瓶頸10多級(jí)存儲(chǔ)體系結(jié)構(gòu)l并行計(jì)算機(jī)的多級(jí)存儲(chǔ)結(jié)構(gòu)主要包括兩個(gè)問(wèn)題：Cache的映射策略，即cache如何從內(nèi)存中取得數(shù)據(jù)進(jìn)行存儲(chǔ)；節(jié)點(diǎn)內(nèi)部或者節(jié)點(diǎn)之間內(nèi)存的訪問(wèn)模式。lcache原理，cache以cache線為基本單位，每條cache
8、包含L個(gè)字，每個(gè)字8個(gè)字節(jié)。例如，L=4，則表示cache線包含4*8=32個(gè)字節(jié)。內(nèi)存空間分割成塊（block），每個(gè)塊大小與cache線長(zhǎng)度一致，數(shù)據(jù)在內(nèi)存和cache之間的移動(dòng)以cache線為基本單位。For i=1 to M Ai=Ai+2*Bi l如果操作數(shù)存在cache中，稱該次訪問(wèn)是命中的，否則，該次操作是“撲空”的。多級(jí)存儲(chǔ)體系結(jié)構(gòu)并行計(jì)算機(jī)的多級(jí)存儲(chǔ)結(jié)構(gòu)主要包括兩個(gè)問(wèn)題：11多級(jí)存儲(chǔ)體系結(jié)構(gòu)lcache的映射策略（內(nèi)存塊和cache線之間如何建立相互映射關(guān)系）：直接映射策略（direct mapping strategy）：每個(gè)內(nèi)存塊只能被唯一的映射到一條cache線中；K路
9、組關(guān)聯(lián)映射策略（K-way set association mapping strategy）：Cache被分解為V個(gè)組，每個(gè)組由K條cache線組成，內(nèi)存塊按直接映射策略映射到某個(gè)組，但在該組中，內(nèi)存塊可以被映射到任意一條cache線；全關(guān)聯(lián)映射策略（full association mapping strategy）:內(nèi)存塊可以被映射到cache中的任意一條cache線。多級(jí)存儲(chǔ)體系結(jié)構(gòu)cache的映射策略（內(nèi)存塊和cache線之12訪存模型lUMA（Uniform Memory Access）模型：該模型內(nèi)存模塊與節(jié)點(diǎn)分離，分別位于互聯(lián)網(wǎng)絡(luò)的兩側(cè) 物理存儲(chǔ)器被所有節(jié)點(diǎn)共享；所有節(jié)點(diǎn)訪問(wèn)任
10、意存儲(chǔ)單元的時(shí)間相同；發(fā)生訪存競(jìng)爭(zhēng)時(shí)，仲裁策略平等對(duì)待每個(gè)節(jié)點(diǎn)，即每個(gè)節(jié)點(diǎn)機(jī)會(huì)均等；各節(jié)點(diǎn)的CPU可帶有局部私有高速緩存；外圍I/O設(shè)備也可以共享，且每個(gè)節(jié)點(diǎn)有平等的訪問(wèn)權(quán)利。訪存模型UMA（Uniform Memory Access）13訪存模型lNUMA（Non-Uniform Memory Access）模型：該模型內(nèi)存模塊分布在各個(gè)節(jié)點(diǎn)內(nèi)部，所有局部?jī)?nèi)存模塊均構(gòu)成并行計(jì)算機(jī)的全局內(nèi)存模塊。內(nèi)存模塊在物理上是分布的，在邏輯上是全局共享的，這種模型也稱之為“分布式共享訪存模型”物理存儲(chǔ)器被所有節(jié)點(diǎn)共享，任意節(jié)點(diǎn)可以直接訪問(wèn)任意內(nèi)存模塊；節(jié)點(diǎn)訪問(wèn)內(nèi)存模塊的速度不同，訪問(wèn)本地存儲(chǔ)模塊的速度一般
11、是訪問(wèn)其他節(jié)點(diǎn)內(nèi)存模塊的3倍以上；發(fā)生訪存競(jìng)爭(zhēng)時(shí)，仲裁策略對(duì)節(jié)點(diǎn)可能是不等價(jià)的；各節(jié)點(diǎn)的CPU可帶有局部私有高速緩存（cache）；外圍I/O設(shè)備也可以共享，但對(duì)各節(jié)點(diǎn)是不等價(jià)的。訪存模型NUMA（Non-Uniform Memory Ac14訪存模型lCOMA（Cache-Only Memory Access）模型：全高速緩存存儲(chǔ)訪問(wèn)模型 各處理器節(jié)點(diǎn)中沒(méi)有存儲(chǔ)層次結(jié)構(gòu)，全部高速緩存組成了全局地址空間；利用分布的高速緩存目錄進(jìn)行遠(yuǎn)程高速緩存的訪問(wèn)；COMA中的高速緩存容量一般都大于2級(jí)高速緩存容量；使用COMA時(shí)，數(shù)據(jù)開(kāi)始時(shí)可以任意分配，因?yàn)樵谶\(yùn)行時(shí)它最終會(huì)被遷移到要用到它的地方。訪存模型C
12、OMA（Cache-Only Memory Acc15并行計(jì)算模型 lSIMD同步并行計(jì)算模型共享存儲(chǔ)的SIMD模型（PRAM模型）；分布存儲(chǔ)的SIMD模型（SIMD互聯(lián)網(wǎng)絡(luò)模型）lMIMD異步并行計(jì)算模型異步PRAM模型BSP模型LogP模型C3模型并行計(jì)算模型 SIMD同步并行計(jì)算模型16同步并行計(jì)算模型lSIMD共享存儲(chǔ)模型假定存在著一個(gè)容量無(wú)限大的共享存儲(chǔ)器，有有限或無(wú)限個(gè)功能相同的處理器，且均具有簡(jiǎn)單的算術(shù)運(yùn)算和邏輯判斷功能，在任何時(shí)刻各處理器均可通過(guò)共享存儲(chǔ)單元相互交換數(shù)據(jù)。lSIMD共享存儲(chǔ)模型（PRAM模型）PRAM-EREW（Exclusive-Read and Exclus
13、ive-Write），不允許同時(shí)讀和同時(shí)寫(xiě)；PRAM-CREW（Concurrent-Read and Exclusive-Write），允許同時(shí)讀但不允許同時(shí)寫(xiě)；PRAM-CRCW（Concurrent-Read and Concurrent-Write），允許同時(shí)讀和同時(shí)寫(xiě)。l優(yōu)點(diǎn)：適合于并行算法的表達(dá)、分析和比較；使用簡(jiǎn)單，很多諸如處理器間通信、存儲(chǔ)管理和進(jìn)程同步等并行計(jì)算機(jī)的低級(jí)細(xì)節(jié)均隱含于模型中；易于設(shè)計(jì)算法和稍加修改便可運(yùn)行在不同的并行計(jì)算機(jī)上；且有可能加入一些諸如同步和通信等需要考慮的方面。同步并行計(jì)算模型SIMD共享存儲(chǔ)模型假定存在著一個(gè)容量無(wú)限大17同步并行計(jì)算模型lSIMD
14、分布存儲(chǔ)模型采用一維線性連接的SIMD模型，簡(jiǎn)記為SIMD-LC采用網(wǎng)孔連接的SIMD模型，簡(jiǎn)記為SIMD-MC采用樹(shù)形連接的SIMD模型，簡(jiǎn)記為SIMD-TC采用樹(shù)網(wǎng)連接的SIMD模型，簡(jiǎn)記為SIMD-MT采用立方連接的SIMD模型，簡(jiǎn)記為SIMD-CC采用立方環(huán)連接的SIMD模型，簡(jiǎn)記為SIMD-CCC采用洗牌交換連接的SIMD模型，簡(jiǎn)記為SIMD-SE采用蝶形連接的SIMD模型，簡(jiǎn)介為SIMD-BF采用多級(jí)互聯(lián)網(wǎng)絡(luò)連接的SIMD模型，簡(jiǎn)記為SIMD-MIN同步并行計(jì)算模型SIMD分布存儲(chǔ)模型18MIMD異步計(jì)算模型APRAM模型lAPRAM特點(diǎn):每個(gè)處理器都有其本地存儲(chǔ)器、局部時(shí)鐘和局部
15、程序處理器間的通信經(jīng)過(guò)共享全局存儲(chǔ)器無(wú)全局時(shí)鐘，各處理器異步地獨(dú)立執(zhí)行各自的指令處理器任何時(shí)間依賴關(guān)系需明確地在各處理器的程序中加入同步障（Synchronization Barrier）一條指令可在非確定但有限的時(shí)間內(nèi)完成。MIMD異步計(jì)算模型APRAM模型APRAM特點(diǎn):19MIMD異步計(jì)算模型PRAM模型lAPRAM模型中有四類指令:l全局讀，將全局存儲(chǔ)單元中的內(nèi)容讀入本地存儲(chǔ)器單元中l(wèi)局部操作，對(duì)本地存儲(chǔ)器中的數(shù)執(zhí)行操作，其結(jié)果存入本地存儲(chǔ)器中l(wèi)全局寫(xiě)，將本地存儲(chǔ)器單元中的內(nèi)容寫(xiě)入全本地存儲(chǔ)器單元中l(wèi)同步，同步是計(jì)算中的一個(gè)邏輯點(diǎn)，在該點(diǎn)各處理器均需等待別的處理器到達(dá)后才能繼續(xù)執(zhí)行其局
16、部程序MIMD異步計(jì)算模型PRAM模型APRAM模型中有四類指20MIMD異步計(jì)算模型BSP模型l大同步并行BSP（Bulk Synchronous Parallel）模型 作為計(jì)算機(jī)語(yǔ)言和體系結(jié)構(gòu)之間的橋梁，由下述三個(gè)參數(shù)描述分布存儲(chǔ)的并行計(jì)算機(jī)模型：處理器/存儲(chǔ)器模塊（下文簡(jiǎn)稱處理器）；處理器模塊之間點(diǎn)到點(diǎn)信息傳遞的路由器；執(zhí)行以時(shí)間間隔L為周期的路障同步器。MIMD異步計(jì)算模型BSP模型大同步并行BSP（Bulk21MIMD異步計(jì)算模型BSP模型l特點(diǎn)：將處理器和路由器分開(kāi)，強(qiáng)調(diào)了計(jì)算任務(wù)和通信任務(wù)的分開(kāi)，而路由器僅施行點(diǎn)到點(diǎn)的消息傳遞，不提供組合、復(fù)制或廣播等功能，這樣做既掩蓋了具體的
17、互聯(lián)網(wǎng)絡(luò)拓?fù)洌趾?jiǎn)化了通信協(xié)議；采用路障方式的以硬件實(shí)現(xiàn)的全局同步是在可控的粗粒度級(jí)，從而提供了執(zhí)行緊耦合同步式并行算法的有效方式，而程序員并無(wú)過(guò)分的負(fù)擔(dān)；在分析BSP模型的性能時(shí)，假定局部操作可在一個(gè)時(shí)間步內(nèi)完成，而在每一超級(jí)步中，一個(gè)處理器至多發(fā)送或接受h條消息（h-relation）MIMD異步計(jì)算模型BSP模型特點(diǎn)：22MIMD異步計(jì)算模型LogP,C3模型lLogP模型一種分布存儲(chǔ)的、點(diǎn)到點(diǎn)通信的多處理機(jī)模型，其中通信網(wǎng)絡(luò)由一組參數(shù)來(lái)描述，但它并不涉及到具體的網(wǎng)絡(luò)結(jié)構(gòu)，也不假定算法一定要用顯式的消息傳遞操作進(jìn)行描述。lC3（Computation,Communication,Cong
18、estion）是一個(gè)與體系結(jié)構(gòu)無(wú)關(guān)的粗粒度的并行計(jì)算模型，旨在能反映計(jì)算復(fù)雜度，通信模式和通信期間潛在的擁擠等因素對(duì)粗粒度網(wǎng)絡(luò)算法的影響。MIMD異步計(jì)算模型LogP,C3模型LogP模型23并行編程環(huán)境l比較流行的并行編程環(huán)境主要有3類：消息傳遞、共享存儲(chǔ)和數(shù)據(jù)并行，共享存儲(chǔ)并行編程基于線程級(jí)細(xì)粒度并行，可移植性不如消息傳遞并行編程，但是，由于他們支持?jǐn)?shù)據(jù)的共享存儲(chǔ)，所以并行編程的難度較小，但一般情況下，當(dāng)處理機(jī)個(gè)數(shù)較多時(shí)，其并行性能明顯不如消息傳遞編程；消息傳遞并行編程基于大粒度的進(jìn)程級(jí)并行，具有最好的可擴(kuò)展性，幾乎被所有當(dāng)前流行的各類并行計(jì)算機(jī)所支持，其具有較好的可擴(kuò)展性，但是，消息傳遞
19、并行編程只能支持進(jìn)程間的分布式存儲(chǔ)模式，即各個(gè)進(jìn)程只能支持訪問(wèn)其局部?jī)?nèi)存空間，而對(duì)其他進(jìn)程的局部?jī)?nèi)存空間的訪問(wèn)只能通過(guò)消息傳遞來(lái)實(shí)現(xiàn)，因此，學(xué)習(xí)和使用消息傳遞并行編程的難度均大于共享存儲(chǔ)和數(shù)據(jù)并行這兩種編程模式。并行編程環(huán)境比較流行的并行編程環(huán)境主要有3類：消息傳遞、共享24并行編程環(huán)境l3類并行編程環(huán)境的主要特征的比較總結(jié) 特征特征消息消息傳遞共享存共享存儲(chǔ)數(shù)據(jù)并行數(shù)據(jù)并行典型代表MPI,PVMOpenMPHPF可移植性所有主流并行計(jì)算機(jī)SMP,DSMSMP,DSM,MPP并行粒度進(jìn)程級(jí)大粒度線程級(jí)細(xì)粒度進(jìn)程級(jí)細(xì)粒度并行操作方式異步異步松散同步數(shù)據(jù)存儲(chǔ)模式分布式存儲(chǔ)共享存儲(chǔ)共享存儲(chǔ)數(shù)據(jù)分配方
20、式顯式隱式半隱式學(xué)習(xí)入門難度較難容易偏易可擴(kuò)展性好較差一般并行編程環(huán)境3類并行編程環(huán)境的主要特征的比較總結(jié) 特征消息傳25并行計(jì)算性能評(píng)測(cè)l加速比（Speedup）：用最優(yōu)串行算法的執(zhí)行時(shí)間最優(yōu)串行算法的執(zhí)行時(shí)間除以并行程序的執(zhí)行時(shí)間并行程序的執(zhí)行時(shí)間所得到的比值，能夠準(zhǔn)確描述對(duì)程序并行化之后所獲得的性能收益。最優(yōu)串行算法的執(zhí)行時(shí)間除以并行程序的執(zhí)行時(shí)間所得到的比值：并行加速比就是指對(duì)于一個(gè)給定的應(yīng)用，并行算法的執(zhí)行速度相對(duì)于串行算法的執(zhí)行速度加快了多少倍。并行計(jì)算性能評(píng)測(cè)加速比（Speedup）：用最優(yōu)串行算法的執(zhí)26并行計(jì)算性能評(píng)測(cè)l并行程序執(zhí)行時(shí)間等于從并行程序開(kāi)始執(zhí)行到所有進(jìn)程執(zhí)行完畢
21、，墻上時(shí)鐘走過(guò)的時(shí)間，也稱為墻上時(shí)間（wall clock time）。對(duì)各個(gè)進(jìn)程，墻上時(shí)間可進(jìn)一步分解為計(jì)算CPU時(shí)間、通信CPU時(shí)間、同步開(kāi)銷時(shí)間、同步導(dǎo)致的進(jìn)程空閑時(shí)間；計(jì)算CPU時(shí)間：進(jìn)程指令執(zhí)行所花費(fèi)的CPU時(shí)間，包括程序本身的指令執(zhí)行占用的時(shí)間和系統(tǒng)指令花費(fèi)的時(shí)間；通信CPU時(shí)間；同步開(kāi)銷時(shí)間；進(jìn)程空閑時(shí)間：當(dāng)一個(gè)進(jìn)程阻塞式等待其他進(jìn)程的消息時(shí)，CPU通常是空閑的，或者處于等待狀態(tài)。進(jìn)程空閑時(shí)間是指并行程序執(zhí)行過(guò)程中，進(jìn)程所有空閑時(shí)間總和。并行計(jì)算性能評(píng)測(cè)并行程序執(zhí)行時(shí)間27并行計(jì)算性能評(píng)測(cè)l加速比性能定律Amdahl定律能夠計(jì)算并行程序相對(duì)于最優(yōu)串行算法在性能提升上的理論最大值表
22、述是一種直觀、清楚的表述，他將程序劃分為可加速與不可加速兩大部分，程序總的加速比是一個(gè)關(guān)于程序中這兩部分所占比例以及可加速部分性能加速程度的函數(shù) 如果只對(duì)50%的程序加速15%的話，整個(gè)程序總的加速比就是：Amdahl定律:S 表示執(zhí)行程序中串行部分的比例，n表示處理器核的數(shù)量。假設(shè)最優(yōu)串行算法的執(zhí)行時(shí)間為一個(gè)單位時(shí)間（也就是分子為1）。處理器核在數(shù)量上能夠無(wú)限制的增加，但是無(wú)限的處理器核卻并不能帶來(lái)性能上的無(wú)限增長(zhǎng)，無(wú)論如何，程序性能上的總是有個(gè)上限，這個(gè)要受限于串行部分所占的比例。并行計(jì)算性能評(píng)測(cè)加速比性能定律Amdahl定律28程序性能優(yōu)化 l串行程序性能優(yōu)化是并行程序性能優(yōu)化的基礎(chǔ)，一
23、個(gè)好的并行程序首先應(yīng)該擁有良好的單機(jī)性能，影響程序單機(jī)性能的主要因素是程序的計(jì)算流程和處理器的體系結(jié)構(gòu) 調(diào)用高性能庫(kù)：充分利用已有的高性能程序庫(kù)是提高應(yīng)用程序?qū)嶋H性能最有效的途徑之一。許多著名的高性能數(shù)學(xué)程序庫(kù)，如BLAS和FFTW；選擇適當(dāng)?shù)木幾g器優(yōu)化選項(xiàng)：現(xiàn)代編譯器在編譯時(shí)能夠?qū)Τ绦蜻M(jìn)行優(yōu)化，從而提高所生成的目標(biāo)代碼的性能。這些優(yōu)化功能通常是通過(guò)一組編譯選項(xiàng)來(lái)控制；合理定義數(shù)組維數(shù)：現(xiàn)代計(jì)算機(jī)為了提高內(nèi)存帶寬，多采用多體交叉并行存儲(chǔ)系統(tǒng)，即使用多個(gè)獨(dú)立的內(nèi)存體，對(duì)他們統(tǒng)一編址。為了充分利用多體存儲(chǔ)，在進(jìn)行連續(xù)數(shù)據(jù)訪問(wèn)時(shí)應(yīng)該使地址的增量與內(nèi)存體數(shù)的最大公約數(shù)盡量的小，特別要避免地址增量正好是
24、體數(shù)的倍數(shù)的情況，因?yàn)榇藭r(shí)所有的訪問(wèn)將集中在一個(gè)存儲(chǔ)體中；程序性能優(yōu)化 串行程序性能優(yōu)化是并行程序性能優(yōu)化的基礎(chǔ)，29程序性能優(yōu)化l串行程序性能優(yōu)化注意嵌套循環(huán)的順序：提高cache使用效率的一個(gè)簡(jiǎn)單原則就是盡量改善數(shù)據(jù)訪問(wèn)的局部性，數(shù)據(jù)訪問(wèn)的局部性包括空間局部性和時(shí)間局部性，空間局部性指的是訪問(wèn)了一個(gè)地址后，會(huì)緊接著訪問(wèn)他的鄰居地址。在嵌套的多循環(huán)語(yǔ)句中，循環(huán)順序往往對(duì)循環(huán)中數(shù)據(jù)訪問(wèn)的局部性有很大的影響。在編寫(xiě)嵌套的多循環(huán)代碼時(shí)，一個(gè)通用的原則就是盡量使最內(nèi)層循環(huán)的數(shù)據(jù)訪問(wèn)連續(xù)進(jìn)行；數(shù)據(jù)分塊和循環(huán)展開(kāi)和一些其他方法，例如使用一些優(yōu)化工具如 Intel VTune等。程序性能優(yōu)化串行程序性能優(yōu)化30多核程序設(shè)計(jì)第二章并行程序設(shè)計(jì)基礎(chǔ)并行計(jì)算基礎(chǔ)課件31
多核程序設(shè)計(jì)第二章并行程序設(shè)計(jì)基礎(chǔ)并行計(jì)算基礎(chǔ)課件
