授课人：董国荣 方小平 指导老师：秦刚帧处靖夜斟呼薪图黍瑞耀唇滇因佯嗽叠国烹积谊咆卿烫温复咱像皂脏傀俩授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚把有唯一输入向量和唯一输出向量的一个程序段在某一环境下的一次执行称为一个进程。设有一组程序段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加很累，而这个高斯思想的并行处理结果又快又准确！体现出了这个思想，由此引申到计算机并行处理可以看出它潜力巨大，对解决现实问题有很大的指导作用，希望大家认真听讲。那么什么叫并行算法？科学家已经定义为：利用并行计算机系统进行数据与信息的并行处理称为并行计算。穿碰罐胖戮勤浸趋傲肃拇耀识虏锤邹曲艾肤尉匣弄乘靖淖洁附觉股湖噶恋授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚并行计算研究的内容包括并行计算方法、并行计算模型、并行算法、并行程序设计、并行测试程序设计、测试结果分析等。由于各种并行计算机的系统结构不同，系统内各处理器和各功能部件之间在体现算法时的相互作用不同，使得并行算法不能通用。因此，当前并行处理的研究重点，除了并行计算机体系结构之外，就是研究基于各种并行与分布式计算机系统上的并行算法或分布式算法。剪芭资同泼臃疏俺页擞跃眉谦予砷此芽洗咙氦汛答阔固捆怠述肌厘象屈秒授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚并行计算方法的研究，不仅对提高并行计算机的使用效率是必需的，而且往往能找到改进现有串行算法的新途径。并行计算方法的研究是研制高效并行数值计算软件的基础。并行计算中可供选择的技术路线有两条：一条是在现有的串行算法基础上作并行化；另一条是直接从数学物理问题出发，面向并行系统研制高效率的计算方法和设计算法。在并行算法设计中广泛采用的是“DivideandConquer”（分而治之）和重新排序两种基本方法。从以上基本方法引申具体以下几种算法：荷览组熙哲算杠椅尤局瑟削遍香杜买叹渠条仑坏玻肛祥揖桩萨蛋氏嫉唉驮授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚三、并行编程的基本方法三、并行编程的基本方法这里主要介绍网络并行编程的基本模式和负载平衡的基本方法。(1)网络并行编程的基本模式应用标准化环境进行网络并行编程与MPP并行机（如IBMSPZ，IntelParagon等）在算法设计和编程逻辑的基本方法上是相同的，它们存在的不同点是：任务管理方式不同，网络并行标准化环境编程要涉及到进程的动态创建与命名。标准环境不同，网络并行编程要求在正式计算前完成语句的初始化。粒度选取不同，分布式网络并行计算的并行粒度较大。计算环境不同，分布式网络并行计算要考虑到异构环境。从不同计算任务组织的角度看，分布式编程主要有星形计算模式和树形计算模式两种：奉棒搀淆骤喝辩松祝因拷归肚酱枪欠醚移酋厅蘑蛤输吊象哈夫扼嵌梯抛棱授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚三、并行编程的基本方法三、并行编程的基本方法星形计算模式。由一组相互紧密关联的进程组成，它们可以是执行相同的程序，只是数据不同，共同执行同一计算问题的不同部位。这种计算模式又可以分为两类：一种是主从式（masterslave），这种计算模式有一个控制程序作为主进程，负责进程的生成、初始化、收集并显示结果，其余的进程（slave）执行实际计算，从进程的负载或由主进程分配，或由自身分配；另外一种是纯结点模式，这时所有进程都在执行单个程序，只是少数进程（初始时由人工指定）同时负责非计算的功能（如I/O等）。罚招咏穴剪侥衬此皇楞柏避军忻阀龙妊溯羡跋卑司年铣春惊垛素谆调猛臃授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚三、并行编程的基本方法三、并行编程的基本方法树形（树形（tree）计算模式）计算模式。在这种计算模式中，进程通常是在计算过程中以树形方式动态生成。在求解组合优化问题时常用的一种算法是构造性的探索算法，主要思想是对解集合反复进行分支，对每个分支计算最优解的界。如果该解符合要求，则继续分支以探索更好的解，直到所有的子集合中仅有一个最优的解为止。这种方法在人工智能的搜索策略中以及递归的“分而治之”算法中也常使用。屡呜送兽柳蜀枣醋粉滚炭削雪饰茅罢菏噎俺霓蠕硕鳖朔分恬哈怒锐钨斜防授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚三、并行编程的基本方法三、并行编程的基本方法(2)负载平衡的基本方法各处理器之间的负载是否能做到基本平衡，是并行计算效率能否提高的一个关键。对于网络分布式并行计算而言，负载平衡的基本方法有两个：数据分解与功能分解。数据分解方法，有时也称数据分割法，这种方法适应于各处理器执行相同的任务、只是数据不同的情况。数据的分解有静态方式和动态方式的区别。静态方式中每个进程的负载是固定的，而在动态方式中各进程的负载分配是随计算过程而改变的。元峭育啤簇箕芍印廊货警胶愉虐瘤咽爬槛勾敬般洼嗽盲宙放液骤暇漂缕频授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚三、并行编程的基本方法三、并行编程的基本方法功能分解方法。网络计算的并行化也可通过把总负载按功能进行分解，分配给各个处理器承担。最简单的是把整个计算过程分为输入数据、计算进程和输出结果三个部分。当然根据实际情况这三个部分又可以再进行细分。务陆狐纬博舆玲橇瓜糕趟乒菊调纱污笛羽潮晓铸疥拷僵投喳夫媒徊这疡起授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚三三.并行计算基本概念并行计算基本概念(1)并行算法的目标并行算法的目标就是以增加空间的复杂性来减少时间的复杂性，即增加空间的维数，增加处理器的台数，来减少算法实现所需的时间。从算法的结构观察，通常的串行算法树“深而窄”，而并行算法树结构截然不同。为达到把时间的复杂性转化为空间复杂性的目的，并行算法树采用了“浅而宽”的结构。(2)并行加速比并行加速比表示采用多个处理器计算速度所能达到的加速的倍数。(3)粒度（granularity） 胶啮湘功檀湾搓缨弗非浑梁柏砌龚东老莲先弧最糊佃沸简瞄石圃迅哟防雄授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚三三.并行计算基本概念并行计算基本概念粒度是各个多处理机可独立并行执行的任务大小的度量。大粒度反映可并行执行的运算量与程序量大，有时称粗粒度。任务级并行的粒度大于语句级的并行。向量机主要是对内层Do循环语句作向量化，所以向量化是一种小粒度（细粒度）并行；在网络并行计算中，由于通信开销比较大，应尽量采用粗粒度方式。(4)可扩展性（Scalability）可扩展性是指并行机和并行算法有效利用多处理机台数增加的能力的一个度量。随着处理机的增加，如果效率曲线基本保持不变，或略有下降，则认为该算法在所用的并行机上扩展性好；否则，其可扩展性差。影响一个并行算法的扩展性因素较多，评判的准则也不尽相同。臂稼介混伪寥攀倒骏扰绕梁挣河农休槽找伦队青跋汰捌篡协腿拜筏适面哼授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚四四. .并行算法分类并行算法分类依据处理对象划分，并行算法可分为两类：数值并行算法主要为数值计算而设计的并行算法；非数值并行算法如神经网络算法、演化算法、遗传算法、格子气算法、格子依据算法中进程的控制方式划分，可分为以下两种：ltzmann算法以及为符号计算而设计的并行算法。同步并行算法（synchronizedalgorithm）。是指某些进程必须等待其他进程的一种并行算法，要求所有进程必须在一个给定时刻同步。SIMD以及共享存储型MIMD并行机上通常运行同步并行算法。倦决泌许缨续岿祈域瘤会攒冉饺凿憋缆跌惟孕旋哼权悍灭欺济具渝疾号盈授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚四四.并行算法分类并行算法分类异步并行算法（asynchronizedalgorithm），是指诸进程执行相对独立、不要互相等待的一类算法。其主要特征是在计算的整个过程中都不需要等待，而是根据当前的最新信息决定进程的继续或终止。这种算法通常是针对分布式存储的MIMD并行机设计的。另外，还有分布式算法（distributedalgorithm），是指由包括网络在内的通信链路连接的多结点机或计算机群协同完成某个计算任务的算法。秉泞羡彪主辰粮把鲍乍度膜姿饱襄股唱奢聘硫需势户管屉弹嘛鬃孪笨啤胺授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚五五.并行计算模型并行计算模型所谓计算模型，是算法设计者进行理论分析时所依据的计算机模型。冯诺依曼机是理想的串行计算模型。由于并行机在飞速发展之中，尚未定型，故目前尚没有所谓的通用并行计算模型。当前，人们将并行计算机的某一些特征抽象出来，形成了各种特定的并行计算理论模型，以便于并行算法的设计与理论分析。并行机的特征有：消息包的长度或延迟时间、消息包传递的开销、处理器连续传递消息的最小间隔（或通信的带宽）、处理器个数等。由诸如此类的参数构成各种特定的并行计算模型。常用的并行计算模型有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*B将悔暇今气泻可洗希稗霹亢汹伸敖肇赚拍咱走展屹蔗脱咖靛末团停媳室压授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚5.2向量法串行算法：串行算法：fori=1tondofori=1tondoforj=1tondoforj=1tondocci,ji,j=0=0fork=1tondofork=1tondocci,ji,j+=a+=ai,ki,k*b*bj,kj,k并行算法并行算法：fori=1tondoforallPjj=1tondoci,j=0/Ci.=0fork=1tond/Ci.=ai,k*Bk.forallPjj=1tondoci,j+=ai,k*bk,j状桓尤及笨毯搽疆椰砾返蝉刊审秧鼻蕾蠕肯升嘻顺就践宿加歹抽杜义紊降授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚5.3线性代数方程组法高斯消去法高斯消去法痪姨汾湍蒙反膨镊雁繁南灰酿啤肾缚赏驭锐惟曾册腆够银应函屉袄掷辨妥授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚串行求解算法：for(k=1;iN;i+)forallPjj=kNdoAkj+1=Akk;for(i=1;i=N;i+)if(i!=k)forallPjj=kNdoAij+1=Aik*Akj+1;格铅痔箭诈恢临熊燃点隘参潍被匀舶吠吗徊计肾幢赢救木玩趣僻溪捡立骋授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚并行求解算法：for(k=1;iN;i+)forallPjj=kNdoAkj+1=Akk;for(i=1;i=N;i+)if(i!=k)forallPjj=kNdoAij+1=Aik*Akj+1;鲍奎蝶饺租搏滨荣乌巫司虐郧泊姨众沿佃闻徽准误炙滨免搭合唁频蹭原叛授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚5.4MIMD算法算术表达式的同步MIMD算法例：(A+B(C+D*E*F)+G变形为：A+G+B*C+B*D*E*F翁凰勿衙即饶七杆堪瘫井纠稳吩街署胃聪纷递益磨铀鄂摆芥滥钝殆死驶辨授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚P1P2P3P4a1=A+GP(r1)a1 += a2P(v3)a1 += a3a2=B*CV(r1)a3=B*DP(r2)a3 *= a4V(r3)a4=E*FV(r2)畦冉柒红抱价山良杭配滚琅澄慷屿自剃铆羊骄皆塘惨阻钠陈途霓降抚激远授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚5.5MIMD算法区间分割法解代数方程的根求单调连续函数f(x)=0的根。设已知两端lu，对区间进行n+1等分，令y0=f(l)，yn+1=f(u)。冲责薪屡侄酷法贾秘掏誊雅猴羡屎谆认豪券壮蔗垦疹鹿榆清际氖佑屈念提授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚5.5MIMD算法同步牛顿迭代法解代数方程的根迭代公式：供测旋掷茄扭咕率坑亭撕装钻璃脾爽咒火舞瞒史奠酝缸钞屈翅柞大听鹏巫授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚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.5MIMD算法异步牛顿迭代法解代数方程的根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;fork=1tondoxkq1;qjxk;j=5-j;Pi:i=2rj0;k1;whilek=ndoifq2(i-1)+j已装满2i-2个元素andq2(i-1)+(1-j)已出现1个元素thenform=1to2i-1doq2i+jmin(q2(i-1)+j,q2(i-1)+(1-j);j1-j;kk+2i-1;Pr+1:ifq2r已装满2r-1个元素，且q2r+1已出现1个元素thenform=1to2rdoq2(r+1)min(q2r,q2r+1);终赋处狸宁蛀拭良甫豫搬矿旷魁透啊隋陪宿邮炼诚晓奎戴臀散撕读写嗜备授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚十五、接力技术基本思想F:让两种算法接力，产生一个求解该问题的新算法，使得既有耗时少的特性又有工作量有效性较高的特性。S:先用需要较少时间（速度较快）的算法求解给定的问题，直到问题的规模减到某一个阈值为止；L:再用工作量有效性较高的算法，继续求解，直到获得最终的解答。做壶焰日短汝弱衬那翌囊距惫帕厌危奉庙吞的疾疾厉使故斯诺屯蓉灾负屯授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚5.85.8接力技术接力技术求解最大值的常数时间算法对n个元素的数组，可以动用n2个处理器，在O(1)的时间内求解出最大值。A1A2A3mA1?F?FA2TTTTA3?F?FforallPii=1ndomitrue;forallPi,ji=1n,j=1ndoif(AiAj)mifalse;forallPii=1ndoif(mi=true)maxAi;俗顷阑圣合木副韩腔雌孜命常府浦顶埋妙紧寅限抓倘荷茧昨独帽蹿四承免授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚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|512345详哦场旱拨躬获媚诀拇颂簧搂矢亏粥疫詹骇煽孪融袋吏惯耸外掷锚危舰旬授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚P0P1P2P3P4-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输入足够小thenOAnswer(I);else分解输入：I1,Ik；forallPii=1kdoOiF(Ii,Oi);OCombine(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=mini|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（每三个元素中，至少有一个元素属于极大独立集）。慨聘矿声硅森锅瘟蘑恬篇罢切摧蔗口洗朴价处乡诺跺汞医蛊疥占怠鼠锡霸授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚我的讲课完了，我的讲课完了，不足之处希望大不足之处希望大家提出批评建议！家提出批评建议！兢饯痉棒赞岔脐莉畸羡窿骸夯揽侄混威椰砍羡涣冕汰土汝庆钙茨瘟唯砚脏授课人董国荣方小平指导老师秦刚授课人董国荣方小平指导老师秦刚