并行算法与并行程序设计第02章 并行算法

并行算法与并行程序设计课件-北京化工大学

第二章 并行算法

教师：彭四伟

并行算法与并行程序设计课件-北京化工大学

第 二 章

一、问题的并行性

并 行 算 法

把有唯一输入向量和唯一输出向量的一个程 序段在某一环境下的一次执行称为一个进程。 设有一组程序段A1…An,若{Ai}在n个处理机 上同时执行的结果等同于{Ai}以任意顺序执 行的结果，则称{Ai}为可并行执行的。

并行算法与并行程序设计课件-北京化工大学

第 二 章

一、问题的并行性

并 行 算 法

设两个程序段A、B,如果 (IA∩OB)∪(OA∩IB)∪(OA∩OB)≠Φ, 则称A和B数据相关，否则称之为数据无关。 设两个语句L1和L2,如果 L1的执行结果能够决定L2是否执行， 则称L2控制相关于L1。

并行算法与并行程序设计课件-北京化工大学

第 二 章

一、问题的并行性

并 行 算 法

设两个程序段A、B,且A先于B,若A与B数据 相关或控制相关，则称A是B的父进程。 父进程关系可以传递，称为祖先进程。记 α(A,B)为A是B的父进程，αT即祖先进程关 系。 设某一程序P中的进程集合W,于是G=(W, α)可以构成一张图，称为进程流程图。

并行算法与并行程序设计课件-北京化工大学

如下例所示：

输入输出表如下：进程 A1 A2 A3 A4 A5 A6 A7 输出 x y s t u v z 输入

第 二 章

并 行 算 法

A1:x A2:y A3:s A4:t A5:u A6:v A7:z

= = = = = = =

1 2 2*x+y x*x*y 3*s-t cos(t) u*v+1

x, x, s, t u,

y y t

v

进程关系表如下：父进程 A1 A2 A3 A4 A5 A6 A7 子进程 A3,A4 A3,A4 A5 A5,A6 A7 A7

进程流程图如下：Begin A1 A3 A5 A2 A4 A6

A7 End

并行算法与并行程序设计课件-北京化工大学

第 二 章

二、并行算法的性能指标

并 行 算 法

对问题规模n,所动用的处理器的数目p(n),运行时间或最坏运行时间 tp(n)。

粒度：并行单元的规模，通常将循环级及以下称为小粒度，子程序级称为大 粒度。 工作量Wp(n):Wp(n) = tp(n) * p(n),直观上即模拟该并行算法的串 行算法的计算量。工作量越小，算法的性能越好。如果对同一问题，并行算 法A与串行算法B的工作量同阶，称A对B工作量有效，若A对最坏情况下的最 优算法B工作量有效，称A工作量有效。 加速比Sp(n):Sp(n) = ts(n)/tp(n),其中ts(n)是解同一问题在最坏 情况下的最优串行算法的运行时间。加速比反映运行时间的改进倍数。由于 并行算法可以用串行算法来模拟，模拟的串行算法的运行时间不超过 p(n)*tp(n),所以有1≤Sp(n)≤p(n)。 工作效率Ep(n):Ep(n) = Sp(n)/p(n),反映算法所占用的处理器的工 作效率，即工作饱满程度。工作效率越高，算法的性能越好。由 1≤Sp(n)≤p(n),有1/p(n) ≤Ep(n) ≤1。

并行算法与并行程序设计课件-北京化工大学

第 二 章

三、并行求和

并 行 算 法

倍增法求和– 倍增法是并行分治的一种简化形式。其基 本思想是将原问题反复分解为等规模的两 个子问题，在逐步分解的过程中，子问题 个数成倍增加。将各个子问题恰当地映射 到各台处理机上，即可实现计算

过程的并 行化。

并行算法与并行程序设计课件-北京化工大学

第 二 章

三、并行求和

并 行 算 法

倍增法求和– 计算序列L[0..n-1]的和，记为S(0,n-1)。

S(0,7) int PSum( int L[], int s, int t ) { if (s==t) return L[s]; S(0,3) S(4,7) int k = (s+t)/2; return PSum(L, s, k)+PSum(L, k+1, t); S(0,1) S(2,3) S(4,5) S(6,7) }

并行算法与并行程序设计课件-北京化工大学

第 二 章

三、并行求和

并 行 算 法

倍减法求和– 计算序列L[0..n-1]的和，记为S(0,n-1)。– 设可用处理器为n/2个。int PSum( int L[], int n ) { k=n/2; while (k>0) { for all Pi i=0..k-1 do { L[i]+=L[i+k]; } k/=2; } return L[0]; }

并行算法与并行程序设计课件-北京化工大学

第 二 章

四、平衡树法

并 行 算 法

平衡树法的基本思想– 用一棵平衡二叉树组织并行计算，输入元 素存放在叶结点，然后逐层并行地计算一 直到根结点。

并行算法与并行程序设计课件-北京化工大学

第 二 章

四、平衡树法

并 行 算 法

以求最大值问题为例– 计算序列L[0..n-1]中的最大值。

不失一般性，设n=2m,A是一个大小为2n-1的数组， 采用完全二叉树的存储结构，将序列分别存放到n个叶 结点中，在树的同一层各结点上作并行计算，逐层递 推，直到得到最终结果。for k=m-1 to 0 do for all Pi i=0…2k-1 do j 2k-1+i; A[j] max( A[2*j+1], A[2*j+2] );

并行算法与并行程序设计课件-北京化工大学

第 二 章

四、平衡树法

并 行 算 法

平衡树法的评估– 以平衡树法求解最大值是一个EREW算法， 计算时间tp(n) = O(logn),运用处理 器最多为p(n) = n/2,工作量为 O(nlogn),不是工作量有效的算法。– 平衡树方法的优点是在树中能快速存取信 息，对数据的传递、压缩、抽取和前缀计 算均十分有用。

并行算法与并行程序设计课件-北京化工大学

第 二 章

五、向量法

并 行 算 法

向量法的基本思想– 以向量方式描述计算过程；– 以并行方式执行向量计算。

并行算法与并行程序设计课件-北京化工大学

第 二 章

五、向量法

并 行 算 法

以矩阵计算为例– 对n阶矩阵，串行加法的计算量为n2,若动用n个 (或n2个)处理器，分别处理每行(或列)的相加 运算，则可以得到计算量亦为n2,工作量有效。

并行算法与并行程序设计课件-北京化工大学

第 二 章

五、向量法

并 行 算 法

以矩阵计算为例– 矩阵相乘：C = A*B

并行算法与并行程序设计课件-北京化工大学

第 二 章

串行算法：for i=1 to n do for j=1 to n do ci,j = 0 for k=1 to n do ci,j += ai,k*bj,k

并 行 算 法

并行算法：for i=1 to n do for all Pj j=1 to n do ci,j = 0 // Ci. = 0 for k=1 to n do // Ci. = ∑ai,k * Bk. for all Pj j=1 to n do ci,j += ai,k*bk,j