單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,*,*,*,第二章 并行計算基礎,組成并行計算機的各個部分：,節(jié)點（node）：每個節(jié)點由多個處理器構成，可以直接進行輸入輸出（I/O）操作；,互聯(lián)網絡（interconnect network）：所有節(jié)點通過互聯(lián)網絡相互連接通信；,內存（memory）：內存由多個存儲模塊組成,1、與節(jié)點對稱的分布在互聯(lián)網絡的兩側；,2、位于各個節(jié)點的內部。,第二章 并行計算基礎組成并行計算機的各個部分：,1,第二章 并行計算基礎,內存模塊與節(jié)點分離,內存模塊位于節(jié)點內部,第二章 并行計算基礎內存模塊與節(jié)點分離內存模塊位于節(jié)點內,2,多級存儲體系結構,解決內存墻（memory wall）性能瓶頸問題；,節(jié)點內部的cache稱為二級cache（L2 cache）；,處理器內部更小的cache成為一級cache（L1 cache）；,L1 cache連接CPU寄存器和L2 cache，負責緩存L2 cache中的數據到寄存器中。,多級存儲體系結構解決內存墻（memory wall）性能瓶頸,3,多級存儲體系結構,并行計算機的多級存儲結構主要包括兩個問題：,Cache的映射策略，即cache如何從內存中取得數據進行存儲；,節(jié)點內部或者節(jié)點之間內存的訪問模式。,cache原理，cache以cache線為基本單位，每條cache包含L個字，每個字8個字節(jié)。例如，L=4，則表示cache線包含4*8=32個字節(jié)。內存空間分割成塊（block），每個塊大小與cache線長度一致，數據在內存和cache之間的移動以cache線為基本單位。,For i=1 to M,Ai=Ai+2*Bi,如果操作數存在cache中，稱該次訪問是命中的，否則，該次操作是“撲空”的。,多級存儲體系結構并行計算機的多級存儲結構主要包括兩個問題：,4,多級存儲體系結構,cache的映射策略（內存塊和cache線之間如何建立相互映射關系）：,直接映射策略（direct mapping strategy）：每個內存塊只能被唯一的映射到一條cache線中,；,K路組關聯(lián)映射策略（K-way set association mapping strategy）：Cache被分解為V個組，每個組由K條cache線組成，內存塊按直接映射策略映射到某個組，但在該組中，內存塊可以被映射到任意一條cache線；,全關聯(lián)映射策略（full association mapping strategy）:內存塊可以被映射到cache中的任意一條cache線。,多級存儲體系結構cache的映射策略（內存塊和cache線之,5,訪存模型,UMA（Uniform Memory Access）模型：該模型內存模塊與節(jié)點分離，分別位于互聯(lián)網絡的兩側,物理存儲器被所有節(jié)點共享；,所有節(jié)點訪問任意存儲單元的時間相同；,發(fā)生訪存競爭時，仲裁策略平等對待每個節(jié)點，即每個節(jié)點機會均等；,各節(jié)點的CPU可帶有局部私有高速緩存；,外圍I/O設備也可以共享，且每個節(jié)點有平等的訪問權利。,訪存模型UMA（Uniform Memory Access）,6,訪存模型,NUMA（Non-Uniform Memory Access）模型：該模型內存模塊分布在各個節(jié)點內部，所有局部內存模塊均構成并行計算機的全局內存模塊。內存模塊在物理上是分布的，在邏輯上是全局共享的，這種模型也稱之為“分布式共享訪存模型”,物理存儲器被所有節(jié)點共享，任意節(jié)點可以直接訪問任意內存模塊；,節(jié)點訪問內存模塊的速度不同，訪問本地存儲模塊的速度一般是訪問其他節(jié)點內存模塊的3倍以上；,發(fā)生訪存競爭時，仲裁策略對節(jié)點可能是不等價的；,各節(jié)點的CPU可帶有局部私有高速緩存（cache）；,外圍I/O設備也可以共享，但對各節(jié)點是不等價的。,訪存模型NUMA（Non-Uniform Memory Ac,7,訪存模型,COMA（Cache-Only Memory Access）模型：全高速緩存存儲訪問模型,各處理器節(jié)點中沒有存儲層次結構，全部高速緩存組成了全局地址空間；,利用分布的高速緩存目錄進行遠程高速緩存的訪問；,COMA中的高速緩存容量一般都大于2級高速緩存容量；,使用COMA時，數據開始時可以任意分配，因為在運行時它最終會被遷移到要用到它的地方。,訪存模型COMA（Cache-Only Memory Acc,8,并行計算模型,SIMD同步并行計算模型,共享存儲的SIMD模型（PRAM模型）；,分布存儲的SIMD模型（SIMD互聯(lián)網絡模型）,MIMD異步并行計算模型,異步PRAM模型,BSP模型,LogP模型,C3,模型,并行計算模型 SIMD同步并行計算模型,9,同步并行計算模型,SIMD共享存儲模型假定存在著一個容量無限大的共享存儲器，有有限或無限個功能相同的處理器，且均具有簡單的算術運算和邏輯判斷功能，在任何時刻各處理器均可通過共享存儲單元相互交換數據。,SIMD共享存儲模型（PRAM模型）,PRAM-EREW（Exclusive-Read and Exclusive-Write），不允許同時讀和同時寫；,PRAM-CREW（Concurrent-Read and Exclusive-Write），允許同時讀但不允許同時寫；,PRAM-CRCW（Concurrent-Read and Concurrent-Write），允許同時讀和同時寫。,優(yōu)點：,適合于并行算法的表達、分析和比較；,使用簡單，很多諸如處理器間通信、存儲管理和進程同步等并行計算機的低級細節(jié)均隱含于模型中；,易于設計算法和稍加修改便可運行在不同的并行計算機上；,且有可能加入一些諸如同步和通信等需要考慮的方面。,同步并行計算模型SIMD共享存儲模型假定存在著一個容量無限大,10,同步并行計算模型,SIMD分布存儲模型,采用一維線性連接的SIMD模型，簡記為SIMD-LC,采用網孔連接的SIMD模型，簡記為SIMD-MC,采用樹形連接的SIMD模型，簡記為SIMD-TC,采用樹網連接的SIMD模型，簡記為SIMD-MT,采用立方連接的SIMD模型，簡記為SIMD-CC,采用立方環(huán)連接的SIMD模型，簡記為SIMD-CCC,采用洗牌交換連接的SIMD模型，簡記為SIMD-SE,采用蝶形連接的SIMD模型，簡介為SIMD-BF,采用多級互聯(lián)網絡連接的SIMD模型，簡記為SIMD-MIN,同步并行計算模型SIMD分布存儲模型,11,MIMD異步計算模型APRAM模型,APRAM特點:,每個處理器都有其本地存儲器、局部時鐘和局部程序,處理器間的通信經過共享全局存儲器,無全局時鐘，各處理器異步地獨立執(zhí)行各自的指令,處理器任何時間依賴關系需明確地在各處理器的程序中加入同步障（Synchronization Barrier）,一條指令可在非確定但有限的時間內完成。,MIMD異步計算模型APRAM模型APRAM特點:,12,MIMD異步計算模型PRAM模型,APRAM模型中有四類指令:,全局讀，將全局存儲單元中的內容讀入本地存儲器單元中,局部操作，對本地存儲器中的數執(zhí)行操作，其結果存入本地存儲器中,全局寫，將本地存儲器單元中的內容寫入全本地存儲器單元中,同步，同步是計算中的一個邏輯點，在該點各處理器均需等待別的處理器到達后才能繼續(xù)執(zhí)行其局部程序,MIMD異步計算模型PRAM模型APRAM模型中有四類指,13,MIMD異步計算模型BSP模型,大同步并行BSP（Bulk Synchronous Parallel）模型 作為計算機語言和體系結構之間的橋梁，由下述三個參數描述分布存儲的并行計算機模型：,處理器/存儲器模塊（下文簡稱處理器）；,處理器模塊之間點到點信息傳遞的路由器；,執(zhí)行以時間間隔L為周期的路障同步器。,MIMD異步計算模型BSP模型大同步并行BSP（Bulk,14,MIMD異步計算模型BSP模型,特點：,將處理器和路由器分開，強調了計算任務和通信任務的分開，而路由器僅施行點到點的消息傳遞，不提供組合、復制或廣播等功能，這樣做既掩蓋了具體的互聯(lián)網絡拓撲，又簡化了通信協(xié)議；,采用路障方式的以硬件實現(xiàn)的全局同步是在可控的粗粒度級，從而提供了執(zhí)行緊耦合同步式并行算法的有效方式，而程序員并無過分的負擔；,在分析BSP模型的性能時，假定局部操作可在一個時間步內完成，而在每一超級步中，一個處理器至多發(fā)送或接受h條消息（h-relation）,MIMD異步計算模型BSP模型特點：,15,MIMD異步計算模型LogP,C3模型,LogP模型,一種分布存儲的、點到點通信的多處理機模型，其中通信網絡由一組參數來描述，但它并不涉及到具體的網絡結構，也不假定算法一定要用顯式的消息傳遞操作進行描述。,C3,（Computation,Communication,Congestion）,是一個與體系結構無關的粗粒度的并行計算模型，旨在能反映計算復雜度，通信模式和通信期間潛在的擁擠等因素對粗粒度網絡算法的影響。,MIMD異步計算模型LogP,C3模型LogP模型,16,并行編程環(huán)境,比較流行的并行編程環(huán)境主要有3類：消息傳遞、共享存儲和數據并行，,共享存儲并行編程基于線程級細粒度并行，可移植性不如消息傳遞并行編程，但是，由于他們支持數據的共享存儲，所以并行編程的難度較小，但一般情況下，當處理機個數較多時，其并行性能明顯不如消息傳遞編程；,消息傳遞并行編程基于大粒度的進程級并行，具有最好的可擴展性，幾乎被所有當前流行的各類并行計算機所支持，其具有較好的可擴展性，但是，消息傳遞并行編程只能支持進程間的分布式存儲模式，即各個進程只能支持訪問其局部內存空間，而對其他進程的局部內存空間的訪問只能通過消息傳遞來實現(xiàn)，因此，學習和使用消息傳遞并行編程的難度均大于共享存儲和數據并行這兩種編程模式。,并行編程環(huán)境比較流行的并行編程環(huán)境主要有3類：消息傳遞、共享,17,并行編程環(huán)境,3類并行編程環(huán)境的主要特征的比較總結,特征,消息傳遞,共享存儲,數據并行,典型代表,MPI,PVM,OpenMP,HPF,可移植性,所有主流并行計算機,SMP,DSM,SMP,DSM,MPP,并行粒度,進程級大粒度,線程級細粒度,進程級細粒度,并行操作方式,異步,異步,松散同步,數據存儲模式,分布式存儲,共享存儲,共享存儲,數據分配方式,顯式,隱式,半隱式,學習入門難度,較難,容易,偏易,可擴展性,好,較差,一般,并行編程環(huán)境3類并行編程環(huán)境的主要特征的比較總結 特征消息傳,18,并行計算性能評測,加速比（Speedup）：用,最優(yōu)串行算法的執(zhí)行時間,除以,并行程序的執(zhí)行時間,所得到的比值，能夠準確描述對程序并行化之后所獲得的性能收益。,最優(yōu)串行算法的執(zhí)行時間除以并行程序的執(zhí)行時間所得到的比值,：,并行加速比就是指對于一個給定的應用，并行算法的執(zhí)行速度相對于串行算法的執(zhí)行速度加快了多少倍。,并行計算性能評測加速比（Speedup）：用最優(yōu)串行算法的執(zhí),19,并行計算性能評測,并行程序執(zhí)行時間,等于從并行程序開始執(zhí)行到所有進程執(zhí)行完畢，墻上時鐘走過的時間，也稱為墻上時間（wall clock time）。對各個進程，墻上時間可進一步分解為計算CPU時間、通信CPU時間、同步開銷時間、同步導致的進程空閑時間；,計算CPU時間：進程指令執(zhí)行所花費的CPU時間，包括程序本身的指令執(zhí)行占用的時間和系統(tǒng)指令花費的時間；,通信CPU時間；,同步開銷時間；,進程空閑時間：當一個進程阻塞式等待其他進程的消息時，CPU通常是空閑的，或者處于等待狀態(tài)。進程空閑時間是指并行程序執(zhí)行過程中，進程所有空閑時間總和。,并行計算性能評測并行程序執(zhí)行時間,20,并行計算性能評測,加速比性能定律Amdahl定律,能夠計算并行程序相對于最優(yōu)串行算法在性能提升上的理論最大值表述是一種直觀、清楚的表述，他將程序劃分為可加速與不可加速兩大部分，程序總的加速比是一個關于程序中這兩部分所占比例以及可加速部分性能加速程度的函數,如果只對50%的程序加速15%的話，整個程序總的加速比就是：,Amdahl定律:,S 表示執(zhí)行程序中串行部分的比例，n表示處理器核的數量。假設最優(yōu)串行算法的執(zhí)行時間為一個單位時間（也就是分子為1）。,處理器核在數量上能夠無限制的增加，但是無限的處理器核卻并不能帶來性能上的無限增長，無論如何，程序性能上的總是有個上限，這個要受限于串行部分所占的比例。,并行計算性能評測加速比性能定律Amdahl定律,21,程序性能優(yōu)化,串行程序性能優(yōu)化,是并行程序性能優(yōu)化的基礎，一個好的并行程序首先應該擁有良好的單機性能，影響程序單機性能的主要因素是程序的計算流程和處理器的體系結構,調用高性能庫：充分利用已有的高性能程序庫是提高應用程序實際性能最有效的途徑之一。許多著名的高性能數學程序庫，如BLAS和FFTW；,選擇適當的編譯器優(yōu)化選項：現(xiàn)代編譯器在編譯時能夠對程序進行優(yōu)化，從而提高所生成的目標代碼的性能。這些優(yōu)化功能通常是通過一組編譯選項來控制；,合理定義數組維數：現(xiàn)代計算機為了提高內存帶寬，多采用多體交叉并行存儲系統(tǒng)，即使用多個獨立的內存體，對他們統(tǒng)一編址。為了充分利用多體存儲，在進行連續(xù)數據訪問時應該使地址的增量與內存體數的最大公約數盡量的小，特別要避免地址增量正好是體數的倍數的情況，因為此時所有的訪問將集中在一個存儲體中；,程序性能優(yōu)化 串行程序性能優(yōu)化是并行程序性能優(yōu)化的基礎，,22,程序性能優(yōu)化,串行程序性能優(yōu)化,注意嵌套循環(huán)的順序：提高cache使用效率的一個簡單原則就是盡量改善數據訪問的局部性，數據訪問的局部性包括空間局部性和時間局部性，空間局部性指的是訪問了一個地址后，會緊接著訪問他的鄰居地址。在嵌套的多循環(huán)語句中，循環(huán)順序往往對循環(huán)中數據訪問的局部性有很大的影響。在編寫嵌套的多循環(huán)代碼時，一個通用的原則就是盡量使最內層循環(huán)的數據訪問連續(xù)進行；,數據分塊和循環(huán)展開和一些其他方法，例如使用一些優(yōu)化工具如 Intel VTune等。,程序性能優(yōu)化串行程序性能優(yōu)化,23,程序性能優(yōu)化,并行程序性能優(yōu)化并行程序的性能優(yōu)化相對于串行程序而言就有些復雜了，最主要的是選擇好的并行算法和通信模式，下面介紹一下常用的并行程序優(yōu)化技術,減少通信量、提高通信粒度：主要有三個途徑：較少通信量、提高通信粒度和提高通信中的并發(fā)度。提高通信粒度的有效方法就是減少通信次數，盡可能將可以一次傳遞的數據合并起來一起傳遞；,全局通信盡量利用高效集合通信算法：當組織多個進程之間的集合通信時，使用高效的通信算法可以大大地提高通信效率，從而降低通信開銷；,挖掘算法的并行度，減少CPU空閑等待：些具有數據相關性的計算過程會導致并行運行的部分進程空閑等待。在這種情況下，可以考慮改變算法來消除數據相關性；,程序性能優(yōu)化并行程序性能優(yōu)化并行程序的性能優(yōu)化相對于串行,24,程序性能優(yōu)化,并行程序性能優(yōu)化,負載平衡：是導致進程空閑等待的另外一個重要因素。在設計并行程序時應該充分考慮負載平衡問題，動態(tài)調整負載時要考慮負載調整的開銷及由于負載不平衡而引起的空閑等待對性能的影響，尋找最優(yōu)負載調整方案；,通信、計算的重疊：通常讓通信和計算重疊進行，利用計算時間來屏蔽通信時間，是減少通信開銷得非常有效的方法。實現(xiàn)通信與計算重疊的方法一般基于非阻塞通信，先發(fā)出非阻塞的消息接受或發(fā)送命令，然后處理與收發(fā)數據無關的計算任務，完成這些計算后再等待消息收發(fā)的完成；,通過引入重復計算來減少通信，即以計算換通信：適當引入一些重復計算，可以減少通信量和通信次數。由于當前大部分并行計算機的計算速度遠遠大于通信速度，并且在一些情況下，當一個進程計算時，別的進程往往處于空閑等待狀態(tài)，因而適當引入重復計算可以提高程序的總體性能。,程序性能優(yōu)化并行程序性能優(yōu)化,25,第二章并行程序設計基礎（并行計算基礎）課件,26,第二章并行程序設計基礎（并行計算基礎）課件,27,