第四章并行算法的设计基础课件

第四章 并行算法的设计基础10/23/20231并行计算相关的研究分支11..并行计算机体系结构22..并行计算的性能评价33..并行算法4.

并行程序设计一、并行算法相关的基本概念及表示二、介绍几种并行计算模型一、并行算法相关的基本概念及表示10/23/20232基本概念并行算法的表示并行算法的复杂性度量并行算法的同步与通信1.

基本概念10/23/20233定义1：算法：在有限步骤内求解某一特定问题的一组无二义性的规则。定义2：并行算法是由一些独立的、可以并行运行

的计算模块（进程）构成，模块（进程）之间能

相互作用和协调，以完成对一个给定问题的求解。根据算法的不同特征，可以对并行算法进行不同的分类：10/23/20234–SIMD算法和MIMD算法–同步算法和异步算法–数值计算算法和非数值计算算法–共享存储算法和分布存储算法定义3：同步算法(synchronized

algorithm):是指算法的诸进程的执行必须相互等待的一类并行算法。

SIMD算法是同步算法中的一种特例。定义4：异步算法(asynchronous

algorithm):是指算法的诸进程的执行不必相互等待的一类并行算法。定义5：分布并行算法(distributed

algorithm)：将同一任务分解为若干个子任务，使之分布在由通信链路连接的多个节点上协同完成运算的算法。分布式算法的执行时间，在很大程度上受通信开销的影响。10/23/20235定义6：确定算法

(deterministic

algorithm)：每个运算步骤上均确定唯一操作的算法。如线性方程组求解的算法。不确定算法(non-deterministicalgorithm)：在问题求解的搜索过程中，提出多种可供选择的操作，它们中的任一种都有希望获得问题的解答，但都不能肯定解出，有时甚至不能确定这些操作中哪一种求解的可能性更大些。对此，只能选择其中任意一种搜索下去。这种搜索方法称为不确定算法。10/23/20236定义7：随机算法(

randomized

algorithm,probabilistic

algorithm

)计算步骤具有随机性的算法。在算法的某一步或某些步上，可以在指定范围内随机地选择下一个演算步的走向。10/23/20237如果方法得当，可比一般算法更快地得出结果，并且能以较高的概率提供正确的结果。表示算法的要求无二义性力图直观、易懂不苛求严格的语法格式一般的串行算法常用类Pascal、类Algol表示10/23/202382.

并行算法的表示1.par-do语句for

i=1

to

n

par-do表示其间的

n

(i=1

ton)

次语句序列的执行可以并行完成表示

k

个处理器同时执行其间的语句序列::end

for2.for

all

语句for

all

Pi

where

0

≤

i≤

k-1

do::for并行算法常引入以下两条并行语句：10/2e3/2n02d393.

并行算法的复杂性度量10/23/202310令

f(n)

和

g(n)

是定义在自然数集合N

上的两个函数，定义8： 如果存在两个正数

c

和

n0

，使得对于所有的

n

≥

n0

均有f(n)

≤

c

g(n)

，则标记为：f(n)=Ο

(

g(n)

)我们称

g(n)

为

f(n)

的上界。定义9： 如果存在两个正数

c

和

n0

，使得对于所有的

n

≥

n0

均有f(n)

≥

c

g(n)

，则标记为：f(n)=

Ω

(

g(n)

)我们称

g(n)

为

f(n)

的下界。定义10：如果存在正数

c1、c2

和

n0

，使得对于所有的

n

≥

n0

均有c1

g(n)

≤

f(n)

≤

c2

g(n)

，则标记为10/23/202311f(n)=

Θ

(

g(n)

)我们称

g(n)

为

f(n)

的紧致界。即：如果

f(n)=Ο

(

g(n)

)且

f(n)=

Ω

(

g(n)

)则

f(n)=

Θ

(

g(n)

)比较两个算法的时间复杂性函数g(n)和f(n)的阶的方法：用定义判断

用求极限的方法来加以判断。若则（1）当c≠0时，说明f(n)和g(n)同阶，记为f(n)=Θ(g(n))（2）当c=0时，说明f(n)比g(n)低阶，记为f(n)

=O(g(n))（3）当c=∞时，说明f(n)比g(n)高阶，记为f(n)=Ω(g(n))10/23/202312并行算法的运行时间

t(n)

：对于输入规模为

n的问题，在给定的并行计算模型之下求解问题所需的时间，也称为时间复杂性

(

time

complexity

)。运行时间

= 计算时间

+ 通信时间处理器数p(n)：表示对给定的问题规模

n，并行算法所用的处理器的个数。并行算法的成本c(n)：并行算法的运行时间

t(n)与所需的处理器数

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

=

t(n)

*

p(n)10/23/202313例:(1)设f(n)=n2/2,g(n)=307n2，则因此，f(n)=n2/2与g(n)=307n2是同阶的。(2)设f(n)=lg

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

n比g(n)=n低阶。10/23/202314定义11：一个并行算法最坏情况下的时间复杂性(worst-case

time-complexity

) ：对于所有输入规模为

n 的问题，在给定的并行计算模型之下求解问题所需的时间的最大值。定义12：一个并行算法的期望时间复杂性(expected

time-complexity

) ：对于所有输入规模为

n 的问题，在给定的计算模型之下求解问题所需的时间的平均值。10/23/202315定义13：一个并行算法最坏情况下的空间复杂性(worst-case

space-complexity) ：对于所有输入规模为

n 的问题，在给定的并行计算模型之下求解问题所需的内存空间的最大值。定义14：一个并行算法的期望空间复杂性(expectedspace-complexity) ：对于所有输入规模为

n

的问题，在给定的计算模型之下求解问题所需的内存空间的平均值。10/23/202316定义15：如果一个并行算法的成本与其对应的最佳串行算法的最坏情况下时间复杂性在同一个数量级上，则称该并行算法为成本最佳的(

cost-optimal

) 或最佳并行算法

(optimal

parallelalgorithm

)。总运算量W

(n):

(并行)算法中所要完成的总的操作数量(

the

number

of

computationaloperations

)10/23/2023174.

并行算法中的同步与通信10/23/202318同步(synchronization)：使多个相关事件的发生保持相同的节奏，彼此之间能良好地配合。在并行算法的各进程异步执行过程中，为了确保

各处理器的正确工作顺序和对共享存储器的访问，程序员需要在算法的适当位置设置同步点。下面给出一个利用

lock

和

unlock 构造的临界区完成数组求和的算法[算法4.1.3]

共享存储多处理机上求和算法输入：A

=

(a0

,

a1

,…,an-1)

,

处理器数

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)：把信息用一定手段通过某种介质或传输线路从一个点传送至另一点的过程。通信是在空间上对并发执行的进程实现数据交换。原语

(primitive)：它由若干条机器指令构成的，用来完成特定功能的一段程序。原语有以下特点：不可中断性：一旦原语被开始执行，就应不间断地执行到结束；不可侵犯性：原语一旦被执行，中间不许插入任何其他操作。10/23/202320通信可使用通信原语来表示：在共享存储的多处理机中，可使用global

read

(X,

Y)将全局存储器中数据

X 读入局部变量

Y；global

write

(U,

V)将局部数据

U 写入共享存储变量

V 中。在分布存储的多计算机中，可使用send

(X,

i

)

或

send

(X,

Pi

)当前处理器发送数据

X

到

Pi

；receive

(Y,

j

)

或

receive

(Y,

Pj

)当前处理器从Pj

接收数据

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

分布存储多计算机上矩阵向量相乘算法给定:一个n*n

的矩阵A和一个向量Xa11

a12

a13……

a1n-1

a1nA

=a21

a22

a23……

a2n-1

a2na31

a32

a33……

a3n-1

a3n……..an1an2

an3……

ann-1

annx1x2X

=

x3…xn计算:

A*X，得到一个向量。假设

r

=

n/p 为一整数因为我们打算在分布存储的多计算机系统上运行该算法，被计算的数据只能分布在各个处理器的局部器上。10/2存3/20储2322我们把

A 按列分为

p

个

n*r 的小矩阵A1

,

A2

,…

,

Ap把

X 按行分为

p

个

r*1 的小向量X1

,

X2

,…

,

Xp计算

A*X就转化为计算：A1

X1

+

A2

X2

+…

Ap

Xp所以处理器Pi（其中1

≤

i

≤

p）将Ai

和 Xi

存放在自己的局部存储器中，各处理器首先计算 Ai

Xi，然后利用通信实现数据求和。X1(r*1)X2(r*1)…Xp(r*1)X

=A

=

A1

A2

…

Ap(n*r)

(n*r)

(n*r)10/23/2023

23我们假设处理器是以环结构组织的PiP2PpP110/23/202324[算法4.1.4]分布存储多计算机上矩阵向量相乘算法输入：处理器数p，第i

个A

矩阵分量Ai

于B

中，第i个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计算z=Bw计算z=Bw计算z=Bw计算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)结束10/23/2023send(y,p126)第四章 并行算法的设计基础10/23/202327一、并行算法相关的基本概念及表示二、介绍几种并行计算模型二、并行计算模型10/23/202328并行计算模型：从并行算法的设计和分析出发，将各种并行计算机（至少是某一类并行计算机）的基本特征抽象出来，形成一个抽象的计算模型。并行计算模型为并行计算提供了硬件和软件的界面，使硬件设计者和软件设计者可以开发并行性的支持机制，从而提高系统的性能。对并行算法的研制者，不会局限于某种具体的并行计算机来研究并行算法，而需借助于抽象的计算

模型，它是设计和分析并行算法的基础。编程模型计算模型体系结构模型机器模型为了能对计算机系统进行简单、明确的描述，发现一般规律，通常在不同层次上进行抽象来定义模型。不同层次模型的关系图：用户系统硬件和操作系统互连网络的作用和执行通信的形式等计算机的费用和资源编程语言的语义10/23/202329并行计算模型的主要作用：它是并行算法实现的基础对同一问题在不同的模型上的不同解决办法，来比较该问题究竟更合理在哪一种模型上实现它给并行算法设计和分析提供了一个简单、方便的框架撇开了硬件的繁杂的细节它使并行算法设计具有一定的生命力集中精力开发应用问题自身的并行性和算法的性能，并使算法具有一定的通用性10/23/202330串行算法的研究已经相当成熟，它们基本上都是基于冯.诺依曼(von

Neumann)体系结构控制器运算器主存储器输出设备输入设备CPU高速缓存10/23/202331程序指令计数器r0r1r2r3:存储器累加器x1x2……xn只读输入磁带y1y2……只写输出磁带串行计算模型RAM

(Random

Access

Machine)10/23/202332RAM机器模型的指令系统与实际计算机的指令系统类似，有四类指令：控制流向指令，

如

jump;输入/输出指令，

如

read

,

write；累加器与存储器之间的传送数据指令，如

load；算术运算指令，

如

add。10/23/2023331.

PRAM

模型10/23/202334(Parallel

Random

Access

Machine

Model)1978年S.

Fortune

和

J. Wyllie总结了阵列式结构的并行机和流水线结构的向量机的特点，将其抽象为具有如下特征的

PRAM 模型：有一个控制器有

p（可有限或无限）台功能相同的处理器有一个容量无限的共享存储器每台处理器有自己的局部存储器处于激活状态的处理器必须执行相同的指令允许任何时刻各处理器均可通过共享存储器与其它处理器交换数据。PRAM模型----SIMD计算模型控

制

器互

联

网

络全

局

共

享

存

储

器P1LM1P2LM2PpLMp……10/23/202335PRAM

模型允许任何时刻各处理器均可通过共享存储器的共享单元与其它处理器交换数据。根据处理器对共享单元的存、取访问的不同约束条件进一步对

PRAM 模型分类：–PRAM-EREW

(Exclusive

Read,

ExclusiveWrite)：不允许有读冲突和写冲突–PRAM-CREW

(Concurrent

Read,

ExclusiveWrite)：每次允许多台处理器同时读同一共享单元内容，但不允许同时写。–PRAM-CRCW

(Concurrent

Read,

ConcurrentWrite)：允许多台处理器同时读、写同一共享单元内容。10/23/202336PRAM-CRCW

模型中允许同时写同一共享单元显然是不现实的，所以对PRAM-CRCW

模型作了更进一步的约定：–共用的(Common)

PRAM-CRCW：同时写同一共享单元的所有处理器必须写相同的值；–优先的(Priority)

PRAM-CRCW：从同时要写同一共享单元的所有处理器中找出标号最小的处理器，将它的值写入共享地址中；–任意的

(Arbitrary) PRAM-CRCW：从同时要写同一共享单元的所有处理器中任选一个处理器的值写入共享地址中。10/23/202337PRAM

模型上的算法的执行：输入数据存放在全局共享存储器中，并只有一个处理器处于激活状态；在每个计算步中，一个激活的处理器可做：–从局部或全局存储器中读一个值–完成一个

RAM 操作–写值到局部或全局存储器中–激活另一个处理器10/23/202338[算法4.2.1]

在

PRAM-EREW 模型上求和算法输入：n个待求和的数

A

[0..(n-1)]输出：最终的n个数的和在

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个处理机例：n=12时间sp10a/2w3/20n23

()：激活n

个处理机的时间为⎡log

n⎤。402.

APRAM 模型

(

Asynchronous

PRAM

)10/23/20234180年代初，人们总结了共享存储型多处理机结构的向量机的特点，将其抽象为具有如下特征的APRAM 模型：有

p（可有限或无限）个处理器；每个处理器有自己的控制器（局部时钟）；有一个容量无限的共享存储器；每台处理器有自己的局部存储器和局部程序；各处理器异步地、独立地执行各自的指令，处理器间的同步需明确地在各处理器的程序中加入障碍（路障）同步

(barrier

synchronization)

指令；利用共享存储器实现处理器间的通信。APRAM

模型----MIMD计算模型控制器1互

联

网

络P1LM1P2LM2PpLMp……控制器2控制器p……全局共享存储器10/23/202342PRAM模型----SIMD计算模型（对比）控

制

器互

联

网

络P1LM1P2LM2PpLMp……全局共享存储器10/23/202343APRAM

模型同样利用共享存储器实现处理器间的通信障碍(路障)同步(barrier

synchronization)：它在程序中设置一些障碍点，当处理器执行到障碍点时暂停，等待所有进程都执行到这个障碍点上，以此方法取得同步。10/23/202344APRAM 模型中的计算

:–计算是由一系列用同步障碍点分开的全局相（global

phase）组成的。在各全局相内每个处理器异步地运行其局部程序每个局部程序中的最后一条指令是一条障碍同步指令各处理器均可异步地读取和写入全局存储器，但在同一相（phase）内不允许两个处理器访问同一共享单元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模型上设计的算法的时间复杂性包括以下几个方面：–假设一个局部操作取为

1 个单位时间–全局读/写时间为

d，它表示全局读/写的平均时间。该值应随着处理器的个数增加而增加。–同步障碍的时间为

B，B 是处理器个数

p 的非递减函数

B

(p)

。–在

APRAM 中常假设：2

≤

d

≤

B

≤

p–设 tph

为全局相内各处理器指令执行时间中最长者，则整个程序运行时间

T 应为：T

=

Σ

tph

+

B

*

同步障碍次数10/23/2023473.

Log

P

模型10/23/202348(Latency

,

overhead

,

gap

,

Processor)1993年D.Culler等人在分析了分布式存储计算机特点的基础上，提出了基于点到点通信的多计算机模型----Log

P模型。该模型虽未涉及到网络的具体结构，但充分说明了互联网络的性能特性：–互连网络带宽的限制–通信中可观的延迟它是

MPP

系统的模型Log

P 模型主要由以下4个参数来描述：

1）L(Latency)最大延迟：在通信时包含一个或几个字的一个消息从源节点传到目标节点的时间的上限值。2）o(overhead)开销：处理器准备发送或接收一个消息的时间开销，在这段时间里处理器不能执行其它操作。3）g(gap)间隔：一台处理器发送或接收一组消息时，两个消息之间的最小时间间隔，其倒数即为处理器的通信带宽。4）P(Processor)节点数：处理器/存储器个数，假定每个局部操作需要

1 个单位时间（即一个处理器周期）。10/23/202349Log

P

的参数示意图Pj处理器L

oo

gPi下一个消息消息Pk时间发送并接收一个消息共需2o+L个单位时间; 处理器

Pi 在向处理器10P/2j3/20发23

送消息后, 在发送下一个消息之前必须等待

g 个时间50单位。LogP模型的特点–处理机之间异步地工作，通过消息传递实现同步；–消息延迟不确定，但延迟不会大于L，即任何消息经历的等待时间是不可预测的，但不会超过L；–Log

P模型支持了计算和通信的重叠；–能够预测算法的实际运行时间。Log

P模型抓住了网络与处理机之间的性能瓶颈。消息间隔参数

g 反映了通信带宽，当一台处理机发送的消息已到达这个容量限度时，再发送的消息将被阻塞。10/23/202351例2：在通信模式是一棵树的情况下求和算法假设P=8、L=5、g=4、o=2，我们考虑在时间为28个单位时间内最多可能求和的个数。P0P4P6P7P2P3P5P110/23/2023524.

BSP 模型

(Bulk

Synchronous

Parallel)10/23/202353BSP 模型是一个分布存储的

MIMD

计算模型BSP

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

1）若干个能进行处理和内存操作的处理器，一个用于在处理器之间传递消息的路由器，在定义的时间间隔内，对所有处理器进行同步的机制。一般情况下，假设这个全局同步机制是用特殊的硬件支持的。一个

BSP 程序是由一系列超步

(superstep) 组成的。BSP 模型有以下三个重要参数： 1）处理器数

p路由器吞吐量

g，（也称为带宽因子）全局同步之间的时间间隔

L在一个超步中，一个处理机最多发送

h

个消息或接收

h

个消息。若有

h

个消息，则称此通信有一个h

关系(h-relation)。g

值的定义方式：–每秒处理机所能完成的局部计算数与每秒路由器所能传输的数据量之比；或–在一个10/23/2023h关系中,传递h个消息所需的时间为g.h。54BSP 模型与

APRAM 模型类似，使用障碍同步使整个计算任务以紧同步方式进行各处理器局部计算全局通信障碍同步max+

l1一0/23个/2023超步的执行时间：计算时间max

+

gh55BSP 模型的主要特点：–将处理器和路由器分开，即把计算任务和通信任务分开。路由器仅进行点到点的消息传递，不考虑互连网络的拓扑结构；–利用硬件实现全局障碍同步使并行粒度增大(相对

APRAM而言)，并能够实现紧耦合同步并行算法；–兼顾了计算和通信的平衡问题；–硬件可将L设置尽量小----这表示通信带宽会更宽些，在设计并行算法时应使L尽量大从而提高并行粒度。10/23/2023565.

C3

模型(Computing,

Communication,

Congestion)10/23/2023571994 年S.

E.

Hambrush 等人在分析高性能可扩展的网络计算机系统特点的基础上提出了

C3

模型，它适用于粗粒度的并行系统。和

BPS

与

Log

P 模型相似，

C3

计算模型也将计算划分为一系列超级步，同步出现在两个超级步之间，这个同步也是利用障碍同步机制来实现。–拥塞(Congestion)：在通信网络中，当各输入站的呼叫数量超过网络的容量，或超过了网络处理的能力时，则称网络中发生了拥塞。C3

模型主要由以下几个参数来描述：处理器的个数

p；网络延迟

h：网络中任意两节点间的距离的平均值；网络的对分宽度

b：表示网络的带宽；启动时间

s，即建立一个消息时的开销；消息包的长度

l，即消息包所含字节数。消息包是处理机间通信的基本单位。10/23/202358C3模型中用到的一些概念10/23/202359C3

模型中考虑了两种路由方式：–存储转发路由方式(store-and-forwardmode)：它是网络中信息交换的一种方式。转发中心不是将终端发出的信息立即传送到接收终端，而是先存储起来，等待适当的时机，选择空闲的信道，并按信息的优先级别转发到下一个转发中心或接收终端。–虫孔(虫蚀)路由方式(wormhole

routing

mode)：在平面网络结构的多处理机系统中进行路径选择的一种方法。它把消息分成若干个包，包又分成若干个称为迁移块(flit)的基本信息单元。每个包中的迁移块以流水线方式向前依次传送。只有包的头几个迁移块含有路径信息，因而一个包的所有迁移块必须一个跟着一个，而不能被别的消息包打断。C3

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

模型中考虑了两种发送/接收原语：

1）阻塞发送和接收原语2）非阻塞发送和接收原语阻塞发送

(blocking

send) ：指一个源处理器从开始发送一条消息，直到它被目标处理器收到消息，源处理器的发送操作才结束。非阻塞的发送

(non-blocking

send) ：源处理器只需将要发送的消息放在发送缓冲器。非阻塞的发送不需考虑目标处理器什么时候接收到信息。各种并行计算模型的比较模型属性PRAMAPRAMLog

PBSPC3体系结构SIMD-SMMIMD-SMMIMD-DMMIMD-DMMIMD-DM计算模式同步计算异步计算异步计算异步计算异步计算同步方式自动同步障碍同步隐式同步障碍同步障碍同步计算粒度细/中粒度中/大粒度中/大粒度中/大粒度粗粒度通信方式共享变量共享变量发/收消息发/收消息发/收消息模型参数10/23/20231

(单位时间步)d:全局读/写时间B:同步时间L:通信延迟

o:通信开销

g:消息间隔

P:处理器数p:处理器数

g:带宽因子

L:同步间隔l:消息包长度s:发送开销

h:通信延61迟由于并行计算机正在处于飞速发展中，但尚未定型，因此到现在为止，还没有一个通用的并行计算模型。人们只能将某一类并行机的基本特征抽象出来，形成各种特定的并行计算模型，以便并行算法的设计与理论分析。10/23/202362PRAM 模型是对一类共享的并行机特征抽取，它抛开了通信的干扰，可用于开发细粒度并行算法；Log

P 模型是对一类分布式并行计算机特征抽取，基于点对点通信的计算模型，集中分析处理机与

网络之间的瓶颈问题；C3

模型是对一类基于消息传递的分布式粗粒度系统特征抽取，集中反映的是网络拥挤和路由影响。10/23/202363例1_1：在PRAM-EREW计算机上对两个

N 维向量

A

和B 求内积

s。假设用

p 个处理机完成该任务，并设N/p 是整数，内积的值在

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