并行算法的設(shè)計(jì)基礎(chǔ)

并行計(jì)算

2023/2/61第二篇并行算法的設(shè)計(jì)

第四章并行算法的設(shè)計(jì)基礎(chǔ)

第五章并行算法的一般設(shè)計(jì)方法

第六章并行算法的基本設(shè)計(jì)技術(shù)

第七章并行算法的一般設(shè)計(jì)過程

2023/2/62第四章并行算法的設(shè)計(jì)基礎(chǔ)

4.1并行算法的基礎(chǔ)知識

4.2并行計(jì)算模型

2023/2/634.1并行算法的基礎(chǔ)知識

4.1.1

并行算法的定義和分類

4.1.2

并行算法的表達(dá)

4.1.3

并行算法的復(fù)雜性度量

4.1.4

并行算法中的同步和通訊2023/2/64并行算法的定義和分類并行算法的定義算法并行算法：一些可同時執(zhí)行的諸進(jìn)程的集合，這些進(jìn)程互相作用和協(xié)調(diào)動作從而達(dá)到給定問題的求解。并行算法的分類數(shù)值計(jì)算和非數(shù)值計(jì)算同步算法和異步算法分布算法確定算法和隨機(jī)算法2023/2/654.1并行算法的基礎(chǔ)知識

4.1.1

并行算法的定義和分類

4.1.2

并行算法的表達(dá)

4.1.3

并行算法的復(fù)雜性度量

4.1.4

并行算法中的同步和通訊2023/2/66并行算法的表達(dá)描述語言可以使用類Algol、類Pascal等；在描述語言中引入并行語句。并行語句示例Par-do語句

fori=1tonpar-do……endforforall語句

forallPi,where0≤i≤k……endfor2023/2/674.1并行算法的基礎(chǔ)知識

4.1.1

并行算法的定義和分類

4.1.2

并行算法的表達(dá)

4.1.3

并行算法的復(fù)雜性度量

4.1.4

并行算法中的同步和通訊2023/2/68并行算法的復(fù)雜性度量串行算法的復(fù)雜性度量最壞情況下的復(fù)雜度(Worst-CASEComplexity)期望復(fù)雜度(ExpectedComplexity)并行算法的幾個復(fù)雜性度量指標(biāo)運(yùn)行時間t(n):包含計(jì)算時間和通訊時間，分別用計(jì)算時間步和選路時間步作單位。n為問題實(shí)例的輸入規(guī)模。處理器數(shù)p(n)并行算法成本c(n):c(n)=t(n)p(n)總運(yùn)算量W(n):并行算法求解問題時所完成的總的操作步數(shù)。

2023/2/69并行算法的復(fù)雜性度量Brent定理令W(n)是某并行算法A在運(yùn)行時間T(n)內(nèi)所執(zhí)行的運(yùn)算量，則A使用p臺處理器可在t(n)=O(W(n)/p+T(n))時間內(nèi)執(zhí)行完畢。W(n)和c(n)密切相關(guān)P=O(W(n)/T(n))時，W(n)和c(n)兩者是漸進(jìn)一致的對于任意的p，c(n)?W(n)2023/2/6104.1并行算法的基礎(chǔ)知識

4.1.1

并行算法的定義和分類

4.1.2

并行算法的表達(dá)

4.1.3

并行算法的復(fù)雜性度量

4.1.4

并行算法中的同步和通訊2023/2/611并行算法的同步同步概念同步是在時間上強(qiáng)使各執(zhí)行進(jìn)程在某一點(diǎn)必須互相等待；可用軟件、硬件和固件的辦法來實(shí)現(xiàn)。同步語句示例算法4.1共享存儲多處理器上求和算法輸入：A=(a0,…,an-1),處理器數(shù)p

輸出：S=ΣaiBegin(1)S=0(2.3)lock(S)(2)forallPiwhere0≤i≤p-1

doS=S+L(2.1)L=0(2.4)unlock(S)(2.2)forj=itonsteppdoendforL=L+ajEndendforendfor2023/2/612并行算法的通訊通訊共享存儲多處理器使用：globalread(X,Y)和globalwrite(X,Y)分布存儲多計(jì)算機(jī)使用：send(X,i)和receive(Y,j)通訊語句示例算法4.2分布存儲多計(jì)算機(jī)上矩陣向量乘算法輸入：處理器數(shù)p,A劃分為B=A[1..n,(i-1)r+1..ir],x劃分為w=w[(i-1)r+1;ir]

輸出：P1保存乘積AXBegin(1)Computez=Bw(2)ifi=1thenyi=0elsereceive(y,left)endif(3)y=y+z(4)send(y,right)(5)ifi=1thenreceive(y,left)End2023/2/613第四章并行算法的設(shè)計(jì)基礎(chǔ)

4.1并行算法的基礎(chǔ)知識

4.2并行計(jì)算模型

2023/2/6144.2并行計(jì)算模型

4.2.1

PRAM模型

4.2.2

異步APRAM模型

4.2.3BSP模型

4.2.4

logP模型2023/2/615

PRAM模型基本概念由Fortune和Wyllie1978年提出，又稱SIMD-SM模型。有一個集中的共享存儲器和一個指令控制器，通過SM的R/W交換數(shù)據(jù)，隱式同步計(jì)算。結(jié)構(gòu)圖ControlUnitInterconnectionNetworkPLMPLMPLMPLMSharedMemory2023/2/616

PRAM模型分類PRAM-CRCW并發(fā)讀并發(fā)寫CPRAM-CRCW(CommonPRAM-CRCW)：僅允許寫入相同數(shù)據(jù)PPRAM-CRCW(PriorityPRAM-CRCW)：僅允許優(yōu)先級最高的處理器寫入APRAM-CRCW(ArbitraryPRAM-CRCW)：允許任意處理器自由寫入PRAM-CREW并發(fā)讀互斥寫PRAM-EREW互斥讀互斥寫計(jì)算能力比較PRAM-CRCW是最強(qiáng)的計(jì)算模型，PRAM-EREW可logp倍模擬PRAM-CREW和PRAM-CRCW2023/2/617

PRAM模型優(yōu)點(diǎn)適合并行算法表示和復(fù)雜性分析，易于使用，隱藏了并行機(jī)的通訊、同步等細(xì)節(jié)。缺點(diǎn)不適合MIMD并行機(jī)，忽略了SM的競爭、通訊延遲等因素2023/2/6184.2并行計(jì)算模型

4.2.1PRAM模型

4.2.2

異步APRAM模型

4.2.3BSP模型

4.2.4

logP模型2023/2/619異步APRAM模型基本概念又稱分相（Phase）PRAM或MIMD-SM。每個處理器有其局部存儲器、局部時鐘、局部程序；無全局時鐘，各處理器異步執(zhí)行；處理器通過SM進(jìn)行通訊；處理器間依賴關(guān)系，需在并行程序中顯式地加入同步路障。指令類型(1)全局讀(2)全局寫(3)局部操作(4)同步2023/2/620異步APRAM模型計(jì)算過程由同步障分開的全局相組成

2023/2/621異步APRAM模型計(jì)算時間

設(shè)局部操作為單位時間；全局讀/寫平均時間為d，d隨著處理器數(shù)目的增加而增加；同步路障時間為B=B(p)非降函數(shù)。滿足關(guān)系；或令為全局相內(nèi)各處理器執(zhí)行時間最長者，則APRAM上的計(jì)算時間為優(yōu)缺點(diǎn)

易編程和分析算法的復(fù)雜度，但與現(xiàn)實(shí)相差較遠(yuǎn)，其上并行算法非常有限，也不適合MIMD-DM模型。

2023/2/6224.2并行計(jì)算模型

4.2.1PRAM模型

4.2.2

異步APRAM模型

4.2.3

BSP模型

4.2.4

logP模型2023/2/623

BSP模型基本概念由Valiant(1990)提出的，“塊”同步模型，是一種異步MIMD-DM模型，支持消息傳遞系統(tǒng)，塊內(nèi)異步并行，塊間顯式同步。

模型參數(shù)p：處理器數(shù)(帶有存儲器)l：同步障時間(Barriersynchronizationtime)g：帶寬因子(timesteps/packet)=1/bandwidth2023/2/624

BSP模型計(jì)算過程由若干超級步組成，每個超級步計(jì)算模式為左圖優(yōu)缺點(diǎn)強(qiáng)調(diào)了計(jì)算和通訊的分離，提供了一個編程環(huán)境，易于程序復(fù)雜性分析。但需要顯式同步機(jī)制，限制至多h條消息的傳遞等。2023/2/6254.2并行計(jì)算模型

4.2.1PRAM模型

4.2.2

異步APRAM模型

4.2.3BSP模型

4.2.4

logP模型2023/2/626

logP模型基本概念由Culler(1993)年提出的，是一種分布存儲的、點(diǎn)到點(diǎn)通訊的多處理機(jī)模型，其中通訊由一組參數(shù)描述，實(shí)行隱式同步。模型參數(shù)L：networklatencyo：communicationoverheadg：gap=1/bandwidthP：#processors注：L和g反映了通訊網(wǎng)絡(luò)的容量

2023/2/627

logP模型優(yōu)缺點(diǎn)

捕捉了MPC的通訊瓶頸，隱藏了并行機(jī)