課件多核并行計(jì)算

第二篇并行算法的設(shè)計(jì)第四章并行算法的設(shè)計(jì)基礎(chǔ)第五章并行算法的一般設(shè)計(jì)方法第六章并行算法的基本設(shè)計(jì)技術(shù)第七章并行算法的一般設(shè)計(jì)過(guò)程第四章并行算法的設(shè)計(jì)基礎(chǔ)并行算法的基礎(chǔ)知識(shí)并行算法的定義和分類并行算法的表達(dá)并行算法的復(fù)雜性度量并行算法中的同步和通訊并行計(jì)算模型國(guó)家高性能計(jì)算中心（合肥）42021/11/4并行算法的定義和分類并行算法的定義算法：略并行算法：一些可同時(shí)執(zhí)行的諸進(jìn)程的集合，這些進(jìn)程互相作用和協(xié)調(diào)動(dòng)作從而達(dá)到給定問(wèn)題的求解。并行算法的分類數(shù)值計(jì)算和非數(shù)值計(jì)算同步算法和異步算法分布算法確定算法和隨機(jī)算法第四章并行算法的設(shè)計(jì)基礎(chǔ)并行算法的基礎(chǔ)知識(shí)并行算法的定義和分類并行算法的表達(dá)并行算法的復(fù)雜性度量并行算法中的同步和通訊并行計(jì)算模型國(guó)家高性能計(jì)算中心（合肥）62021/11/4并行算法的表達(dá)描述語(yǔ)言可以使用類Algol、類Pascal等；在描述語(yǔ)言中引入并行語(yǔ)句。并行語(yǔ)句示例Par-do語(yǔ)句for

i=1

to

n

par-do……end

forfor

all語(yǔ)句for

all

Pi,

where0≤i≤k

do……end

for第四章并行算法的設(shè)計(jì)基礎(chǔ)并行算法的基礎(chǔ)知識(shí)并行算法的定義和分類并行算法的表達(dá)并行算法的復(fù)雜性度量并行算法中的同步和通訊并行計(jì)算模型并行算法的復(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)情形下串行算法所需要的時(shí)間，則成本最優(yōu)性：若c(n)等于在并行算法是成本最優(yōu)的?？傔\(yùn)算量W(n):并行算法求解問(wèn)題時(shí)所完成的總的操作步數(shù)。2021/11/4國(guó)家高性能計(jì)算中心（合肥）8并行算法的復(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í)行完畢。注：(1)揭示了并行算法工作量和運(yùn)行時(shí)間的關(guān)系；(2)提供了并行算法的WT(Work-Time)表示方法；(3)告訴

：設(shè)計(jì)并行算法時(shí)應(yīng)盡可能將每個(gè)時(shí)間步的工作量均勻地分?jǐn)偨op臺(tái)處理器，使各處理器處于活躍狀態(tài)。2021/11/4國(guó)家高性能計(jì)算中心（合肥）9第四章并行算法的設(shè)計(jì)基礎(chǔ)并行算法的基礎(chǔ)知識(shí)并行算法的定義和分類并行算法的表達(dá)并行算法的復(fù)雜性度量并行算法中的同步和通訊并行計(jì)算模型并行算法的同步同步概念同步是在時(shí)間上強(qiáng)使各執(zhí)行進(jìn)程在某一點(diǎn)必須互相等待；可用

、硬件和固件的辦法來(lái)實(shí)現(xiàn)。同步語(yǔ)句示例算法4.1

共享

多處理器上求和算法輸入：A=(a0,…,an-1),處理器數(shù)p(2.3)

lock(S)S=S+L(2.4)

unlock(S)end

forEnd輸出：S=ΣaiBeginS=0for

all

Pi

where

0≤i≤p-1

do(2.1)

L=0(2.2)

forj=i

to

nstep

p

doL=L+ajend

for國(guó)家高性能計(jì)算中心（合肥）112021/11/4并行算法的通訊（1）通訊共享

多處理器使用：global

read(X,Y)和global

write(X,Y)分布

多計(jì)算機(jī)使用：send(X,i)和receive(Y,j)通訊語(yǔ)句示例算法4.2

分布

多計(jì)算機(jī)上矩陣向量乘算法輸入：處理器數(shù)p,

A劃分為B=A[1..n,(i-1)r+1..ir],x劃分為w=w[(i-1)r+1..ir]

r=n/p,

i=1~p輸出：P1保存乘積AXBeginCompute

z=Bwifi=1

then

yi=0

else

receive(y,left)

endify=y+zsend(y,right)ifi=1

then

receive(y,left)End2021/11/4國(guó)家高性能計(jì)算中心（合肥）13并行算法的通訊（2）計(jì)算過(guò)程圖示2021/11/4國(guó)家高性能計(jì)算中心（合肥）14第四章并行算法的設(shè)計(jì)基礎(chǔ)并行算法的基礎(chǔ)知識(shí)并行計(jì)算模型PRAM模型異步APRAM模型BSP模型logP模型PRAM模型基本概念由Fortune和Wyllie1978年提出，又稱SIMD-SM模型。有一個(gè)集中的共享

器和一個(gè)指令控制器，通過(guò)SM

的R/W交換數(shù)據(jù)，隱式同步計(jì)算。結(jié)構(gòu)圖Control

UnitInterconnection

NetworkPPPLM

LM

LMPLMShared

Memory2021/11/4國(guó)家高性能計(jì)算中心（合肥）16PRAM模型分類PRAM-CRCW并發(fā)讀并發(fā)寫CPRAM-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-CRCWTEREW

TCREW

TCRCWTEREW

O(TCREW

log

p)

O(TCRCW

log

p)TEREW

TCREW

TCRCW2021/11/4國(guó)家高性能計(jì)算中心（合肥）17PRAM模型優(yōu)點(diǎn)適合并行算法表示和復(fù)雜性分析，易于使用，隱藏了并行機(jī)的通訊、同步等細(xì)節(jié)。缺點(diǎn)不適合MIMD并行機(jī)，忽略了SM的競(jìng)爭(zhēng)、通訊延遲等因素2021/11/4國(guó)家高性能計(jì)算中心（合肥）18第四章并行算法的設(shè)計(jì)基礎(chǔ)并行算法的基礎(chǔ)知識(shí)并行計(jì)算模型PRAM模型異步APRAM模型BSP模型logP模型異步APRAM模型基本概念又稱分相（Phase）PRAM或MIMD-SM。每個(gè)處理器有其局部

器、局部時(shí)鐘、局部程序；無(wú)全局時(shí)鐘，各處理器異步執(zhí)行；處理器通過(guò)SM進(jìn)行通訊；處理器間依賴關(guān)系，需在并行程序中顯式地加入同步路障。指令類型(1)全局讀(3)局部操作(2)全局寫(4)同步2021/11/4國(guó)家高性能計(jì)算中心（合肥）20異步APRAM模型計(jì)算過(guò)程由同步障分開(kāi)的全局相組成2021/11/4國(guó)家高性能計(jì)算中心（合肥）21異步APRAM模型間為計(jì)算時(shí)間設(shè)局部操作為單位時(shí)間；全局讀/寫平均時(shí)間為d，d隨著處理器數(shù)目的增加而增加；同步路障時(shí)間為B=B(p)非降函數(shù)。滿足關(guān)系

2

d

B

p

；B

B(p)

O(d

log

p)或O(d

log

p

/log

d

)令t

ph

為全局相內(nèi)各處理器執(zhí)行時(shí)間最長(zhǎng)者，則APRAM上的計(jì)算時(shí)優(yōu)缺點(diǎn)易編程和分析算法的復(fù)雜度，但與現(xiàn)實(shí)相差較遠(yuǎn)，其上并行算法非常有限，也不適合MIMD-DM模型。2021/11/4國(guó)家高性能計(jì)算中心（合肥）22T

t

ph

B

同步障次數(shù)第四章并行算法的設(shè)計(jì)基礎(chǔ)并行算法的基礎(chǔ)知識(shí)并行計(jì)算模型PRAM模型異步APRAM模型BSP模型logP模型BSP模型基本概念由Valiant(1990)

，“塊”同步模型，是一種異步MIMD-DM模型，支持消息傳遞系統(tǒng)，塊內(nèi)異步并行，塊間顯式同步。模型參數(shù)p：處理器數(shù)(帶有

器)l：同步障時(shí)間(Barrier

synchronizationtime)g：帶寬因子(timesteps/packet)=1/bandwidth2021/11/4國(guó)家高性能計(jì)算中心（合肥）24BSP模型計(jì)算過(guò)程由若干超級(jí)步組成，每個(gè)超級(jí)步計(jì)算模式為左圖優(yōu)缺點(diǎn)強(qiáng)調(diào)了計(jì)算和通訊的分離，提供了一個(gè)編程環(huán)境，易于程序復(fù)雜性分析。但需要顯式同步機(jī)制，限制至多h條消息的傳遞等。各處理器2021/11/4國(guó)家高性能計(jì)算中心（合肥）25局部計(jì)算全局通信路障同步圖4.3第四章并行算法的設(shè)計(jì)基礎(chǔ)并行算法的基礎(chǔ)知識(shí)并行計(jì)算模型PRAM模型異步APRAM模型BSP模型logP模型logP模型基本概念由Culler(1993)年，是一種分布的、點(diǎn)到點(diǎn)通訊的多處理機(jī)模型，其中通訊由一組參數(shù)描述，實(shí)行隱式同步。模型參數(shù)L：network

latencyo：communication

overheadg：gap=1/bandwidthP：#processors注：L和g反映了通訊網(wǎng)絡(luò)的容量2021/11/4國(guó)家高性能計(jì)算中心（合肥）27logP模型優(yōu)缺點(diǎn)捕捉了MPC的通訊瓶頸，隱藏了并行機(jī)的網(wǎng)絡(luò)拓?fù)?、路由、協(xié)議，可以應(yīng)用到共享

、消息傳遞、數(shù)據(jù)并行的編程模型中；但難以進(jìn)行算法描述、設(shè)計(jì)和分析