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

第四章 并行算法的设计基础;一、并行算法相关的基本概念及表示;1. 基本概念;根据算法的不同特征，可以对并行算法进行不同的分类：;定义3：同步算法(synchronizedalgorithm):是指算法的诸进程的执行必须相互等待的一类并行算法。SIMD算法是同步算法中的一种特例。

定义4：异步算法(asynchronousalgorithm):是指算法的诸进程的执行不必相互等待的一类并行算法。

定义5：分布并行算法(distributedalgorithm)：将同一任务分解为若干个子任务，使之分布在由通信链路连接的多个节点上协同完成运算的算法。

分布式算法的执行时间，在很大程度上受通信开销的影响。;定义6：确定算法 (deterministic algorithm)：每个运算步骤上均确定唯一操作的算法。如线性方程组求解的算法。

不确定算法(non-deterministicalgorithm)：在问题求解的搜索过程中，提出多种可供选择的操作，它们中的任一种都有希望获得问题的解答，但都不能肯定解出，有时甚至不能确定这些操作中哪一种求解的可能性更大些。对此，只能选择其中任意一种搜索下去。这种搜索方法称为不确定算法。;定义7：随机算法( randomized algorithm,probabilistic algorithm )计算步骤具有随机性的算法。在算法的某一步或某些步上，可以在指定范围内随机地选择下一个演算步的走向。;表示算法的要求

无二义性

力图直观、易懂

不苛求严格的语法格式

一般的串行算法常用类Pascal、类Algol表示;;3. 并行算法的复杂性度量;定义10：如果存在正数 c1、c2 和 n0，使得对于所有的 n ≥ n0均有c1g(n) ≤ f(n) ≤ c2g(n) ，

则标记为;比较两个算法的时间复杂性函数g(n)和f(n)的阶的方法：;并行算法的运行时间 t(n) ：对于输入规模为 n的问题，在给定的并行计算模型之下求解问题所需

的时间，也称为时间复杂性 ( time complexity )。

运行时间 = 计算时间 + 通信时间

处理器数p(n)：表示对给定的问题规模 n，并行算法所用的处理器的个数。

并行算法的成本c(n)：并行算法的运行时间 t(n)与所需的处理器数 p(n) 之积，即

c(n) = t(n) * p(n);例:(1)设f(n)=n2/2,g(n)=307n2，则;定义11：一个并行算法最坏情况下的时间复杂性(worst-case time-complexity ) ：对于所有输??规模为 n 的问题，在给定的并行计算模型之下求解问题所需的时间的最大值。

定义12：一个并行算法的期望时间复杂性(expected time-complexity ) ：对于所有输入规模为 n 的问题，在给定的计算模型之下求解问题所需的时间的平均值。;定义13：一个并行算法最坏情况下的空间复杂性(worst-case space-complexity) ：对于所有输入规模为 n 的问题，在给定的并行计算模型之下求解问题所需的内存空间的最大值。

定义14：一个并行算法的期望空间复杂性(expectedspace-complexity) ：对于所有输入规模为 n 的问题，在给定的计算模型之下求解问题所需的内存空间的平均值。;定义15：如果一个并行算法的成本与其对应的最佳串行算法的最坏情况下时间复杂性在同一个数量级上，则称该并行算法为成本最佳的( cost-optimal ) 或最佳并行算法 (optimal parallelalgorithm )。

总运算量W (n): (并行)算法中所要完成的总的操作数量( the number of computationaloperations );4. 并行算法中的同步与通信;[算法4.1.3] 共享存储多处理机上求和算法输入：A=(a0,a1,…,an-1),处理器数p；

输出：a0+a1+…+an-1存放在全局变量S中。

begin

S=0

forallPiwhere0?i?p-1doL=0

forj=iton-1steppdo

L=L+ajendfor

lock(u)

S=S+L

unlock(u)endfor;通信(communication)：把信息用一定手段通过某种介质或传输线路从一个点传送至另一点的过程。

通信是在空间上对并发执行的进程实现数据交换。

原语 (primitive)：它由若干条机器指令构成的，用来完成特定功能的一段程序。原语有以下特点：

不可中断性：一旦原语被开始执行，就应不间断地执行到