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

第四章 并行算法的設(shè)計(jì)基礎(chǔ)10/23/20231并行計(jì)算相關(guān)的研究分支11..并行計(jì)算機(jī)體系結(jié)構(gòu)22..并行計(jì)算的性能評(píng)價(jià)33..并行算法4.

并行程序設(shè)計(jì)一、并行算法相關(guān)的基本概念及表示二、介紹幾種并行計(jì)算模型一、并行算法相關(guān)的基本概念及表示10/23/20232基本概念并行算法的表示并行算法的復(fù)雜性度量并行算法的同步與通信1.

基本概念10/23/20233定義1：算法：在有限步驟內(nèi)求解某一特定問(wèn)題的一組無(wú)二義性的規(guī)則。定義2：并行算法是由一些獨(dú)立的、可以并行運(yùn)行

的計(jì)算模塊（進(jìn)程）構(gòu)成，模塊（進(jìn)程）之間能

相互作用和協(xié)調(diào)，以完成對(duì)一個(gè)給定問(wèn)題的求解。根據(jù)算法的不同特征，可以對(duì)并行算法進(jìn)行不同的分類(lèi)：10/23/20234–SIMD算法和MIMD算法–同步算法和異步算法–數(shù)值計(jì)算算法和非數(shù)值計(jì)算算法–共享存儲(chǔ)算法和分布存儲(chǔ)算法定義3：同步算法(synchronized

algorithm):是指算法的諸進(jìn)程的執(zhí)行必須相互等待的一類(lèi)并行算法。

SIMD算法是同步算法中的一種特例。定義4：異步算法(asynchronous

algorithm):是指算法的諸進(jìn)程的執(zhí)行不必相互等待的一類(lèi)并行算法。定義5：分布并行算法(distributed

algorithm)：將同一任務(wù)分解為若干個(gè)子任務(wù)，使之分布在由通信鏈路連接的多個(gè)節(jié)點(diǎn)上協(xié)同完成運(yùn)算的算法。分布式算法的執(zhí)行時(shí)間，在很大程度上受通信開(kāi)銷(xiāo)的影響。10/23/20235定義6：確定算法

(deterministic

algorithm)：每個(gè)運(yùn)算步驟上均確定唯一操作的算法。如線性方程組求解的算法。不確定算法(non-deterministicalgorithm)：在問(wèn)題求解的搜索過(guò)程中，提出多種可供選擇的操作，它們中的任一種都有希望獲得問(wèn)題的解答，但都不能肯定解出，有時(shí)甚至不能確定這些操作中哪一種求解的可能性更大些。對(duì)此，只能選擇其中任意一種搜索下去。這種搜索方法稱(chēng)為不確定算法。10/23/20236定義7：隨機(jī)算法(

randomized

algorithm,probabilistic

algorithm

)計(jì)算步驟具有隨機(jī)性的算法。在算法的某一步或某些步上，可以在指定范圍內(nèi)隨機(jī)地選擇下一個(gè)演算步的走向。10/23/20237如果方法得當(dāng)，可比一般算法更快地得出結(jié)果，并且能以較高的概率提供正確的結(jié)果。表示算法的要求無(wú)二義性力圖直觀、易懂不苛求嚴(yán)格的語(yǔ)法格式一般的串行算法常用類(lèi)Pascal、類(lèi)Algol表示10/23/202382.

并行算法的表示1.par-do語(yǔ)句for

i=1

to

n

par-do表示其間的

n

(i=1

ton)

次語(yǔ)句序列的執(zhí)行可以并行完成表示

k

個(gè)處理器同時(shí)執(zhí)行其間的語(yǔ)句序列::end

for2.for

all

語(yǔ)句for

all

Pi

where

0

≤

i≤

k-1

do::for并行算法常引入以下兩條并行語(yǔ)句：10/2e3/2n02d393.

并行算法的復(fù)雜性度量10/23/202310令

f(n)

和

g(n)

是定義在自然數(shù)集合N

上的兩個(gè)函數(shù)，定義8： 如果存在兩個(gè)正數(shù)

c

和

n0

，使得對(duì)于所有的

n

≥

n0

均有f(n)

≤

c

g(n)

，則標(biāo)記為：f(n)=Ο

(

g(n)

)我們稱(chēng)

g(n)

為

f(n)

的上界。定義9： 如果存在兩個(gè)正數(shù)

c

和

n0

，使得對(duì)于所有的

n

≥

n0

均有f(n)

≥

c

g(n)

，則標(biāo)記為：f(n)=

Ω

(

g(n)

)我們稱(chēng)

g(n)

為

f(n)

的下界。定義10：如果存在正數(shù)

c1、c2

和

n0

，使得對(duì)于所有的

n

≥

n0

均有c1

g(n)

≤

f(n)

≤

c2

g(n)

，則標(biāo)記為10/23/202311f(n)=

Θ

(

g(n)

)我們稱(chēng)

g(n)

為

f(n)

的緊致界。即：如果

f(n)=Ο

(

g(n)

)且

f(n)=

Ω

(

g(n)

)則

f(n)=

Θ

(

g(n)

)比較兩個(gè)算法的時(shí)間復(fù)雜性函數(shù)g(n)和f(n)的階的方法：用定義判斷

用求極限的方法來(lái)加以判斷。若則（1）當(dāng)c≠0時(shí)，說(shuō)明f(n)和g(n)同階，記為f(n)=Θ(g(n))（2）當(dāng)c=0時(shí)，說(shuō)明f(n)比g(n)低階，記為f(n)

=O(g(n))（3）當(dāng)c=∞時(shí)，說(shuō)明f(n)比g(n)高階，記為f(n)=Ω(g(n))10/23/202312并行算法的運(yùn)行時(shí)間

t(n)

：對(duì)于輸入規(guī)模為

n的問(wèn)題，在給定的并行計(jì)算模型之下求解問(wèn)題所需的時(shí)間，也稱(chēng)為時(shí)間復(fù)雜性

(

time

complexity

)。運(yùn)行時(shí)間

= 計(jì)算時(shí)間

+ 通信時(shí)間處理器數(shù)p(n)：表示對(duì)給定的問(wèn)題規(guī)模

n，并行算法所用的處理器的個(gè)數(shù)。并行算法的成本c(n)：并行算法的運(yùn)行時(shí)間

t(n)與所需的處理器數(shù)

p(n) 之積，即c(n)

=

t(n)

*

p(n)10/23/202313例:(1)設(shè)f(n)=n2/2,g(n)=307n2，則因此，f(n)=n2/2與g(n)=307n2是同階的。(2)設(shè)f(n)=lg

n，g(n)=n，則所以，f(n)=lg

n比g(n)=n低階。10/23/202314定義11：一個(gè)并行算法最壞情況下的時(shí)間復(fù)雜性(worst-case

time-complexity

) ：對(duì)于所有輸入規(guī)模為

n 的問(wèn)題，在給定的并行計(jì)算模型之下求解問(wèn)題所需的時(shí)間的最大值。定義12：一個(gè)并行算法的期望時(shí)間復(fù)雜性(expected

time-complexity

) ：對(duì)于所有輸入規(guī)模為

n 的問(wèn)題，在給定的計(jì)算模型之下求解問(wèn)題所需的時(shí)間的平均值。10/23/202315定義13：一個(gè)并行算法最壞情況下的空間復(fù)雜性(worst-case

space-complexity) ：對(duì)于所有輸入規(guī)模為

n 的問(wèn)題，在給定的并行計(jì)算模型之下求解問(wèn)題所需的內(nèi)存空間的最大值。定義14：一個(gè)并行算法的期望空間復(fù)雜性(expectedspace-complexity) ：對(duì)于所有輸入規(guī)模為

n

的問(wèn)題，在給定的計(jì)算模型之下求解問(wèn)題所需的內(nèi)存空間的平均值。10/23/202316定義15：如果一個(gè)并行算法的成本與其對(duì)應(yīng)的最佳串行算法的最壞情況下時(shí)間復(fù)雜性在同一個(gè)數(shù)量級(jí)上，則稱(chēng)該并行算法為成本最佳的(

cost-optimal

) 或最佳并行算法

(optimal

parallelalgorithm

)。總運(yùn)算量W

(n):

(并行)算法中所要完成的總的操作數(shù)量(

the

number

of

computationaloperations

)10/23/2023174.

并行算法中的同步與通信10/23/202318同步(synchronization)：使多個(gè)相關(guān)事件的發(fā)生保持相同的節(jié)奏，彼此之間能良好地配合。在并行算法的各進(jìn)程異步執(zhí)行過(guò)程中，為了確保

各處理器的正確工作順序和對(duì)共享存儲(chǔ)器的訪問(wèn)，程序員需要在算法的適當(dāng)位置設(shè)置同步點(diǎn)。下面給出一個(gè)利用

lock

和

unlock 構(gòu)造的臨界區(qū)完成數(shù)組求和的算法[算法4.1.3]

共享存儲(chǔ)多處理機(jī)上求和算法輸入：A

=

(a0

,

a1

,…,an-1)

,

處理器數(shù)

p；輸出：a

0

+a1

+…+an-1存放在全局變量S

中。beginS

=

0for

all

Pi

where

0

i

p-1

doL

=

0for

j

=

i

ton-1

step

p

doL

=

L

+

ajend

forlock

(u)S

=

S

+

Lunlock

(u)end

for10/23/202319end通信(communication)：把信息用一定手段通過(guò)某種介質(zhì)或傳輸線路從一個(gè)點(diǎn)傳送至另一點(diǎn)的過(guò)程。通信是在空間上對(duì)并發(fā)執(zhí)行的進(jìn)程實(shí)現(xiàn)數(shù)據(jù)交換。原語(yǔ)

(primitive)：它由若干條機(jī)器指令構(gòu)成的，用來(lái)完成特定功能的一段程序。原語(yǔ)有以下特點(diǎn)：不可中斷性：一旦原語(yǔ)被開(kāi)始執(zhí)行，就應(yīng)不間斷地執(zhí)行到結(jié)束；不可侵犯性：原語(yǔ)一旦被執(zhí)行，中間不許插入任何其他操作。10/23/202320通信可使用通信原語(yǔ)來(lái)表示：在共享存儲(chǔ)的多處理機(jī)中，可使用global

read

(X,

Y)將全局存儲(chǔ)器中數(shù)據(jù)

X 讀入局部變量

Y；global

write

(U,

V)將局部數(shù)據(jù)

U 寫(xiě)入共享存儲(chǔ)變量

V 中。在分布存儲(chǔ)的多計(jì)算機(jī)中，可使用send

(X,

i

)

或

send

(X,

Pi

)當(dāng)前處理器發(fā)送數(shù)據(jù)

X

到

Pi

；receive

(Y,

j

)

或

receive

(Y,

Pj

)當(dāng)前處理器從Pj

接收數(shù)據(jù)

Y。10/23/202321[算法4.1.4]

分布存儲(chǔ)多計(jì)算機(jī)上矩陣向量相乘算法給定:一個(gè)n*n

的矩陣A和一個(gè)向量Xa11

a12

a13……

a1n-1

a1nA

=a21

a22

a23……

a2n-1

a2na31

a32

a33……

a3n-1

a3n……..an1an2

an3……

ann-1

annx1x2X

=

x3…xn計(jì)算:

A*X，得到一個(gè)向量。假設(shè)

r

=

n/p 為一整數(shù)因?yàn)槲覀兇蛩阍诜植即鎯?chǔ)的多計(jì)算機(jī)系統(tǒng)上運(yùn)行該算法，被計(jì)算的數(shù)據(jù)只能分布在各個(gè)處理器的局部器上。10/2存3/20儲(chǔ)2322我們把

A 按列分為

p

個(gè)

n*r 的小矩陣A1

,

A2

,…

,

Ap把

X 按行分為

p

個(gè)

r*1 的小向量X1

,

X2

,…

,

Xp計(jì)算

A*X就轉(zhuǎn)化為計(jì)算：A1

X1

+

A2

X2

+…

Ap

Xp所以處理器Pi（其中1

≤

i

≤

p）將Ai

和 Xi

存放在自己的局部存儲(chǔ)器中，各處理器首先計(jì)算 Ai

Xi，然后利用通信實(shí)現(xiàn)數(shù)據(jù)求和。X1(r*1)X2(r*1)…Xp(r*1)X

=A

=

A1

A2

…

Ap(n*r)

(n*r)

(n*r)10/23/2023

23我們假設(shè)處理器是以環(huán)結(jié)構(gòu)組織的PiP2PpP110/23/202324[算法4.1.4]分布存儲(chǔ)多計(jì)算機(jī)上矩陣向量相乘算法輸入：處理器數(shù)p，第i

個(gè)A

矩陣分量Ai

于B

中，第i個(gè)X向量分量Xi于w中;輸出：A*X

于

P1

變量

y中。begincompute

z

=

Bwif i

=

1

then

y

=

0else

receive

(y

,

left)endify

=

y

+

zsend

(y

,right)if i

=

1

then

receive

(y

,left)en10/d23/202325p1p3p2p4計(jì)算z=Bw計(jì)算z=Bw計(jì)算z=Bw計(jì)算z=Bwy=0rec(y,

p1)rec(y,

p2)rec(y,

p3)y=y+zsend(y,p2)send(y,p3)send(y,p4)rec(y,p4)y=y+zy(1)y=y+zy(2)y=y+zy(3)y(4)結(jié)束10/23/2023send(y,p126)第四章 并行算法的設(shè)計(jì)基礎(chǔ)10/23/202327一、并行算法相關(guān)的基本概念及表示二、介紹幾種并行計(jì)算模型二、并行計(jì)算模型10/23/202328并行計(jì)算模型：從并行算法的設(shè)計(jì)和分析出發(fā)，將各種并行計(jì)算機(jī)（至少是某一類(lèi)并行計(jì)算機(jī)）的基本特征抽象出來(lái)，形成一個(gè)抽象的計(jì)算模型。并行計(jì)算模型為并行計(jì)算提供了硬件和軟件的界面，使硬件設(shè)計(jì)者和軟件設(shè)計(jì)者可以開(kāi)發(fā)并行性的支持機(jī)制，從而提高系統(tǒng)的性能。對(duì)并行算法的研制者，不會(huì)局限于某種具體的并行計(jì)算機(jī)來(lái)研究并行算法，而需借助于抽象的計(jì)算

模型，它是設(shè)計(jì)和分析并行算法的基礎(chǔ)。編程模型計(jì)算模型體系結(jié)構(gòu)模型機(jī)器模型為了能對(duì)計(jì)算機(jī)系統(tǒng)進(jìn)行簡(jiǎn)單、明確的描述，發(fā)現(xiàn)一般規(guī)律，通常在不同層次上進(jìn)行抽象來(lái)定義模型。不同層次模型的關(guān)系圖：用戶(hù)系統(tǒng)硬件和操作系統(tǒng)互連網(wǎng)絡(luò)的作用和執(zhí)行通信的形式等計(jì)算機(jī)的費(fèi)用和資源編程語(yǔ)言的語(yǔ)義10/23/202329并行計(jì)算模型的主要作用：它是并行算法實(shí)現(xiàn)的基礎(chǔ)對(duì)同一問(wèn)題在不同的模型上的不同解決辦法，來(lái)比較該問(wèn)題究竟更合理在哪一種模型上實(shí)現(xiàn)它給并行算法設(shè)計(jì)和分析提供了一個(gè)簡(jiǎn)單、方便的框架撇開(kāi)了硬件的繁雜的細(xì)節(jié)它使并行算法設(shè)計(jì)具有一定的生命力集中精力開(kāi)發(fā)應(yīng)用問(wèn)題自身的并行性和算法的性能，并使算法具有一定的通用性10/23/202330串行算法的研究已經(jīng)相當(dāng)成熟，它們基本上都是基于馮.諾依曼(von

Neumann)體系結(jié)構(gòu)控制器運(yùn)算器主存儲(chǔ)器輸出設(shè)備輸入設(shè)備CPU高速緩存10/23/202331程序指令計(jì)數(shù)器r0r1r2r3:存儲(chǔ)器累加器x1x2……xn只讀輸入磁帶y1y2……只寫(xiě)輸出磁帶串行計(jì)算模型RAM

(Random

Access

Machine)10/23/202332RAM機(jī)器模型的指令系統(tǒng)與實(shí)際計(jì)算機(jī)的指令系統(tǒng)類(lèi)似，有四類(lèi)指令：控制流向指令，

如

jump;輸入/輸出指令，

如

read

,

write；累加器與存儲(chǔ)器之間的傳送數(shù)據(jù)指令，如

load；算術(shù)運(yùn)算指令，

如

add。10/23/2023331.

PRAM

模型10/23/202334(Parallel

Random

Access

Machine

Model)1978年S.

Fortune

和

J. Wyllie總結(jié)了陣列式結(jié)構(gòu)的并行機(jī)和流水線結(jié)構(gòu)的向量機(jī)的特點(diǎn)，將其抽象為具有如下特征的

PRAM 模型：有一個(gè)控制器有

p（可有限或無(wú)限）臺(tái)功能相同的處理器有一個(gè)容量無(wú)限的共享存儲(chǔ)器每臺(tái)處理器有自己的局部存儲(chǔ)器處于激活狀態(tài)的處理器必須執(zhí)行相同的指令允許任何時(shí)刻各處理器均可通過(guò)共享存儲(chǔ)器與其它處理器交換數(shù)據(jù)。PRAM模型----SIMD計(jì)算模型控

制

器互

聯(lián)

網(wǎng)

絡(luò)全

局

共

享

存

儲(chǔ)

器P1LM1P2LM2PpLMp……10/23/202335PRAM

模型允許任何時(shí)刻各處理器均可通過(guò)共享存儲(chǔ)器的共享單元與其它處理器交換數(shù)據(jù)。根據(jù)處理器對(duì)共享單元的存、取訪問(wèn)的不同約束條件進(jìn)一步對(duì)

PRAM 模型分類(lèi)：–PRAM-EREW

(Exclusive

Read,

ExclusiveWrite)：不允許有讀沖突和寫(xiě)沖突–PRAM-CREW

(Concurrent

Read,

ExclusiveWrite)：每次允許多臺(tái)處理器同時(shí)讀同一共享單元內(nèi)容，但不允許同時(shí)寫(xiě)。–PRAM-CRCW

(Concurrent

Read,

ConcurrentWrite)：允許多臺(tái)處理器同時(shí)讀、寫(xiě)同一共享單元內(nèi)容。10/23/202336PRAM-CRCW

模型中允許同時(shí)寫(xiě)同一共享單元顯然是不現(xiàn)實(shí)的，所以對(duì)PRAM-CRCW

模型作了更進(jìn)一步的約定：–共用的(Common)

PRAM-CRCW：同時(shí)寫(xiě)同一共享單元的所有處理器必須寫(xiě)相同的值；–優(yōu)先的(Priority)

PRAM-CRCW：從同時(shí)要寫(xiě)同一共享單元的所有處理器中找出標(biāo)號(hào)最小的處理器，將它的值寫(xiě)入共享地址中；–任意的

(Arbitrary) PRAM-CRCW：從同時(shí)要寫(xiě)同一共享單元的所有處理器中任選一個(gè)處理器的值寫(xiě)入共享地址中。10/23/202337PRAM

模型上的算法的執(zhí)行：輸入數(shù)據(jù)存放在全局共享存儲(chǔ)器中，并只有一個(gè)處理器處于激活狀態(tài)；在每個(gè)計(jì)算步中，一個(gè)激活的處理器可做：–從局部或全局存儲(chǔ)器中讀一個(gè)值–完成一個(gè)

RAM 操作–寫(xiě)值到局部或全局存儲(chǔ)器中–激活另一個(gè)處理器10/23/202338[算法4.2.1]

在

PRAM-EREW 模型上求和算法輸入：n個(gè)待求和的數(shù)

A

[0..(n-1)]輸出：最終的n個(gè)數(shù)的和在

A

[0]

中全局變量：n

,

A

[

0..(n-1)]

,

jbegin*

spawn(P0,

P1,

…

, P

n/2

-

1)for

all

Pi

where

0

i

n/2

-

1

dofor

j

=

0

to

log

n

-

1

doif

i

mod

2j

=

0

and

2i +2j

<

n

thenA

[

2i

]

=

A

[

2i

]

+

A

[

2i

+2j

]endifendfor10/23/2023endfor39spawn()：激活n個(gè)處理機(jī)例：n=12時(shí)間sp10a/2w3/20n23

()：激活n

個(gè)處理機(jī)的時(shí)間為?log

n?。402.

APRAM 模型

(

Asynchronous

PRAM

)10/23/20234180年代初，人們總結(jié)了共享存儲(chǔ)型多處理機(jī)結(jié)構(gòu)的向量機(jī)的特點(diǎn)，將其抽象為具有如下特征的APRAM 模型：有

p（可有限或無(wú)限）個(gè)處理器；每個(gè)處理器有自己的控制器（局部時(shí)鐘）；有一個(gè)容量無(wú)限的共享存儲(chǔ)器；每臺(tái)處理器有自己的局部存儲(chǔ)器和局部程序；各處理器異步地、獨(dú)立地執(zhí)行各自的指令，處理器間的同步需明確地在各處理器的程序中加入障礙（路障）同步

(barrier

synchronization)

指令；利用共享存儲(chǔ)器實(shí)現(xiàn)處理器間的通信。APRAM

模型----MIMD計(jì)算模型控制器1互

聯(lián)

網(wǎng)

絡(luò)P1LM1P2LM2PpLMp……控制器2控制器p……全局共享存儲(chǔ)器10/23/202342PRAM模型----SIMD計(jì)算模型（對(duì)比）控

制

器互

聯(lián)

網(wǎng)

絡(luò)P1LM1P2LM2PpLMp……全局共享存儲(chǔ)器10/23/202343APRAM

模型同樣利用共享存儲(chǔ)器實(shí)現(xiàn)處理器間的通信障礙(路障)同步(barrier

synchronization)：它在程序中設(shè)置一些障礙點(diǎn)，當(dāng)處理器執(zhí)行到障礙點(diǎn)時(shí)暫停，等待所有進(jìn)程都執(zhí)行到這個(gè)障礙點(diǎn)上，以此方法取得同步。10/23/202344APRAM 模型中的計(jì)算

:–計(jì)算是由一系列用同步障礙點(diǎn)分開(kāi)的全局相（global

phase）組成的。在各全局相內(nèi)每個(gè)處理器異步地運(yùn)行其局部程序每個(gè)局部程序中的最后一條指令是一條障礙同步指令各處理器均可異步地讀取和寫(xiě)入全局存儲(chǔ)器，但在同一相（phase）內(nèi)不允許兩個(gè)處理器訪問(wèn)同一共享單元10/23/202345處理器

1處理器

2處理器

3Phase1同步障礙read

x1read

x2:write

to

Aread

x3:write

to

Bwrite

to

Cread

xn::write

to

Dread

C:read

B:write

to

Bread

A:write

to

Dwrite

to

C::read

D:Phase2同步障礙Phase310/23/2023同步障礙write

to

Bread

A:write

to

B46在APRAM模型上設(shè)計(jì)的算法的時(shí)間復(fù)雜性包括以下幾個(gè)方面：–假設(shè)一個(gè)局部操作取為

1 個(gè)單位時(shí)間–全局讀/寫(xiě)時(shí)間為

d，它表示全局讀/寫(xiě)的平均時(shí)間。該值應(yīng)隨著處理器的個(gè)數(shù)增加而增加。–同步障礙的時(shí)間為

B，B 是處理器個(gè)數(shù)

p 的非遞減函數(shù)

B

(p)

。–在

APRAM 中常假設(shè)：2

≤

d

≤

B

≤

p–設(shè) tph

為全局相內(nèi)各處理器指令執(zhí)行時(shí)間中最長(zhǎng)者，則整個(gè)程序運(yùn)行時(shí)間

T 應(yīng)為：T

=

Σ

tph

+

B

*

同步障礙次數(shù)10/23/2023473.

Log

P

模型10/23/202348(Latency

,

overhead

,

gap

,

Processor)1993年D.Culler等人在分析了分布式存儲(chǔ)計(jì)算機(jī)特點(diǎn)的基礎(chǔ)上，提出了基于點(diǎn)到點(diǎn)通信的多計(jì)算機(jī)模型----Log

P模型。該模型雖未涉及到網(wǎng)絡(luò)的具體結(jié)構(gòu)，但充分說(shuō)明了互聯(lián)網(wǎng)絡(luò)的性能特性：–互連網(wǎng)絡(luò)帶寬的限制–通信中可觀的延遲它是

MPP

系統(tǒng)的模型Log

P 模型主要由以下4個(gè)參數(shù)來(lái)描述：

1）L(Latency)最大延遲：在通信時(shí)包含一個(gè)或幾個(gè)字的一個(gè)消息從源節(jié)點(diǎn)傳到目標(biāo)節(jié)點(diǎn)的時(shí)間的上限值。2）o(overhead)開(kāi)銷(xiāo)：處理器準(zhǔn)備發(fā)送或接收一個(gè)消息的時(shí)間開(kāi)銷(xiāo)，在這段時(shí)間里處理器不能執(zhí)行其它操作。3）g(gap)間隔：一臺(tái)處理器發(fā)送或接收一組消息時(shí)，兩個(gè)消息之間的最小時(shí)間間隔，其倒數(shù)即為處理器的通信帶寬。4）P(Processor)節(jié)點(diǎn)數(shù)：處理器/存儲(chǔ)器個(gè)數(shù)，假定每個(gè)局部操作需要

1 個(gè)單位時(shí)間（即一個(gè)處理器周期）。10/23/202349Log

P

的參數(shù)示意圖Pj處理器L

oo

gPi下一個(gè)消息消息Pk時(shí)間發(fā)送并接收一個(gè)消息共需2o+L個(gè)單位時(shí)間; 處理器

Pi 在向處理器10P/2j3/20發(fā)23

送消息后, 在發(fā)送下一個(gè)消息之前必須等待

g 個(gè)時(shí)間50單位。LogP模型的特點(diǎn)–處理機(jī)之間異步地工作，通過(guò)消息傳遞實(shí)現(xiàn)同步；–消息延遲不確定，但延遲不會(huì)大于L，即任何消息經(jīng)歷的等待時(shí)間是不可預(yù)測(cè)的，但不會(huì)超過(guò)L；–Log

P模型支持了計(jì)算和通信的重疊；–能夠預(yù)測(cè)算法的實(shí)際運(yùn)行時(shí)間。Log

P模型抓住了網(wǎng)絡(luò)與處理機(jī)之間的性能瓶頸。消息間隔參數(shù)

g 反映了通信帶寬，當(dāng)一臺(tái)處理機(jī)發(fā)送的消息已到達(dá)這個(gè)容量限度時(shí)，再發(fā)送的消息將被阻塞。10/23/202351例2：在通信模式是一棵樹(shù)的情況下求和算法假設(shè)P=8、L=5、g=4、o=2，我們考慮在時(shí)間為28個(gè)單位時(shí)間內(nèi)最多可能求和的個(gè)數(shù)。P0P4P6P7P2P3P5P110/23/2023524.

BSP 模型

(Bulk

Synchronous

Parallel)10/23/202353BSP 模型是一個(gè)分布存儲(chǔ)的

MIMD

計(jì)算模型BSP

模型的組成主要包括如下部分：

1）若干個(gè)能進(jìn)行處理和內(nèi)存操作的處理器，一個(gè)用于在處理器之間傳遞消息的路由器，在定義的時(shí)間間隔內(nèi)，對(duì)所有處理器進(jìn)行同步的機(jī)制。一般情況下，假設(shè)這個(gè)全局同步機(jī)制是用特殊的硬件支持的。一個(gè)

BSP 程序是由一系列超步

(superstep) 組成的。BSP 模型有以下三個(gè)重要參數(shù)： 1）處理器數(shù)

p路由器吞吐量

g，（也稱(chēng)為帶寬因子）全局同步之間的時(shí)間間隔

L在一個(gè)超步中，一個(gè)處理機(jī)最多發(fā)送

h

個(gè)消息或接收

h

個(gè)消息。若有

h

個(gè)消息，則稱(chēng)此通信有一個(gè)h

關(guān)系(h-relation)。g

值的定義方式：–每秒處理機(jī)所能完成的局部計(jì)算數(shù)與每秒路由器所能傳輸?shù)臄?shù)據(jù)量之比；或–在一個(gè)10/23/2023h關(guān)系中,傳遞h個(gè)消息所需的時(shí)間為g.h。54BSP 模型與

APRAM 模型類(lèi)似，使用障礙同步使整個(gè)計(jì)算任務(wù)以緊同步方式進(jìn)行各處理器局部計(jì)算全局通信障礙同步max+

l1一0/23個(gè)/2023超步的執(zhí)行時(shí)間：計(jì)算時(shí)間max

+

gh55BSP 模型的主要特點(diǎn)：–將處理器和路由器分開(kāi)，即把計(jì)算任務(wù)和通信任務(wù)分開(kāi)。路由器僅進(jìn)行點(diǎn)到點(diǎn)的消息傳遞，不考慮互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)；–利用硬件實(shí)現(xiàn)全局障礙同步使并行粒度增大(相對(duì)

APRAM而言)，并能夠?qū)崿F(xiàn)緊耦合同步并行算法；–兼顧了計(jì)算和通信的平衡問(wèn)題；–硬件可將L設(shè)置盡量小----這表示通信帶寬會(huì)更寬些，在設(shè)計(jì)并行算法時(shí)應(yīng)使L盡量大從而提高并行粒度。10/23/2023565.

C3

模型(Computing,

Communication,

Congestion)10/23/2023571994 年S.

E.

Hambrush 等人在分析高性能可擴(kuò)展的網(wǎng)絡(luò)計(jì)算機(jī)系統(tǒng)特點(diǎn)的基礎(chǔ)上提出了

C3

模型，它適用于粗粒度的并行系統(tǒng)。和

BPS

與

Log

P 模型相似，

C3

計(jì)算模型也將計(jì)算劃分為一系列超級(jí)步，同步出現(xiàn)在兩個(gè)超級(jí)步之間，這個(gè)同步也是利用障礙同步機(jī)制來(lái)實(shí)現(xiàn)。–擁塞(Congestion)：在通信網(wǎng)絡(luò)中，當(dāng)各輸入站的呼叫數(shù)量超過(guò)網(wǎng)絡(luò)的容量，或超過(guò)了網(wǎng)絡(luò)處理的能力時(shí)，則稱(chēng)網(wǎng)絡(luò)中發(fā)生了擁塞。C3

模型主要由以下幾個(gè)參數(shù)來(lái)描述：處理器的個(gè)數(shù)

p；網(wǎng)絡(luò)延遲

h：網(wǎng)絡(luò)中任意兩節(jié)點(diǎn)間的距離的平均值；網(wǎng)絡(luò)的對(duì)分寬度

b：表示網(wǎng)絡(luò)的帶寬；啟動(dòng)時(shí)間

s，即建立一個(gè)消息時(shí)的開(kāi)銷(xiāo)；消息包的長(zhǎng)度

l，即消息包所含字節(jié)數(shù)。消息包是處理機(jī)間通信的基本單位。10/23/202358C3模型中用到的一些概念10/23/202359C3

模型中考慮了兩種路由方式：–存儲(chǔ)轉(zhuǎn)發(fā)路由方式(store-and-forwardmode)：它是網(wǎng)絡(luò)中信息交換的一種方式。轉(zhuǎn)發(fā)中心不是將終端發(fā)出的信息立即傳送到接收終端，而是先存儲(chǔ)起來(lái)，等待適當(dāng)?shù)臅r(shí)機(jī)，選擇空閑的信道，并按信息的優(yōu)先級(jí)別轉(zhuǎn)發(fā)到下一個(gè)轉(zhuǎn)發(fā)中心或接收終端。–蟲(chóng)孔(蟲(chóng)蝕)路由方式(wormhole

routing

mode)：在平面網(wǎng)絡(luò)結(jié)構(gòu)的多處理機(jī)系統(tǒng)中進(jìn)行路徑選擇的一種方法。它把消息分成若干個(gè)包，包又分成若干個(gè)稱(chēng)為遷移塊(flit)的基本信息單元。每個(gè)包中的遷移塊以流水線方式向前依次傳送。只有包的頭幾個(gè)遷移塊含有路徑信息，因而一個(gè)包的所有遷移塊必須一個(gè)跟著一個(gè)，而不能被別的消息包打斷。C3

模型中用到的一些概念10/23/202360C3

模型中考慮了兩種發(fā)送/接收原語(yǔ)：

1）阻塞發(fā)送和接收原語(yǔ)2）非阻塞發(fā)送和接收原語(yǔ)阻塞發(fā)送

(blocking

send) ：指一個(gè)源處理器從開(kāi)始發(fā)送一條消息，直到它被目標(biāo)處理器收到消息，源處理器的發(fā)送操作才結(jié)束。非阻塞的發(fā)送

(non-blocking

send) ：源處理器只需將要發(fā)送的消息放在發(fā)送緩沖器。非阻塞的發(fā)送不需考慮目標(biāo)處理器什么時(shí)候接收到信息。各種并行計(jì)算模型的比較模型屬性PRAMAPRAMLog

PBSPC3體系結(jié)構(gòu)SIMD-SMMIMD-SMMIMD-DMMIMD-DMMIMD-DM計(jì)算模式同步計(jì)算異步計(jì)算異步計(jì)算異步計(jì)算異步計(jì)算同步方式自動(dòng)同步障礙同步隱式同步障礙同步障礙同步計(jì)算粒度細(xì)/中粒度中/大粒度中/大粒度中/大粒度粗粒度通信方式共享變量共享變量發(fā)/收消息發(fā)/收消息發(fā)/收消息模型參數(shù)10/23/20231

(單位時(shí)間步)d:全局讀/寫(xiě)時(shí)間B:同步時(shí)間L:通信延遲

o:通信開(kāi)銷(xiāo)

g:消息間隔

P:處理器數(shù)p:處理器數(shù)

g:帶寬因子

L:同步間隔l:消息包長(zhǎng)度s:發(fā)送開(kāi)銷(xiāo)

h:通信延61遲由于并行計(jì)算機(jī)正在處于飛速發(fā)展中，但尚未定型，因此到現(xiàn)在為止，還沒(méi)有一個(gè)通用的并行計(jì)算模型。人們只能將某一類(lèi)并行機(jī)的基本特征抽象出來(lái)，形成各種特定的并行計(jì)算模型，以便并行算法的設(shè)計(jì)與理論分析。10/23/202362PRAM 模型是對(duì)一類(lèi)共享的并行機(jī)特征抽取，它拋開(kāi)了通信的干擾，可用于開(kāi)發(fā)細(xì)粒度并行算法；Log

P 模型是對(duì)一類(lèi)分布式并行計(jì)算機(jī)特征抽取，基于點(diǎn)對(duì)點(diǎn)通信的計(jì)算模型，集中分析處理機(jī)與

網(wǎng)絡(luò)之間的瓶頸問(wèn)題；C3

模型是對(duì)一類(lèi)基于消息傳遞的分布式粗粒度系統(tǒng)特征抽取，集中反映的是網(wǎng)絡(luò)擁擠和路由影響。10/23/202363例1_1：在PRAM-EREW計(jì)算機(jī)上對(duì)兩個(gè)

N 維向量

A

和B 求內(nèi)積

s。假設(shè)用

p 個(gè)處理機(jī)完成該任務(wù)，并設(shè)N/p 是整數(shù)，內(nèi)積的值在

LocalVal

[0] 中。VECTORMUL(PRAM-EREW):Global

N,

i,

A[0..N-1],

B[0..N-1],

LocalVal[0..p-1]Local

jbeginspawn(P0,

P1,

P2,

…,

Pp-1)for

allPi,其中0

≤i≤p-1dobeginLocalVal[i]

=0;for

j

=

i;

j

<

N

step

p

doLocalVal[i]

=

LocalVal[i]

+

A[j]

*

B[j];for

j

=

0

to

?log

p?

-1

doif imod

2j+1

==

0and

i+2j

<pthenLocalVal[i]

=

LocalVal[i]

+

LocalVal[i

+2j