授课人董国荣方小平指导老师秦刚.ppt

授课人董国荣方小平指导老师秦刚 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望一一.并行算法的提出并行算法的提出把有唯一输入向量和唯一输出向量的一个程序段在某一环境下的一次执行称为一个进程。设有一组程序段A1An，若Ai在n个处理机上同时执行的结果等同于Ai以任意顺序执行的结果，则称Ai为可并行执行的。设两个程序段A、B，且A先于B，若A与B数据相关或控制相关，则称A是B的父进程。由此 图示可以明确看出并行处理关系！A1：x=1A2：y=2A3：s=2*x+yA4：t=x*x*yA5：u=3*s-tA6：v=cos(t)A7：z=u*v+1如下例所示：u,vzA7tvA6s,tuA5x,ytA4x,ysA3yA2xA1输入输入输出输出进程进程输入输出表如下：输入输出表如下：BeginA1A2A3A4A5A6A7End进程流程图如下：一一.并行算法的提出并行算法的提出下面简单例子让我们能更深刻理解并行算法：倍增法求和倍增法是并行分治的一种简化形式。其基本思想是将原问题反复分解为等规模的两个子问题，在逐步分解的过程中，子问题个数成倍增加。将各个子问题恰当地映射到各台处理机上，即可实现计算过程的并行化。例如:倍增法求和 计算序列L0.n-1的和，记为S(0,n-1)。int BSum(int L,int s,int t)if(s=t)return Ls;int k=(s+t)/2;return BSum(L,s,k)+BSum(L,k+1,t);并行求和一一.并行算法的提出并行算法的提出 从以上一个简单的例子我们可以看到并行算法的真谛！所以这么说基于普通的算法大家开始加，串行从1到100加很累，而这个高斯思想的并行处理结果又快又准确！体现出了这个思想，由此引申到计算机并行处理可以看出它潜力巨大，对解决现实问题有很大的指导作用，希望大家认真听讲。那么什么叫并行算法？科学家已经定义为：利用并行计算机系统进行数据与信息的并行处理称为并行计算。二二.并行算法的提出并行算法的提出 并行计算研究的内容包括并行计算方法、并行计算模型、并行算法、并行程序设计、并行测试程序设计、测试结果分析等。由于各种并行计算机的系统结构不同，系统内各处理器和各功能部件之间在体现算法时的相互作用不同，使得并行算法不能通用。因此，当前并行处理的研究重点，除了并行计算机体系结构之外，就是研究基于各种并行与分布式计算机系统上的并行算法或分布式算法。二二.并行算法基本方法并行算法基本方法 并行计算方法的研究，不仅对提高并行计算机的使用效率是必需的，而且往往能找到改进现有串行算法的新途径。并行计算方法的研究是研制高效并行数值计算软件的基础。并行计算中可供选择的技术路线有两条：一条是在现有的串行算法基础上作并行化；另一条是直接从数学物理问题出发，面向并行系统研制高效率的计算方法和设计算法。在并行算法设计中广泛采用的是“Divide and Conquer”（分而治之）和重新排序两种基本方法。从以上基本方法引申具体以下几种算法：三、并行编程的基本方法三、并行编程的基本方法 这里主要介绍网络并行编程的基本模式和负载平衡的基本方法。(1)网络并行编程的基本模式 应用标准化环境进行网络并行编程与MPP并行机（如IBM SPZ，Intel Paragon等）在算法设计和编程逻辑的基本方法上是相同的，它们存在的不同点是：任务管理方式不同，网络并行标准化环境编程要涉及到进程的动态创建与命名。标准环境不同，网络并行编程要求在正式计算前完成语句的初始化。粒度选取不同，分布式网络并行计算的并行粒度较大。计算环境不同，分布式网络并行计算要考虑到异构环境。从不同计算任务组织的角度看，分布式编程主要有星形计算模式和树形计算模式两种：三、并行编程的基本方法三、并行编程的基本方法 星形计算模式。由一组相互紧密关联的进程组成，它们可以是执行相同的程序，只是数据不同，共同执行同一计算问题的不同部位。这种计算模式又可以分为两类：一种是主从式（master slave），这种计算模式有一个控制程序作为主进程，负责进程的生成、初始化、收集并显示结果，其余的进程（slave）执行实际计算，从进程的负载或由主进程分配，或由自身分配；另外一种是纯结点模式，这时所有进程都在执行单个程序，只是少数进程（初始时由人工指定）同时负责非计算的功能（如I/O等）。三、并行编程的基本方法三、并行编程的基本方法 树形（树形（tree）计算模式）计算模式。在这种计算模式中，进程通常是在计算过程中以树形方式动态生成。在求解组合优化问题时常用的一种算法是构造性的探索算法，主要思想是对解集合反复进行分支，对每个分支计算最优解的界。如果该解符合要求，则继续分支以探索更好的解，直到所有的子集合中仅有一个最优的解为止。这种方法在人工智能的搜索策略中以及递归的“分而治之”算法中也常使用。三、并行编程的基本方法三、并行编程的基本方法 (2)负载平衡的基本方法 各处理器之间的负载是否能做到基本平衡，是并行计算效率能否提高的一个关键。对于网络分布式并行计算而言，负载平衡的基本方法有两个：数据分解与功能分解。数据分解方法，有时也称数据分割法，这种方法适应于各处理器执行相同的任务、只是数据不同的情况。数据的分解有静态方式和动态方式的区别。静态方式中每个进程的负载是固定的，而在动态方式中各进程的负载分配是随计算过程而改变的。三、并行编程的基本方法三、并行编程的基本方法 功能分解方法。网络计算的并行化也可通过把总负载按功能进行分解，分配给各个处理器承担。最简单的是把整个计算过程分为输入数据、计算进程和输出结果三个部分。当然根据实际情况这三个部分又可以再进行细分。三三.并行计算基本概念并行计算基本概念(1)并行算法的目标 并行算法的目标就是以增加空间的复杂性来减少时间的复杂性，即增加空间的维数，增加处理器的台数，来减少算法实现所需的时间。从算法的结构观察，通常的串行算法树“深而窄”，而并行算法树结构截然不同。为达到把时间的复杂性转化为空间复杂性的目的，并行算法树采用了“浅而宽”的结构。(2)并行加速比 并行加速比表示采用多个处理器计算速度所能达到的加速的倍数。(3)粒度（granularity）三三.并行计算基本概念并行计算基本概念 粒度是各个多处理机可独立并行执行的任务大小的度量。大粒度反映可并行执行的运算量与程序量大，有时称粗粒度。任务级并行的粒度大于语句级的并行。向量机主要是对内层Do循环语句作向量化，所以向量化是一种小粒度（细粒度）并行；在网络并行计算中，由于通信开销比较大，应尽量采用粗粒度方式。(4)可扩展性（Scalability）可扩展性是指并行机和并行算法有效利用多处理机台数增加的能力的一个度量。随着处理机的增加，如果效率曲线基本保持不变，或略有下降，则认为该算法在所用的并行机上扩展性好；否则，其可扩展性差。影响一个并行算法的扩展性因素较多，评判的准则也不尽相同。四四.并行算法分类并行算法分类 依据处理对象划分，并行算法可分为两类：数值并行算法 主要为数值计算而设计的并行算法；非数值并行算法 如神经网络算法、演化算法、遗传算法、格子气算法、格子 依据算法中进程的控制方式划分，可分为以下两种：ltzmann算法以及为符号计算而设计的并行算法。同步并行算法（synchronized algorithm）。是指某些进程必须等待其他进程的一种并行算法，要求所有进程必须在一个给定时刻同步。SIMD以及共享存储型MIMD并行机上通常运行同步并行算法。四四.并行算法分类并行算法分类 异步并行算法（asynchronized algorithm），是指诸进程执行相对独立、不要互相等待的一类算法。其主要特征是在计算的整个过程中都不需要等待，而是根据当前的最新信息决定进程的继续或终止。这种算法通常是针对分布式存储的MIMD并行机设计的。另外，还有分布式算法（distributed algorithm），是指由包括网络在内的通信链路连接的多结点机或计算机群协同完成某个计算任务的算法。五五.并行计算模型并行计算模型 所谓计算模型，是算法设计者进行理论分析时所依据的计算机模型。冯诺依曼机是理想的串行计算模型。由于并行机在飞速发展之中，尚未定型，故目前尚没有所谓的通用并行计算模型。当前，人们将并行计算机的某一些特征抽象出来，形成了各种特定的并行计算理论模型，以便于并行算法的设计与理论分析。并行机的特征有：消息包的长度或延迟时间、消息包传递的开销、处理器连续传递消息的最小间隔（或通信的带宽）、处理器个数等。由诸如此类的参数构成各种特定的并行计算模型。常用的并行计算模型有PRAM、VLSI、BSP、LogP和C3模型。下面我讲述几点经典算法。5.1 平衡树法 平衡树法的评估：以平衡树法求解最大值是一个EREW算法，计算时间tp(n)=O(logn)，运用处理器最多为p(n)=n/2，工作量为O(nlogn)，不是工作量有效的算法。平衡树方法的优点是在树中能快速存取信息，对数据的传递、压缩、抽取和前缀计算均十分有用。5.2 向量法 向量法的基本思想 以向量方式描述计算过程；以并行方式执行向量计算。以矩阵计算为例 对n阶矩阵，串行加法的计算量为n2，若动用n个（或n2个）处理器，分别处理每行（或列）的相加运算，则可以得到计算量亦为n2，工作量有效。5.2 向量法以矩阵计算为例矩阵相乘：C=A*B5.2 向量法串行算法：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 dofor all Pj j=1 to n do ci,j=0/Ci.=0for k=1 to n d/Ci.=ai,k*Bk.for all Pj j=1 to n do ci,j+=ai,k*bk,j5.3 线性代数方程组法高斯消去法高斯消去法 串行求解算法：for(k=1;iN;i+)for all Pj j=kN do Akj+1=Akk;for(i=1;i=N;i+)if(i!=k)for all Pj j=kN doAij+1=Aik*Akj+1;并行求解算法：for(k=1;iN;i+)for all Pj j=kN do Akj+1=Akk;for(i=1;i=N;i+)if(i!=k)for all Pj j=kN doAij+1=Aik*Akj+1;5.4 MIMD算法算术表达式的同步MIMD算法例：(A+B(C+D*E*F)+G变形为：A+G+B*C+B*D*E*FP1P2P3P4a1=A+GP(r1)a1+=a2P(v3)a1+=a3a2=B*CV(r1)a3=B*DP(r2)a3*=a4V(r3)a4=E*FV(r2)5.5 MIMD算法 区间分割法解代数方程的根 求单调连续函数f(x)=0的根。设已知两端lu，对区间进行n+1等分，令y0=f(l)，yn+1=f(u)。5.5 MIMD算法同步牛顿迭代法解代数方程的根迭代公式：P0P1while 未达到精度未达到精度y=f(x);wait(y)x=x y/y;while 未达到精度未达到精度wait(x)y=f(x);并行进程如下：P0P1y0=f(x0)y0=f(x0)x1=x0 y0/y0y1=f(x1)y1=f(x1)x2=x1-y1/y1并行计算过程如下：5.5 MIMD算法异步牛顿迭代法解代数方程的根P1P2While 未达到精度未达到精度y=f(x);x=x y/y;While 未达到精度未达到精度y=f(x);5.6 流水线技术流水线技术 归并排序：设输入长度为n=2r，用p(n)=r+1个处理器并行完全合并排序的任务。设处理器编号从1到r+1，其中首处理器有一个输入，尾处理器有一个输出，其他处理器各有两个输入和两个输出。各处理器同步运行，在一个时间步内，P1从原始输入序列中读取一个数并将其作为结果输出，Pi(i=2r+1)接收从Pi-1输出的两个长度为2i-2的子序列，并将其合并为一个长度为2i-1的子序列。从P1到Pr，每一个处理器交替地在上面和下面两条输出线上产生合并子序列。除P1外，每个处理器Pi当其前一个处理器的一条输出线上已经产生了长为2i-2的子序列，另一条输出线上出现了第一个元素时，就可以开始归并了。设Pi和Pi+1之间通过的队列为q2i和q2i+1，即q2i和q2i+1是Pi的输出序列，Pi+1的输入序列。如下图所示：设n=2r，p(n)=r+1，算法描述如下：P1:j2;for k=1 to n doxkq1;qjxk;j=5-j;Pi:i=2rj0;k1;while k=n doif q2(i-1)+j已装满2i-2个元素 and q2(i-1)+(1-j)已出现1个元素 thenfor m=1 to 2i-1 do q2i+jmin(q2(i-1)+j,q2(i-1)+(1-j);j1-j;kk+2i-1;Pr+1:if q2r已装满2r-1个元素，且q2r+1已出现1个元素 thenfor m=1 to 2r doq2(r+1)min(q2r,q2r+1);十五、接力技术基本思想F:让两种算法接力，产生一个求解该问题的新算法，使得既有耗时少的特性又有工作量有效性较高的特性。S:先用需要较少时间（速度较快）的算法求解给定的问题，直到问题的规模减到某一个阈值为止；L:再用工作量有效性较高的算法，继续求解，直到获得最终的解答。5.85.8接力技术接力技术求解最大值的常数时间算法对n个元素的数组，可以动用n2个处理器，在O(1)的时间内求解出最大值。A1A2A3mA1?F?FA2TTTTA3?F?Ffor all Pi i=1n do mi true;for all Pi,j i=1n,j=1n doif(AiAj)mi false;for all Pi i=1n doif(mi=true)max Ai;216个叶子根28个结点，每个分28个叶结点28*24个结点，每个分24个叶结点28*24*22个结点，每个分22个叶结点28*24*22*2个结点，每个分2个叶结点十五、接力技术求解最大值的重对数时间算法设n个元素的 序列 ，定义一棵以n个元素为叶结点的重对数深度平衡树如下：树中每一个非叶子结点u的子结点的个数为以u为根的子树上的叶结点的个数的平方根。则第0层为树根，有一个结点，第1层为n1/2个结点，每个结点为根的 子树上有n/n1/2=n1/2个叶子，所以每个结点有n1/4个子结点，可以证明，以第i层上每一个结点为根的子树上有 个叶子结点，第i层上共有 个结点，可知这样一棵树的高度为loglogn+1，因此称为重对数深度平衡树。在重对数深度平衡树上，除第0层外，对每一层按父结点分组，对每一组用常数时间算法求解最大值，结果放在其父结点中。可证明，共须n个处理器，经过loglogn+1个并行步完成计算，时间复杂度为O(loglogn)。5.5、流水线技术排序问题每个进程一次从前一个进程接收待排序序列中的一个数，保存当前接受到的最大的数字，把比这个数小的其他数传给下一个进程。第一个进程P0直接从待排序序列接收数据。P0P1P2P3P44|3|1|2|512345P0P1P2P3P4-4|3|1|2|55-4|3|1|25-4|3|1252-4|3152-431531-42542-315431-254321 十四、流水线技术十四、流水线技术质数生成问题顺序解法for(i=2;i=n;i+)primei=1;for(i=0;i=sqrt_n;i+)if(primei=1)for(j=i*i;j=n;j+=i)primej=0;质数生成问题流水线解法：第一个流水线级输入一系列连续的数，然后剔出所有2的倍数，并把余下的数传递给第二级流水线；第二级剔出所有3的倍数并把余下的数传递给第三级流水线；以此类推；流水线的个数与质数的个数的方根相同；十四、流水线技术十五、接力技术十五、接力技术对数深度树和重对数深度树算法接力第一步，利用对数深度平衡树方法向上逐层进行计算，经过logloglogn层的选拔后停下来。第二步，以第一步选拔出的最大值候选结点为叶结点，按重对数时间算法进行继续计算，直到所求的解。第一步所需时间为O(logloglogn)，工作量为O(nlogloglogn)，在第一步结束时，剩下的结点数为：n=n/2logloglogn=n/loglogn。则第二步需要的时间为O(loglogn)=O(loglogn)，工作量为O(nloglogn)=O(n)。从而进一步提高了工作量的有效性。十二、并行分治十二、并行分治分治通过将一个问题分解成若干个性质相同的子问题，并递归地对子问题进行求解，然后将各子问题的解加以合并构造出原问题的解。分治步骤将问题的输入进行均匀划分，构成规模大致相等的若干个同类的子问题；递归求解各子问题；将各子问题的解归并成为原问题的解；十二、并行分治十二、并行分治并行分治:F(I)if 输入足够小 then O Answer(I);else分解输入：I1,Ik；for all Pi i=1k doOi F(Ii,Oi);O Combine(O1,Ok);十二、并行分治最近点对问题d1d2d2d十三、划分法划分法与分治法相似，划分原理也是将原问题进行分解，分别求解，再归并子问题的解。所不同的是，分治法采用简单的分解方法，因此设计的难点在于如何归并子问题的解，而划分方法则讲究分解的方法，以获得简单的归并策略。有序序列归并:设A=(a1,a2,an)，B=(b1,b2,bm)，是U上的单调增序列，且AB=。将A和B归并到：C=(c1,c2,cm+n)。十三、划分法有序序列归并定义：对U上的有序序列列X=(x1,x2,xt)，xU，x在X上的位序rank(x:X)为X中小于等于x的元素个数。归并问题即求rank(x:AB)，xAB。分别求出rank(ai:B)和rank(bj:A)，即可得到rank(x:AB)=rank(x:A)+rank(x:B)。这样就可以在O(logn)时间内用O(nlogn)工作量完成合并的任务。但这样的解法不是一个工作量有效的算法。通过进一步划分，可以得到工作量有效的解法。十三、划分法有序序列归并定义：对U上的有序序列列X=(x1,x2,xt)，xU，x在X上的位序rank(x:X)为X中小于等于x的元素个数。归并问题即求rank(x:AB)，xAB。分别求出rank(ai:B)和rank(bj:A)，即可得到rank(x:AB)=rank(x:A)+rank(x:B)。这样就可以在O(logn)时间内用O(nlogn)工作量完成合并的任务。但这样的解法不是一个工作量有效的算法。通过进一步划分，可以得到工作量有效的解法。十七、确定性破对称技术基本概念破对称：打破并行操作的对称性，即避免两个处理器同时被分派对同一个单元进行处理或同时不被分派进行处理。前面的随机消元中的抛硬币方法就是一种不确定的破对称技术。确定性破对称技术：利用处理器的编号来打破对称性。例如前面的例子中，通过让下标较小的处理器先访问来打破对称性。十七、确定性破对称技术确定性破对称算法要求从静态链表中选出一部分元素，这部分元素在链表中两两不相邻，且数目是链表中元素总数的常分数倍。n个处理器和O(log*n)的计算时间，其中log*n定义为：log*x=min i|log(i)x=0;log(i)x定义为：对1n265536，有0log*n5，因此对一般的实际应用，log*n是一个小常数。十七、确定性破对称技术无向图着色与极大独立集无向图G=(V,E)的一个着色是一个映射：，使得对所有u,v，如果(u)=C(v)，则(u,v)不属于，即相邻点不同色。在链表上进行-着色，可用的颜色号为0,1,2,3,4,5，且相邻元素不同色。虽然可以用O(logn)的时间并行地对链表进行2-着色，将奇、偶元素分别着以不同的颜色，但通常只要有一种O(1)的着色就可以了。下面的算法在O(log*n)的时间对n个元素的链表进行6-着色。十七、确定性破对称技术无向图着色与极大独立集G=(V,E)的一个独立集是其顶点集V的一个子集V，使得E中的每条边最多只与V中的一个顶点相关联。极大独立集是一个不能再并入其他任何顶点的独立集。最大独立集是图G的一个规模最大的独立集。求极大独立集是一个易解的问题，求最大独立集却是一个NP-完全问题。虽然对一个链表可以通过O(logn)时间分别标出奇偶点，从而得到两个最大独立集，但速度不够快。而只要我们能求得链表的极大独立集，则可知极大独立集中的元素个数不小于n/3（每三个元素中，至少有一个元素属于极大独立集）。我的讲课完了，我的讲课完了，不足之处希望大不足之处希望大家提出批评建议！家提出批评建议！