理学并行算法讲稿PPT学习教案

1、会计学1 理学并行算法讲稿理学并行算法讲稿 A1：x = 1 A2：y = 2 A3：s = 2*x+y A4：t = x*x*y A5：u = 3*s-t A6：v = cos(t) A7：z = u*v+1 如下例所示： u, vzA7 tvA6 s, tuA5 x, ytA4 x, ysA3 yA2 xA1 输入输入输出输出进程进程 输入输出表如下：输入输出表如下： Begin A1A2 A3A4 A5A6 A7 End 进程流程图如下： 第1页/共52页 第2页/共52页 那么什么叫并行算法？ 科学家已经定义为：利用并 行计算机系统进行数据与信息的 并行处理称为并行计算。 第3页/共5

2、2页 就是研究基于各种并行与分布式 计算机系统上的并行算法或分布 式算法。 第4页/共52页 率的计算方法和设计算法。在并 行算法设计中广泛采用的是 “Divide and Conquer”（分而治之） 和重新排序两种基本方法。 从以上基本方法引申具体以下几 种算法： 第5页/共52页 第6页/共52页 由自身分配；另外一种是纯结点 模式，这时所有进程都在执行单 个程序，只是少数进程（初始时 由人工指定）同时负责非计算的 功能（如I/O等）。 第7页/共52页 种方法在人工智能的搜索策略中 以及递归的“分而治之”算法中也 常使用。 第8页/共52页 同的情况。数据的分解有静态方 式和动态方式的

3、区别。静态方式 中每个进程的负载是固定的，而 在动态方式中各进程的负载分配 是随计算过程而改变的。 第9页/共52页 第10页/共52页 第11页/共52页 第12页/共52页 同步并行算法（synchronized algorithm）。是指某些进程必须等 待其他进程的一种并行算法，要求 所有进程必须在一个给定时刻同步。 SIMD以及共享存储型MIMD并行机 上通常运行同步并行算法。 第13页/共52页 包括网络在内的通信链路连接的 多结点机或计算机群协同完成某 个计算任务的算法。 第14页/共52页 理器连续传递消息的最小间隔（或 通信的带宽）、处理器个数等。由 诸如此类的参数构成各种特定

4、的并 行计算模型。常用的并行计算模型 有PRAM、VLSI、BSP、LogP和C3 模型。下面我讲述几点经典算法。 第15页/共52页 平衡树法的评估：以平衡树法求解最大值是一个 EREW算法，计算时间tp(n) = O(logn)，运用处理 器最多为p(n) = n/2，工作量为O(nlogn)，不是工作 量有效的算法。 平衡树方法的优点是在树中能快速存取信息，对数 据的传递、压缩、抽取和前缀计算均十分有用。 第16页/共52页 第17页/共52页 第18页/共52页 for i=1 to n do for all Pj j=1 to n do ci,j = 0 / Ci. = 0 for

5、k=1 to n d/ Ci. = ai,k * Bk. for all Pj j=1 to n do ci,j += ai,k*bk,j 第19页/共52页 高斯消去法高斯消去法 第20页/共52页 串行求解算法： 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 do Aij+1 = Aik*Akj+1; 第21页/共52页 并行求解算法： for( k=1; iN; i+ ) for all Pj j=kN do Akj+1 = Akk; fo

6、r( i=1; i=N; i+ ) if( i!=k ) for all Pj j=kN do Aij+1 = Aik*Akj+1; 第22页/共52页 5.4 MIMD算法 算术表达式的同步MIMD算法 例：(A+B(C+D*E*F)+G 变形为：A + G + B*C + B*D*E*F 第23页/共52页 + + * + * * * A G B C B D E F P1P2P3P4 a1=A+G P(r1) a1 += a2 P(v3) a1 += a3 a2=B*C V(r1) a3=B*D P(r2) a3 *= a4 V(r3) a4=E*F V(r2) 第24页/共52页 5.5

7、 MIMD算法 区间分割法解代数方程的根 求单调连续函数f(x)=0的根。 设已知两端lu，对区间进行n+1等分， 令y0=f(l)，yn+1=f(u)。 l u 第25页/共52页 5.5 MIMD算法 同步牛顿迭代法解代数方程的根 迭代公式： )( )( 1 i i ii xf xf xx 第26页/共52页 P0P1 while 未达到精度未达到精度 y = f(x); wait(y) x = x y/y; while 未达到精度未达到精度 wait(x) y = f(x); 并行进程如下： P0P1 y0 = f(x0)y0 = f(x0) x1 = x0 y0/y0 y1 = f(x

8、1)y1 = f(x1) x2 = x1 - y1/y1 并行计算过程如下： 第27页/共52页 5.5 MIMD算法 异步牛顿迭代法解代数方程的根 P1P2 While 未达到精度未达到精度 y = f(x); x = x y/y; While 未达到精度未达到精度 y = f(x); 第28页/共52页 5.6 流水线技术流水线技术 归并排序： 设输入长度为n=2r，用p(n)=r+1个处理器并行 完全合并排序的任务。设处理器编号从1到r+1， 其中首处理器有一个输入，尾处理器有一个输出， 其他处理器各有两个输入和两个输出。各处理器 同步运行，在一个时间步内，P1从原始输入序列 中读取一个

9、数并将其作为结果输出，Pi(i=2r+1) 接收从Pi-1输出的两个长度为2i-2的子序列，并将 其合并为一个长度为2i-1的子序列。从P1到Pr，每 一个处理器交替地在上面和下面两条输出线上产 生合并子序列。除P1外，每个处理器Pi当其前一 个处理器的一条输出线上已经产生了长为2i-2的子 序列，另一条输出线上出现了第一个元素时，就 可以开始归并了。 第29页/共52页 设Pi和Pi+1之间通过的队列为q2i和q2i+1，即q2i和q2i+1是Pi 的输出序列，Pi+1的输入序列。 如下图所示： P1 P2 P3 P4 q1 q2 q3 q4 q5 q6 q7 q8 第30页/共52页 设n

10、=2r，p(n)=r+1，算法描述如下： P1: j2; for k=1 to n do xkq1; qjxk; j = 5-j; Pi: i=2r j0; k1; while k=n do if q2(i-1)+j已装满2i-2个元素 and q2(i-1)+(1-j)已出现1个元素 then for 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个元素 then for m=1 to 2r do q2(r+1)min( q2r, q

11、2r+1 ); 第31页/共52页 十五、接力技术 基本思想 F:让两种算法接力，产生一个求解该问题的 新算法，使得既有耗时少的特性又有工作量 有效性较高的特性。 S:先用需要较少时间（速度较快）的算法求 解给定的问题，直到问题的规模减到某一个 阈值为止； L:再用工作量有效性较高的算法，继续求解， 直到获得最终的解答。 第32页/共52页 5.85.8接力技术接力技术 求解最大值的常数时间算法 对n个元素的数组，可以动用n2个处理器，在 O(1)的时间内求解出最大值。 A1A2A3m A1?F?F A2TTTT A3?F?F for all Pfor all Pi i i=1n do i=1

12、n do mi mi true;true; for all Pfor all Pi,j i,j i=1n, j=1n do i=1n, j=1n do if (AiAj) mi if (AiAj) mi false;false; for all Pi i=1n dofor all Pi i=1n do if (mi=true) max if (mi=true) max Ai;Ai; 第33页/共52页 216个叶子 根 28个结点，每个分28个叶结点 28*24个结点，每个分24个叶结点 28*24*22个结点，每个分22个叶结点 28*24*22*2个结点，每个分2个叶结点 第34页/共52

13、页 十五、接力技术 求解最大值的重对数时间算法 设n个元素的 序列 ，定义一棵以n个元素为叶结点 的重对数深度平衡树如下： 树中每一个非叶子结点u的子结点的个数为以u为根的子 树上的叶结点的个数的平方根。则第0层为树根，有一个 结点，第1层为n1/2个结点，每个结点为根的 子树上有 n/n1/2= n1/2个叶子，所以每个结点有n1/4个子结点，可以 证明，以第i层上每一个结点为根的子树上有 个叶子结 点，第i层上 共有 个结点，可知这样一棵树的高度为loglogn+1 ，因此称为重对数深度平衡树。 在重对数深度平衡树上，除第0层外，对每一层按父结点 分组，对每一组用常数时间算法求解最大值，结

14、果放在 其父结点中。可证明，共须n个处理器，经过loglogn+1个 并行步完成计算，时间复杂度为O(loglogn)。 k n 2 2 i n 2 1 i i n n n 2 1 1 2 1 第35页/共52页 5.5 、流水线技术 排序问题 每个进程一次从前一个进程接收待排序序 列中的一个数，保存当前接受到的最大的 数字，把比这个数小的其他数传给下一个 进程。 第一个进程P0直接从待排序序列接收数据。 P P0 0P P1 1P P2 2P P3 3P P4 44|3|1|2|54|3|1|2|5 1 12 23 34 45 5 第36页/共52页 P P0 0P P1 1P P2 2P

15、P3 3P P4 4 - - - - - -4|3|1|2|54|3|1|2|5 5 5- - - - -4|3|1|24|3|1|2 5 5- - - - -4|3|14|3|1 2 2 5 52 2- - - -4|34|3 1 1 5 52 2- - - -4 4 3 31 1 5 53 31 1- - - 4 42 2 5 54 42 2- - - 3 31 1 5 54 43 31 1- - 2 2 5 54 43 32 21 1 第37页/共52页 十四、流水线技术十四、流水线技术 质数生成问题 顺序解法 for (i=2; i=n; i+)for (i=2; i=n; i+) p

16、rimei = 1;primei = 1; for (i=0; i=sqrt_n; i+)for (i=0; i=sqrt_n; i+) if (primei=1)if (primei=1) for (j=ifor (j=i* *i; j=n; j+=i)i; j=n; j+=i) primej = 0;primej = 0; 第38页/共52页 质数生成问题流水线解法： 第一个流水线级输入一系列连续的数，然后剔出所有2的 倍数，并把余下的数传递给第二级流水线；第二级剔出所 有3的倍数并把余下的数传递给第三级流水线；以此类推 ；流水线的个数与质数的个数的方根相同； 十四、流水线技术 第39页/

17、共52页 十五、接力技术十五、接力技术 对数深度树和重对数深度树算法接力 第一步，利用对数深度平衡树方法向上逐层进行计 算，经过logloglogn层的选拔后停下来。 第二步，以第一步选拔出的最大值候选结点为叶结 点，按重对数时间算法进行继续计算，直到所求的 解。 第一步所需时间为O(logloglogn)，工作量为 O(nlogloglogn)，在第一步结束时，剩下的结点数为 ：n=n/2logloglogn=n/loglogn。则第二步需要的时间 为O(loglogn)=O(loglogn)，工作量为 O(nloglogn)=O(n)。从而进一步提高了工作量的有 效性。 第40页/共52页

18、 十二、并行分治十二、并行分治 分治 通过将一个问题分解成若干个性质相同的子问题，并递 归地对子问题进行求解，然后将各子问题的解加以合并 构造出原问题的解。 分治步骤 将问题的输入进行均匀划分，构成规模大致相等的若干 个同类的子问题； 递归求解各子问题； 将各子问题的解归并成为原问题的解； 第41页/共52页 十二、并行分治十二、并行分治 并行分治: F(I) if 输入足够小 then O Answer( I ); else 分解输入：I1, Ik； for all Pi i=1k do Oi F( Ii, Oi ); O Combine( O1,Ok ); 第42页/共52页 十二、并行分

19、治 最近点对问题 d1d2 d 2d 第43页/共52页 十三、划分法 划分法 与分治法相似，划分原理也是将原问题进行分解，分别求解 ，再归并子问题的解。 所不同的是，分治法采用简单的分解方法，因此设计的难点 在于如何归并子问题的解，而划分方法则讲究分解的方法， 以获得简单的归并策略。 有序序列归并: 设A=(a1, a2, , an)， B=(b1, b2, , bm)， 是U上的单调增序列，且AB=。 将A和B归并到： C=(c1, c2, , cm+n)。 第44页/共52页 十三、划分法 有序序列归并 定义：对U上的有序序列列X=(x1,x2,xt)，xU，x在X上 的位序rank(x

20、: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)工作量完成合并的 任务。 但这样的解法不是一个工作量有效的算法。通过进一步划 分，可以得到工作量有效的解法。 第45页/共52页 十三、划分法 有序序列归并 定义：对U上的有序序列列X=(x1,x2,xt)，xU，x在X上的 位序rank(x:X)为X中小于等于x的元素个数。 归并问题即求rank(x:AB)，xAB。 分别求出rank(

21、ai:B)和rank(bj:A)，即可得到 rank(x:AB)=rank(x:A) + rank(x:B)。 这样就可以在O(logn)时间内用O(nlogn)工作量完成合并的任 务。 但这样的解法不是一个工作量有效的算法。通过进一步划分 ，可以得到工作量有效的解法。 第46页/共52页 十七、确定性破对称技术 基本概念 破对称：打破并行操作的对称性，即避免两个处理器同时 被分派对同一个单元进行处理或同时不被分派进行处理。 前面的随机消元中的抛硬币方法就是一种不确定的破对称 技术。 确定性破对称技术：利用处理器的编号来打破对称性。例 如前面的例子中，通过让下标较小的处理器先访问来打破 对称性。 第47页/共52页 十七、确定性破对称技术 确定性破对称算法 要求从静态链表中选出一部分元素，这部分元素在链表中 两两不相邻，且数目是链表中元素总数的常分数倍。 n个处理器和O(log*n)的计算时间，其中log*n定义为： log*x = min i | log(i)x=0 ; log(i)x定义为