中國(guó)科技大學(xué)并行計(jì)算課件4并行算法的設(shè)計(jì)基礎(chǔ)

1、并 行 計(jì) 算 中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系國(guó)家高性能計(jì)算中心(合肥)2004年12月第二篇 并行算法的設(shè)計(jì) 第四章 并行算法的設(shè)計(jì)基礎(chǔ) 第五章 并行算法的一般設(shè)計(jì)方法 第六章 并行算法的基本設(shè)計(jì)技術(shù) 第七章 并行算法的一般設(shè)計(jì)過(guò)程第四章 并行算法的設(shè)計(jì)基礎(chǔ) 4.1 并行算法的基礎(chǔ)知識(shí) 4.2 并行計(jì)算模型4.1 并行算法的基礎(chǔ)知識(shí) 4.1.1 并行算法的定義和分類 4.1.2 并行算法的表達(dá) 4.1.3 并行算法的復(fù)雜性度量 4.1.4 并行算法中的同步和通訊國(guó)家高性能計(jì)算中心（合肥）52022/9/11 并行算法的定義和分類并行算法的定義算法并行算法：一些可同時(shí)執(zhí)行的諸進(jìn)程的集合，這

2、些進(jìn)程互相作用和協(xié)調(diào)動(dòng)作從而達(dá)到給定問(wèn)題的求解。并行算法的分類數(shù)值計(jì)算和非數(shù)值計(jì)算同步算法和異步算法分布算法確定算法和隨機(jī)算法4.1 并行算法的基礎(chǔ)知識(shí) 4.1.1 并行算法的定義和分類 4.1.2 并行算法的表達(dá) 4.1.3 并行算法的復(fù)雜性度量 4.1.4 并行算法中的同步和通訊國(guó)家高性能計(jì)算中心（合肥）72022/9/11 并行算法的表達(dá)描述語(yǔ)言可以使用類Algol、類Pascal等；在描述語(yǔ)言中引入并行語(yǔ)句。并行語(yǔ)句示例Par-do語(yǔ)句 for i=1 to n par-do end forfor all語(yǔ)句 for all Pi, where 0ik end for 4.1 并行算法

3、的基礎(chǔ)知識(shí) 4.1.1 并行算法的定義和分類 4.1.2 并行算法的表達(dá) 4.1.3 并行算法的復(fù)雜性度量 4.1.4 并行算法中的同步和通訊國(guó)家高性能計(jì)算中心（合肥）92022/9/11 并行算法的復(fù)雜性度量串行算法的復(fù)雜性度量最壞情況下的復(fù)雜度(Worst-CASE Complexity)期望復(fù)雜度(Expected Complexity)并行算法的幾個(gè)復(fù)雜性度量指標(biāo)運(yùn)行時(shí)間t(n):包含計(jì)算時(shí)間和通訊時(shí)間，分別用計(jì)算時(shí)間步和選路時(shí)間步作單位。n為問(wèn)題實(shí)例的輸入規(guī)模。處理器數(shù)p(n)并行算法成本c(n): c(n)=t(n)p(n)總運(yùn)算量W(n): 并行算法求解問(wèn)題時(shí)所完成的總的操作步數(shù)

4、。 國(guó)家高性能計(jì)算中心（合肥）102022/9/11 并行算法的復(fù)雜性度量Brent定理令W(n)是某并行算法A在運(yùn)行時(shí)間T(n)內(nèi)所執(zhí)行的運(yùn)算量，則A使用p臺(tái)處理器可在t(n)=O(W(n)/p+T(n)時(shí)間內(nèi)執(zhí)行完畢。W(n)和c(n)密切相關(guān)P=O(W(n)/T(n)時(shí)，W(n)和c(n)兩者是漸進(jìn)一致的對(duì)于任意的p，c(n)W(n)4.1 并行算法的基礎(chǔ)知識(shí) 4.1.1 并行算法的定義和分類 4.1.2 并行算法的表達(dá) 4.1.3 并行算法的復(fù)雜性度量 4.1.4 并行算法中的同步和通訊國(guó)家高性能計(jì)算中心（合肥）122022/9/11 并行算法的同步同步概念同步是在時(shí)間上強(qiáng)使各執(zhí)行進(jìn)程

5、在某一點(diǎn)必須互相等待；可用軟件、硬件和固件的辦法來(lái)實(shí)現(xiàn)。同步語(yǔ)句示例算法4.1 共享存儲(chǔ)多處理器上求和算法 輸入：A=(a0,an-1),處理器數(shù)p 輸出：S=ai Begin (1)S=0 (2.3) lock(S) (2)for all Pi where 0ip-1 do S=S+L (2.1) L=0 (2.4) unlock(S) (2.2) for j=i to n step p do end for L=L+aj End end for end for 國(guó)家高性能計(jì)算中心（合肥）132022/9/11 并行算法的通訊通訊共享存儲(chǔ)多處理器使用：global read(X,Y)和glo

6、bal write(X,Y)分布存儲(chǔ)多計(jì)算機(jī)使用：send(X,i)和receive(Y,j)通訊語(yǔ)句示例算法4.2 分布存儲(chǔ)多計(jì)算機(jī)上矩陣向量乘算法 輸入：處理器數(shù)p, A劃分為B=A1.n,(i-1)r+1.ir, x劃分為w=w(i-1)r+1;ir 輸出：P1保存乘積AX Begin (1) Compute z=Bw (2) if i=1 then yi=0 else receive(y,left) endif (3) y=y+z (4) send(y,right) (5) if i=1 then receive(y,left) End 第四章 并行算法的設(shè)計(jì)基礎(chǔ) 4.1 并行算法的基

7、礎(chǔ)知識(shí) 4.2 并行計(jì)算模型4.2 并行計(jì)算模型 4.2.1 PRAM模型 4.2.2 異步APRAM模型 4.2.3 BSP模型 4.2.4 logP模型國(guó)家高性能計(jì)算中心（合肥）162022/9/11 PRAM模型基本概念由Fortune和Wyllie1978年提出，又稱SIMD-SM模型。有一個(gè)集中的共享存儲(chǔ)器和一個(gè)指令控制器，通過(guò)SM的R/W交換數(shù)據(jù)，隱式同步計(jì)算。結(jié)構(gòu)圖Control UnitInterconnection NetworkPLMPLMPLMPLMShared Memory國(guó)家高性能計(jì)算中心（合肥）172022/9/11 PRAM模型分類PRAM-CRCW并發(fā)讀并發(fā)寫C

8、PRAM-CRCW(Common PRAM-CRCW)：僅允許寫入相同數(shù)據(jù)PPRAM-CRCW(Priority PRAM-CRCW)：僅允許優(yōu)先級(jí)最高的處理器寫入APRAM-CRCW(Arbitrary PRAM-CRCW)：允許任意處理器自由寫入 PRAM-CREW并發(fā)讀互斥寫 PRAM-EREW互斥讀互斥寫 計(jì)算能力比較PRAM-CRCW是最強(qiáng)的計(jì)算模型，PRAM-EREW可logp倍模擬PRAM-CREW和PRAM-CRCW 國(guó)家高性能計(jì)算中心（合肥）182022/9/11 PRAM模型優(yōu)點(diǎn)適合并行算法表示和復(fù)雜性分析，易于使用，隱藏了并行機(jī)的通訊、同步等細(xì)節(jié)。缺點(diǎn)不適合MIMD并行機(jī)

9、，忽略了SM的競(jìng)爭(zhēng)、通訊延遲等因素4.2 并行計(jì)算模型 4.2.1 PRAM模型 4.2.2 異步APRAM模型 4.2.3 BSP模型 4.2.4 logP模型國(guó)家高性能計(jì)算中心（合肥）202022/9/11 異步APRAM模型基本概念又稱分相（Phase）PRAM或MIMD-SM。每個(gè)處理器有其局部存儲(chǔ)器、局部時(shí)鐘、局部程序；無(wú)全局時(shí)鐘，各處理器異步執(zhí)行；處理器通過(guò)SM進(jìn)行通訊；處理器間依賴關(guān)系，需在并行程序中顯式地加入同步路障。指令類型(1)全局讀 (2)全局寫 (3)局部操作 (4)同步 國(guó)家高性能計(jì)算中心（合肥）212022/9/11 異步APRAM模型計(jì)算過(guò)程由同步障分開(kāi)的全局相組

10、成 國(guó)家高性能計(jì)算中心（合肥）222022/9/11 異步APRAM模型計(jì)算時(shí)間 設(shè)局部操作為單位時(shí)間；全局讀/寫平均時(shí)間為d，d隨著處理器數(shù)目的增加而增加；同步路障時(shí)間為B=B(p)非降函數(shù)。 滿足關(guān)系 ； 或 令 為全局相內(nèi)各處理器執(zhí)行時(shí)間最長(zhǎng)者，則APRAM上的計(jì)算時(shí)間為 優(yōu)缺點(diǎn) 易編程和分析算法的復(fù)雜度，但與現(xiàn)實(shí)相差較遠(yuǎn)，其上并行算法非常有限，也不適合MIMD-DM模型。 4.2 并行計(jì)算模型 4.2.1 PRAM模型 4.2.2 異步APRAM模型 4.2.3 BSP模型 4.2.4 logP模型國(guó)家高性能計(jì)算中心（合肥）242022/9/11 BSP模型基本概念由Valiant(1

11、990)提出的，“塊”同步模型，是一種異步MIMD-DM模型，支持消息傳遞系統(tǒng)，塊內(nèi)異步并行，塊間顯式同步。 模型參數(shù)p：處理器數(shù)(帶有存儲(chǔ)器)l：同步障時(shí)間(Barrier synchronization time)g：帶寬因子(time steps/packet)=1/bandwidth 國(guó)家高性能計(jì)算中心（合肥）252022/9/11 BSP模型計(jì)算過(guò)程由若干超級(jí)步組成，每個(gè)超級(jí)步計(jì)算模式為左圖優(yōu)缺點(diǎn) 強(qiáng)調(diào)了計(jì)算和通訊的分離， 提供了一個(gè)編程環(huán)境，易于 程序復(fù)雜性分析。但需要顯 式同步機(jī)制，限制至多h條 消息的傳遞等。4.2 并行計(jì)算模型 4.2.1 PRAM模型 4.2.2 異步APRAM模型 4.2.3 BSP模型 4.2.4 logP模型國(guó)家高性能計(jì)算中心（合肥）272022/9/11 logP模型基本概念由Culler(1993)年提出的，是一種分布存儲(chǔ)的、點(diǎn)到點(diǎn)通訊的多處理機(jī)模型，其中通訊由一組參數(shù)描述，實(shí)行隱式同步。模型參數(shù)L：network latencyo：communication overheadg：gap=1/bandwidthP：#processors注：L和g反映了通訊網(wǎng)絡(luò)的容量 國(guó)家高性能計(jì)算中心（合肥）282022/9/11 logP模型優(yōu)缺點(diǎn) 捕捉了MPC的通訊瓶頸，隱藏了并行機(jī)的網(wǎng)絡(luò)拓?fù)?、路由、協(xié)議，可以應(yīng)