《第二章并行程序設(shè)計基礎(chǔ)（并行計算基礎(chǔ)）課件》由會員分享，可在線閱讀，更多相關(guān)《第二章并行程序設(shè)計基礎(chǔ)（并行計算基礎(chǔ)）課件（27頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,,單擊此處編輯母版文本樣式,,第二級,,第三級,,*,*,*,第二章 并行計算基礎(chǔ),組成并行計算機的各個部分：,,節(jié)點（,node,）：每個節(jié)點由多個處理器構(gòu)成，可以直接進(jìn)行輸入輸出（,I/O,）操作；,,互聯(lián)網(wǎng)絡(luò)（,interconnect network,）：所有節(jié)點通過互聯(lián)網(wǎng)絡(luò)相互連接通信；,,內(nèi)存 （,memory,）：內(nèi)存由多個存儲模塊組成,,1,、與節(jié)點對稱的分布在互聯(lián)網(wǎng)絡(luò)的兩側(cè)；,,2,、位于各個節(jié)點的內(nèi)部。,第二章 并行計算基礎(chǔ),,內(nèi)存模塊與節(jié)點分離,內(nèi)存模塊位于節(jié)點內(nèi)部,多級存儲體系結(jié)構(gòu),解決內(nèi)存墻（,memory wall,）性能瓶頸問題；

2、,,節(jié)點內(nèi)部的,cache,稱為二級,cache,（,L2 cache,）；,,處理器內(nèi)部更小的,cache,成為一級,cache,（,L1 cache,）；,,L1 cache,連接,CPU,寄存器和,L2 cache,，負(fù)責(zé)緩存,L2 cache,中的數(shù)據(jù)到寄存器中。,多級存儲體系結(jié)構(gòu),并行計算機的多級存儲結(jié)構(gòu)主要包括兩個問題：,,Cache,的映射策略，即,cache,如何從內(nèi)存中取得數(shù)據(jù)進(jìn)行存儲；,,,節(jié)點內(nèi)部或者節(jié)點之間內(nèi)存的訪問模式,。,,cache,原理，,cache,以,cache,線為基本單位，每條,cache,包含,L,個字，每個字,8,個字節(jié)。例如，,L=4,，則表示,c

3、ache,線包含,4*8=32,個字節(jié)。內(nèi)存空間分割成塊（,block,），每個塊大小與,cache,線長度一致，數(shù)據(jù)在內(nèi)存和,cache,之間的移動以,cache,線為基本單位,。,,For i=1 to M,,,,A[i]=A[i]+2*B[i],,,如果操作數(shù)存在,cache,中，稱該次訪問是命中的，否則，該次操作是“撲空”的,。,多級存儲體系結(jié)構(gòu),cache,的映射策略（內(nèi)存塊和,cache,線之間如何建立相互映射關(guān)系）,：,,直接映射策略（,direct mapping strategy,）：每個內(nèi)存塊只能被唯一的映射到一條,cache,線中,；,,,K,－路組關(guān)聯(lián)映射策略 （,K-

4、way set association mapping strategy,）：,Cache,被分解為,V,個組，每個組由,K,條,cache,線組成，內(nèi)存塊按直接映射策略映射到某個組，但在該組中，內(nèi)存塊可以被映射到任意一條,cache,線；,,全關(guān)聯(lián)映射策略 （,full association mapping strategy,）,:,內(nèi)存塊可以被映射到,cache,中的任意一條,cache,線。,訪存模型,UMA,（,Uniform Memory Access,）模型：該模型內(nèi)存模塊與節(jié)點分離，分別位于互聯(lián)網(wǎng)絡(luò)的兩側(cè),,物理存儲器被所有節(jié)點共享；,,所有節(jié)點訪問任意存儲單元的時間相同；,,

5、發(fā)生訪存競爭時，仲裁策略平等對待每個節(jié)點，即每個節(jié)點機會均等；,,各節(jié)點的,CPU,可帶有局部私有高速緩存；,,外圍,I/O,設(shè)備也可以共享，且每個節(jié)點有平等的訪問權(quán)利。,訪存模型,NUMA,（,Non-Uniform Memory Access,）模型：該模型內(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ā)生訪存競爭

6、時，仲裁策略對節(jié)點可能是不等價的；,,各節(jié)點的,CPU,可帶有局部私有高速緩存 （,cache,）；,,外圍,I/O,設(shè)備也可以共享，但對各節(jié)點是不等價的。,訪存模型,COMA,（,Cache-Only Memory Access,）模型：全高速緩存存儲訪問模型,,各處理器節(jié)點中沒有存儲層次結(jié)構(gòu)，全部高速緩存組成了全局地址空間；,,利用分布的高速緩存目錄進(jìn)行遠(yuǎn)程高速緩存的訪問；,,COMA,中的高速緩存容量一般都大于,2,級高速緩存容量；,,使用,COMA,時，數(shù)據(jù)開始時可以任意分配，因為在運行時它最終會被遷移到要用到它的地方。,并行計算模型,SIMD,同步并行計算模型,,共享存儲的,SIMD

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

8、urrent-Read and Exclusive-Write,） ，允許同時讀但不允許同時寫；,,PRAM-CRCW,（,Concurrent-Read and Concurrent-Write,） ，允許同時讀和同時寫。,,優(yōu)點：,,適合于并行算法的表達(dá)、分析和比較；,,使用簡單，很多諸如處理器間通信、存儲管理和進(jìn)程同步等并行計算機的低級細(xì)節(jié)均隱含于模型中；,,易于設(shè)計算法和稍加修改便可運行在不同的并行計算機上；,,且有可能加入一些諸如同步和通信等需要考慮的方面。,同步并行計算模型,SIMD,分布存儲模型,,采用一維線性連接的,SIMD,模型，簡記為,SIMD-LC,,采用網(wǎng)孔連接的,SI

9、MD,模型，簡記為,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,,MIMD,異步計算模型,——APRAM,模型,APRAM,特點,:,,每個處理器都有其本地存儲器、局部時鐘和局部程序,,處理器間的通信經(jīng)過

10、共享全局存儲器,,無全局時鐘，各處理器異步地獨立執(zhí)行各自的指令,,處理器任何時間依賴關(guān)系需明確地在各處理器的程序中加入同步障（,Synchronization Barrier,）,,一條指令可在非確定但有限的時間內(nèi)完成。,,MIMD,異步計算模型,——PRAM,模型,APRAM,模型中有四類指令,:,,全局讀，將全局存儲單元中的內(nèi)容讀入本地存儲器單元中,,局部操作，對本地存儲器中的數(shù)執(zhí)行操作，其結(jié)果存入本地存儲器中,,全局寫，將本地存儲器單元中的內(nèi)容寫入全本地存儲器單元中,,同步，同步是計算中的一個邏輯點，在該點各處理器均需等待別的處理器到達(dá)后才能繼續(xù)執(zhí)行其局部程序,,MIMD,異步計算模型,

11、——BSP,模型,大同步并行,BSP,（,Bulk Synchronous Parallel,）模型,作為計算機語言和體系結(jié)構(gòu)之間的橋梁，由下述三個參數(shù)描述分布存儲的并行計算機模型：,,處理器,/,存儲器模塊（下文簡稱處理器）；,,處理器模塊之間點到點信息傳遞的路由器；,,執(zhí)行以時間間隔,L,為周期的路障同步器。,MIMD,異步計算模型,——BSP,模型,特點：,,將處理器和路由器分開，強調(diào)了計算任務(wù)和通信任務(wù)的分開，而路由器僅施行點到點的消息傳遞，不提供組合、復(fù)制或廣播等功能，這樣做既掩蓋了具體的互聯(lián)網(wǎng)絡(luò)拓?fù)?，又簡化了通信協(xié)議；,,采用路障方式的以硬件實現(xiàn)的全局同步是在可控的粗粒度級，從而提

12、供了執(zhí)行緊耦合同步式并行算法的有效方式，而程序員并無過分的負(fù)擔(dān)；,,在分析,BSP,模型的性能時，假定局部操作可在一個時間步內(nèi)完成，而在每一超級步中，一個處理器至多發(fā)送或接受,h,條消息（,h-relation,）,,MIMD,異步計算模型,——LogP,C3,模型,LogP,模型,,一種分布存儲的、點到點通信的多處理機模型，其中通信網(wǎng)絡(luò)由一組參數(shù)來描述，但它并不涉及到具體的網(wǎng)絡(luò)結(jié)構(gòu)，也不假定算法一定要用顯式的消息傳遞操作進(jìn)行描述。,,C3,（,Computation, Communication, Congestion,）,,是一個與體系結(jié)構(gòu)無關(guān)的粗粒度的并行計算模型，旨在能反映計算復(fù)雜度，

13、通信模式和通信期間潛在的擁擠等因素對粗粒度網(wǎng)絡(luò)算法的影響。,,并行編程環(huán)境,比較流行的并行編程環(huán)境主要有,3,類：消息傳遞、共享存儲和數(shù)據(jù)并行，,,共享存儲并行編程基于線程級細(xì)粒度并行，可移植性不如消息傳遞并行編程，但是，由于他們支持?jǐn)?shù)據(jù)的共享存儲，所以并行編程的難度較小，但一般情況下，當(dāng)處理機個數(shù)較多時，其并行性能明顯不如消息傳遞編程,；,,消息傳遞并行編程基于大粒度的進(jìn)程級并行，具有最好的可擴展性，幾乎被所有當(dāng)前流行的各類并行計算機所支持，其具有較好的可擴展性，但是，消息傳遞并行編程只能支持進(jìn)程間的分布式存儲模式，即各個進(jìn)程只能支持訪問其局部內(nèi)存空間，而對其他進(jìn)程的局部內(nèi)存空間的訪問只能通

14、過消息傳遞來實現(xiàn)，因此，學(xué)習(xí)和使用消息傳遞并行編程的難度均大于共享存儲和數(shù)據(jù)并行這兩種編程模式。,,并行編程環(huán)境,3,類并行編程環(huán)境的主要特征的比較總結(jié),,特征,消息傳遞,共享存儲,數(shù)據(jù)并行,典型代表,MPI, PVM,OpenMP,HPF,可移植性,所有主流并行計算機,SMP, DSM,SMP, DSM, MPP,并行粒度,進(jìn)程級大粒度,線程級細(xì)粒度,進(jìn)程級細(xì)粒度,并行操作方式,異步,異步,松散同步,數(shù)據(jù)存儲模式,分布式存儲,共享存儲,共享存儲,數(shù)據(jù)分配方式,顯式,隱式,半隱式,學(xué)習(xí)入門難度,較難,容易,偏易,可擴展性,好,較差,一般,并行計算性能評測,加速比（,Speedup,）：,用,最

15、優(yōu)串行算法的執(zhí)行時間,除以,并行程序的執(zhí)行時間,所得到的比值，能夠準(zhǔn)確描述對程序并行化之后所獲得的性能收益。,,,最優(yōu)串行算法的執(zhí)行時間除以并行程序的執(zhí)行時間所得到的比值,：,,,,,并行加速比就是指對于一個給定的應(yīng)用，并行算法的執(zhí)行速度相對于串行算法的執(zhí)行速度加快了多少倍。,,并行計算性能評測,并行程序執(zhí)行時間,,等于從并行程序開始執(zhí)行到所有進(jìn)程執(zhí)行完畢，墻上時鐘走過的時間，也稱為墻上時間 （,wall clock time,）。對各個進(jìn)程，墻上時間可進(jìn)一步分解為計算,CPU,時間、通信,CPU,時間、同步開銷時間、同步導(dǎo)致的進(jìn)程空閑時間；,,計算,CPU,時間：,進(jìn)程指令執(zhí)行所花費的,CP

16、U,時間，包括程序本身的指令執(zhí)行占用的時間和系統(tǒng)指令花費的時間,；,,通信,CPU,時間；,,同步開銷時間；,,進(jìn)程空閑時間：,當(dāng)一個進(jìn)程阻塞式等待其他進(jìn)程的消息時，,CPU,通常是空閑的，或者處于等待狀態(tài)。進(jìn)程空閑時間是指并行程序執(zhí)行過程中，進(jìn)程所有空閑時間總和。,,,并行計算性能評測,加速比性能定律,——Amdahl,定律,,能夠計算并行程序相對于最優(yōu)串行算法在性能提升上的理論最大值,——,表述是一種直觀、清楚的表述，他將程序劃分為可加速與不可加速兩大部分，程序總的加速比是一個關(guān)于程序中這兩部分所占比例以及可加速部分性能加速程度的函數(shù),,,,如果只對,50%,的程序加速,15%,的話，整個

17、程序總的加速比就是：,,,Amdahl,定律,:,,,,S,表示執(zhí)行程序中串行部分的比例，,n,表示處理器核的數(shù)量。假設(shè)最優(yōu)串行算法的執(zhí)行時間為一個單位時間（也就是分子為,1,）。,,處理器核在數(shù)量上能夠無限制的增加，但是無限的處理器核卻并不能帶來性能上的無限增長，無論如何，程序性能上的總是有個上限，這個要受限于串行部分所占的比例。,,,,,,程序性能優(yōu)化,串行程序性能優(yōu)化,——,是并行程序性能優(yōu)化的基礎(chǔ)，一個好的并行程序首先應(yīng)該擁有良好的單機性能，影響程序單機性能的主要因素是程序的計算流程和處理器的體系結(jié)構(gòu),,,調(diào)用高性能庫：充分利用已有的高性能程序庫是提高應(yīng)用程序?qū)嶋H性能最有效的途徑之一。

18、許多著名的高性能數(shù)學(xué)程序庫，如,BLAS,和,FFTW,；,,選擇適當(dāng)?shù)木幾g器優(yōu)化選項 ：現(xiàn)代編譯器在編譯時能夠?qū)Τ绦蜻M(jìn)行優(yōu)化，從而提高所生成的目標(biāo)代碼的性能。這些優(yōu)化功能通常是通過一組編譯選項來控制；,,合理定義數(shù)組維數(shù)：現(xiàn)代計算機為了提高內(nèi)存帶寬，多采用多體交叉并行存儲系統(tǒng)，即使用多個獨立的內(nèi)存體，對他們統(tǒng)一編址。為了充分利用多體存儲，在進(jìn)行連續(xù)數(shù)據(jù)訪問時應(yīng)該使地址的增量與內(nèi)存體數(shù)的最大公約數(shù)盡量的小，特別要避免地址增量正好是體數(shù)的倍數(shù)的情況，因為此時所有的訪問將集中在一個存儲體中；,,程序性能優(yōu)化,串行程序性能優(yōu)化,,注意嵌套循環(huán)的順序：提高,cache,使用效率的一個簡單原則就是盡量改

19、善數(shù)據(jù)訪問的局部性，數(shù)據(jù)訪問的局部性包括空間局部性和時間局部性，空間局部性指的是訪問了一個地址后，會緊接著訪問他的鄰居地址。在嵌套的多循環(huán)語句中，循環(huán)順序往往對循環(huán)中數(shù)據(jù)訪問的局部性有很大的影響。在編寫嵌套的多循環(huán)代碼時，一個通用的原則就是盡量使最內(nèi)層循環(huán)的數(shù)據(jù)訪問連續(xù)進(jìn)行；,,數(shù)據(jù)分塊和循環(huán)展開和一些其他方法，例如使用一些優(yōu)化工具如,Intel VTune,等。,程序性能優(yōu)化,并行程序性能優(yōu)化,——,并行程序的性能優(yōu)化相對于串行程序而言就有些復(fù)雜了，最主要的是選擇好的并行算法和通信模式，下面介紹一下常用的并行程序優(yōu)化技術(shù),,,減少通信量、提高通信粒度：主要有三個途徑：較少通信量、提高通信粒度

20、和提高通信中的并發(fā)度。提高通信粒度的有效方法就是減少通信次數(shù)，盡可能將可以一次傳遞的數(shù)據(jù)合并起來一起傳遞；,,全局通信盡量利用高效集合通信算法,：,當(dāng)組織多個進(jìn)程之間的集合通信時，使用高效的通信算法可以大大地提高通信效率，從而降低通信開銷,；,,挖掘算法的并行度，減少,CPU,空閑等待,：,些具有數(shù)據(jù)相關(guān)性的計算過程會導(dǎo)致并行運行的部分進(jìn)程空閑等待。在這種情況下，可以考慮改變算法來消除數(shù)據(jù)相關(guān)性,；,程序性能優(yōu)化,并行程序性能優(yōu)化,,負(fù)載平衡：是導(dǎo)致進(jìn)程空閑等待的另外一個重要因素。在設(shè)計并行程序時應(yīng)該充分考慮負(fù)載平衡問題，動態(tài)調(diào)整負(fù)載時要考慮負(fù)載調(diào)整的開銷及由于負(fù)載不平衡而引起的空閑等待對性能的影響，尋找最優(yōu)負(fù)載調(diào)整方案；,,通信、計算的重疊,：,通常讓通信和計算重疊進(jìn)行，利用計算時間來屏蔽通信時間，是減少通信開銷得非常有效的方法。實現(xiàn)通信與計算重疊的方法一般基于非阻塞通信，先發(fā)出非阻塞的消息接受或發(fā)送命令，然后處理與收發(fā)數(shù)據(jù)無關(guān)的計算任務(wù)，完成這些計算后再等待消息收發(fā)的完成,；,,通過引入重復(fù)計算來減少通信，即以計算換通信,：,適當(dāng)引入一些重復(fù)計算，可以減少通信量和通信次數(shù)。由于當(dāng)前大部分并行計算機的計算速度遠(yuǎn)遠(yuǎn)大于通信速度，并且在一些情況下，當(dāng)一個進(jìn)程計算時，別的進(jìn)程往往處于空閑等待狀態(tài)，因而適當(dāng)引入重復(fù)計算可以提高程序的總體性能,。,,,,,