,單擊此處編輯母版標(biāo)題樣式,*,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第二章 并行計(jì)算基礎(chǔ),并行計(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ì)算：,1,并行計(jì)算的應(yīng)用,預(yù)測(cè)模型的構(gòu)造和模擬、工程設(shè)計(jì)和自動(dòng)化、能源勘探、醫(yī)學(xué)、軍事以及基礎(chǔ)理論研究等領(lǐng)域中都對(duì)計(jì)算提出了極高的要求。,并行計(jì)算三種主要的基本類型：,計(jì)算密集型應(yīng)用，如大型科學(xué)工程計(jì)算與數(shù)值模擬；,數(shù)據(jù)密集型應(yīng)用，如數(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ā)方法,并行層次與代碼粒度,指令級(jí)并行：在多個(gè)并行層次中指令級(jí)并行是代碼粒度最小的并行，也稱為微粒度并行、甚細(xì)粒度并行；,數(shù)據(jù)級(jí)并行：又稱為細(xì)粒度并行，它比指令級(jí)并行所執(zhí)行的代碼粒度要大一些，一般長(zhǎng)度為幾百條指令，這類并行通常都是在編譯階段由編譯器來(lái)負(fù)責(zé)實(shí)現(xiàn)的；,控制級(jí)并行：也叫中粒度并行，通常是面對(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ā)方法,并行程序的開(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ǔ)言重新編寫能運(yùn)行于高性能并行計(jì)算機(jī)上的并行代碼。,并行程序開(kāi)發(fā)方法并行程序的開(kāi)發(fā)策略,4,并行程序設(shè)計(jì)模式,并行程序設(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ì)模式,并行程序設(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)題的解；,流水線模式：將一個(gè)計(jì)算過(guò)程分解成流水線式的多個(gè)步驟序列，對(duì)于每個(gè)步驟的處理使用一個(gè)或多個(gè)線程來(lái)實(shí)現(xiàn)；,并行程序設(shè)計(jì)模式并行程序設(shè)計(jì)模式,6,并行程序設(shè)計(jì)模式,并行程序設(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)生的。運(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ǔ),組成并行計(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)存模塊位于節(jié)點(diǎn)內(nèi)部,9,多級(jí)存儲(chǔ)體系結(jié)構(gòu),解決內(nèi)存墻（,memory wall,）性能瓶頸問(wèn)題；,節(jié)點(diǎn)內(nèi)部的,cache,稱為二級(jí),cache,（,L2 cache,）；,處理器內(nèi)部更小的,cache,成為一級(jí),cache,（,L1 cache,）；,L1 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),并行計(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)模式,。,cache,原理，,cache,以,cache,線為基本單位，每條,cache,包含,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,如果操作數(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),cache,的映射策略（,內(nèi)存塊和,cache,線之間如何建立相互映射關(guān)系,）,：,直接映射策略（,direct mapping strategy,）：每個(gè)內(nèi)存塊只能被唯一的映射到一條,cache,線中,；,K,路組關(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,訪存模型,UMA,（,Uniform Memory Access,）模型：該模型內(nèi)存模塊與節(jié)點(diǎn)分離，分別位于互聯(lián)網(wǎng)絡(luò)的兩側(cè),物理存儲(chǔ)器被所有節(jié)點(diǎn)共享；,所有節(jié)點(diǎn)訪問(wèn)任意存儲(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,訪存模型,NUMA（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ǔ)模塊的速度一般是訪問(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 Ac,14,訪存模型,COMA（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ì)被遷移到要用到它的地方。,訪存模型COMA（Cache-Only Memory Acc,15,并行計(jì)算模型,SIMD同步并行計(jì)算模型,共享存儲(chǔ)的,SIMD,模型（,PRAM,模型）；,分布存儲(chǔ)的,SIMD,模型（,SIMD,互聯(lián)網(wǎng)絡(luò)模型）,MIMD異步并行計(jì)算模型,異步,PRAM,模型,BSP,模型,LogP,模型,C,3,模型,并行計(jì)算模型 SIMD同步并行計(jì)算模型,16,同步并行計(jì)算模型,SIMD,共享存儲(chǔ)模型假定存在著一個(gè)容量無(wú)限大的共享存儲(chǔ)器，有有限或無(wú)限個(gè)功能相同的處理器，且均具有簡(jiǎn)單的算術(shù)運(yùn)算和邏輯判斷功能，在任何時(shí)刻各處理器均可通過(guò)共享存儲(chǔ)單元相互交換數(shù)據(jù)。,SIMD共享存儲(chǔ)模型（PRAM模型）,PRAM-EREW,（,Exclusive-Read and Exclusive-Write,），不允許同時(shí)讀和同時(shí)寫；,PRAM-CREW,（,Concurrent-Read and Exclusive-Write,），允許同時(shí)讀但不允許同時(shí)寫；,PRAM-CRCW,（,Concurrent-Read and Concurrent-Write,），允許同時(shí)讀和同時(shí)寫。,優(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ì)算模型,SIMD分布存儲(chǔ)模型,采用一維線性連接的,SIMD,模型，簡(jiǎn)記為,SIMD-LC,采用網(wǎng)孔連接的,SIMD,模型，簡(jiǎn)記為,SIMD-MC,采用樹形連接的,SIMD,模型，簡(jiǎn)記為,SIMD-TC,采用樹網(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ǔ)模型,18,MIMD,異步計(jì)算模型,A,PRAM,模型,APRAM特點(diǎn):,每個(gè)處理器都有其本地存儲(chǔ)器、局部時(shí)鐘和局部程序,處理器間的通信經(jīng)過(guò)共享全局存儲(chǔ)器,無(wú)全局時(shí)鐘，各處理器異步地獨(dú)立執(zhí)行各自的指令,處理器任何時(shí)間依賴關(guān)系需明確地在各處理器的程序中加入同步障（,Synchronization Barrier,）,一條指令可在非確定但有限的時(shí)間內(nèi)完成。,MIMD異步計(jì)算模型APRAM模型APRAM特點(diǎn):,19,MIMD,異步計(jì)算模型,PRAM,模型,APRAM,模型中有四類指令,:,全局讀，將全局存儲(chǔ)單元中的內(nèi)容讀入本地存儲(chǔ)器單元中,局部操作，對(duì)本地存儲(chǔ)器中的數(shù)執(zhí)行操作，其結(jié)果存入本地存儲(chǔ)器中,全局寫，將本地存儲(chǔ)器單元中的內(nèi)容寫入全本地存儲(chǔ)器單元中,同步，同步是計(jì)算中的一個(gè)邏輯點(diǎn)，在該點(diǎn)各處理器均需等待別的處理器到達(dá)后才能繼續(xù)執(zhí)行其局部程序,MIMD異步計(jì)算模型PRAM模型APRAM模型中有四類指,20,MIMD異步計(jì)算模型BSP模型,大同步并行,BSP,（,Bulk Synchronous Parallel,）,模型,作為計(jì)算機(jī)語(yǔ)言和體系結(jié)構(gòu)之間的橋梁，由下述三個(gè)參數(shù)描述分布存儲(chǔ)的并行計(jì)算機(jī)模型：,處理器,/,存儲(chǔ)器模塊（下文簡(jiǎn)稱處理器）；,處