文档介绍：并行算法的抽象模型
并行算法的定义和分类
并行算法的定义
算法
并行算法:一些可同时执行的诸进程的集合,这些进程互相作用和协调动作从而达到给定问题的求解。
并行算法的分类
数值计算和非数值计算
同步算法和异步算法
分布算法
确定算法和随机算法
并行算法的表达
描述语言
可以使用类Algol、类Pascal等;
在描述语言中引入并行语句。
并行语句示例
Par-do语句(Do in parallle)算法要并行执行
for i=1 to n par-do
……
end for
for all语句(几个处理器同时执行相同的操作)
for all Pi, where 0≤i≤k
……
end for
并行算法的复杂性度量
串行算法的复杂性度量
最坏情况下的复杂度(Worst-plexity)
期望复杂度(plexity)
并行算法的几个复杂性度量指标
运行时间t(n):包含计算时间和通讯时间,分别用计算时间步和选路时间步作单位。n为问题实例的输入规模。
处理器数p(n)
并行算法成本c(n): c(n)=t(n)p(n)
总运算量W(n): 并行算法求解问题时所完成的总的操作步数。
并行算法的复杂性度量
Brent定理
令W(n)是某并行算法A在运行时间T(n)内所执行的运算
量,则A使用p台处理器可在t(n)=O(W(n)/p+T(n))时间
内执行完毕。
W(n)和c(n)密切相关
P=O(W(n)/T(n))时,W(n)和c(n)两者是渐进一致的
对于任意的p,c(n)›W(n)
一个算法在运行过程中,不一定都能充分地利用有效地处理器去工作。
并行算法的同步
同步概念
同步是在时间上强使各执行进程在某一点必须互相等待;
可用软件、硬件和固件的办法来实现。
同步语句示例
共享存储多处理器上求和算法
输入:A=(a0,…,an-1),处理器数p
输出:S=Σai
Begin
(1)S=0 () lock(S)
(2)for all Pi where 0≤i≤p-1 do S=S+L
() L=0 () unlock(S)
() for j=i to n step p do end for
L=L+aj End
end for
end for
并行算法的通信
通信(使用通信原语)
共享存储多处理器使用:global read(X,Y)和global write(X,Y)
分布存储多计算机使用:send(X,i)和receive(Y,j)
通信语句示例
分布存储多计算机上矩阵向量乘算法
输入:处理器数p, A划分为B=A[1..n,(i-1)r+1..ir],
x划分为w=w[(i-1)r+1;ir]
输出:P1保存乘积AX
Begin
(1) Compute z=Bw
(2) if i=1 then yi=0 else receive(y,left) endif
(3) y=y+z
(4) send(y,right)
(5) if i=1 then receive(y,left)
End
抽象模型的概念
并行计算模型通常指从并行算法的设计和分析出发,将各种并行计算机(至少某一类并行计算机)的基本特征抽象出来,形成一个抽象的计算模型。从更广的意义上说,并行计算模型为并行计算提供了硬件和软件界面,在该界面的约定下,并行系统硬件设计者和软件设计者可以开发对并行性的支持机制,从而提高系统的性能。
并行计算机的抽象模型
并行计算机的理论模型是从物理模型抽象的;
为开发并行算法提供了一种方便的框架;
用这些模型可求得并行计算机的理论性能界限;
可在芯片制作前估算芯片区的VLSI复杂性和执行时间。
一、时间与空间复杂性
计算机求解一个规模为s的问题的算法复杂性取决于:
执行时间
存储空间