課件多核并行計算

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

i=1

to

n

par-do……end

forfor

all語句for

all

Pi,

where0≤i≤k

do……end

for第四章并行算法的設計基礎并行算法的基礎知識并行算法的定義和分類并行算法的表達并行算法的復雜性度量并行算法中的同步和通訊并行計算模型并行算法的復雜性度量串行算法的復雜性度量情況下的復雜度(Worst-Case

Complexity)期望復雜度(Expected

Complexity)并行算法的幾個復雜性度量指標運行時間t(n):包含計算時間和通訊時間，分別用計算時間步和選路時間步作單位。n為問題實例的輸入規(guī)模。處理器數(shù)p(n)并行算法成本c(n):c(n)=t(n)p(n)情形下串行算法所需要的時間，則成本最優(yōu)性：若c(n)等于在并行算法是成本最優(yōu)的?？傔\算量W(n):并行算法求解問題時所完成的總的操作步數(shù)。2021/11/4國家高性能計算中心（合肥）8并行算法的復雜性度量Brent定理令W(n)是某并行算法A在運行時間T(n)內所執(zhí)行的運算量，則A使用p臺處理器可在t(n)=O(W(n)/p+T(n))時間內執(zhí)行完畢。注：(1)揭示了并行算法工作量和運行時間的關系；(2)提供了并行算法的WT(Work-Time)表示方法；(3)告訴

：設計并行算法時應盡可能將每個時間步的工作量均勻地分攤給p臺處理器，使各處理器處于活躍狀態(tài)。2021/11/4國家高性能計算中心（合肥）9第四章并行算法的設計基礎并行算法的基礎知識并行算法的定義和分類并行算法的表達并行算法的復雜性度量并行算法中的同步和通訊并行計算模型并行算法的同步同步概念同步是在時間上強使各執(zhí)行進程在某一點必須互相等待；可用

、硬件和固件的辦法來實現(xiàn)。同步語句示例算法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國家高性能計算中心（合肥）112021/11/4并行算法的通訊（1）通訊共享

多處理器使用：global

read(X,Y)和global

write(X,Y)分布

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

分布

多計算機上矩陣向量乘算法輸入：處理器數(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國家高性能計算中心（合肥）13并行算法的通訊（2）計算過程圖示2021/11/4國家高性能計算中心（合肥）14第四章并行算法的設計基礎并行算法的基礎知識并行計算模型PRAM模型異步APRAM模型BSP模型logP模型PRAM模型基本概念由Fortune和Wyllie1978年提出，又稱SIMD-SM模型。有一個集中的共享

器和一個指令控制器，通過SM

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

UnitInterconnection

NetworkPPPLM

LM

LMPLMShared

Memory2021/11/4國家高性能計算中心（合肥）16PRAM模型分類PRAM-CRCW并發(fā)讀并發(fā)寫CPRAM-CRCW(Common

PRAM-CRCW)：僅允許寫入相同數(shù)據(jù)PPRAM-CRCW(Priority

PRAM-CRCW)：僅允許優(yōu)先級最高的處理器寫入APRAM-CRCW(Arbitrary

PRAM-CRCW)：允許任意處理器 寫入PRAM-CREW并發(fā)讀互斥寫PRAM-EREW互斥讀互斥寫計算能力比較PRAM-CRCW是最強的計算模型，PRAM-EREW可logp倍模擬PRAM-CREW和PRAM-CRCWTEREW

TCREW

TCRCWTEREW

O(TCREW

log

p)

O(TCRCW

log

p)TEREW

TCREW

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

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

2

d

B

p

；B

B(p)

O(d

log

p)或O(d

log

p

/log

d

)令t

ph

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

t

ph

B

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

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

器)l：同步障時間(Barrier

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

latencyo：communication

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

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