并行编程中的设计模式.docx

并行编程中的设计模式这篇文章是对这段时间学习并行编程中的设计模式的一个总结。有不当之处，盼望得到大家的批判、指正。首先，所谓''并行编程中的设计模式(patternsinparallelprogramming)仍处于不断的被发觉、发掘的阶段。当前已经有各路人马对这一领域进行了讨论，但远远没有达到统一熟识的高度。也没有一套业界普遍认同的体系或者描述。这就造成了当前这领域的现状:从事讨论的人有不同的背景，他们各自总结出的模式种类不尽相同。即使是同个模式，不同的团队给它们取得名字也可能不一样。不过这并不阻碍我们对''并行编程中的设计模式进行肯定的了解，并在实际的软件开发工作中有所借鉴。本文分两部分，第一部分会简洁介绍这一领域的进呈现状：首先是进行讨论的主要团体及其代表人物，然后介绍一下他们各自总结的模式体系，最终着重介绍一下加州高校伯克利分校的体系，Apatternlanguageforparallelprogramming,=其次部分则从该体系中挑出八个常用的设计模式作略微具体一点的介绍。每个设计模式都附有实际的应用例子来关心理解。我始终信任，通过例子的学习是最简洁理解的一种方式。1.并行编程模式的进呈现状在这一领域比较活跃的讨论团体包括：1 .加州高校伯克利分校。其代表人物是KilrtKeUtZe教授，他曾是SynoPSyS公司的CTOo2 .Intel公司。代表人物是TimMattSon,他是Intel的PrincipleEngineer和并行计算的布道师(evangelist),是"PatternsforParallelProgramming一书的作者。3 .伊利诺伊高校。代表人物是RaIphJohnson教授。他是闻名的设计模式''GangofFour"中的一员¢4 .其他团体：包括微软、麻省理工高校等等。他们总结出的并行编程模式体系不尽相同，相互之间又有着紧密的联系。主要有：1,加州高校伯克利分校的APattemLangUag6ParallelProgrammingver2.02 .伊利诺伊高校的ParallelPrOqramminqPdtternS3 .TimMattson的著作PattemSforParallelProgramming这其中，我最为喜爱加州高校伯克利分校的体系：伯克利的讨论人员认为，写出高质量并行软件的关键在于拥有好的软件设计：从软件的总体架构，始终到系统的底层实现。将这些''好的设计以一种系统的方式描述出来，并在各个不同的软件项目当中重用是解决构建高质量并行软件问题的关键。这远比各种具体的编程模型以及其支撑环境来得重要。由于拥有了一个好的设计之后，我们可以很简洁的在各种开发平台上编写源代码。伯克利的模式体系包含了几个不同的层次，上自软件架构，下至程序指令执行的策略。最上面的两块分别是''架构模式"(StnJCtUralPattemS)和"计算模式(COmPUtationalpatterns),这两块并不单单包括并行软件，也包括传统的串行软件模式。用我们常用来表达系统架构的线框图打比方，”架构模式指的就是那些箭头和框框，它们表示的是程序总体的组织结构，以及各部分之间是怎么交互的计算模式指的是框框里面的计算类型。例如，是基于图的算法，还是有限状态机，还是线性代数运算，等等。程序设计师通常需要在这两大类模式之间翻来覆去的进行选择。例如，我们可能先选择了一种架构模式，然后考虑使用某些合适的计算模式。但是选择的计算模式可能更适合于在另一种架构模式下运行，所以我们又得重新选择一种架构模式.如此反复。上面这张图在''架构模式和''计算模式”这两大块之间画了两个反复的箭头，表达的就是这个意思。这张图下方的三大块就专指并行编程当中的模式了。它们包括“算法模式(AlgoHthmstrategypatterns),''实现模式"(ImplementationstrategyPatternS)和''并行执行模式”(Parallelexecutionpatterns)o顾名思义，''算法模式指的是程序算法层面的模式。它们表达的是，为了解决某一类实际问题，怎么样在较高的算法层面实现并行。''实现模式指的是我们在编写源代码的时候，采用什么样的一些程序掌握结构利数据结构来实现并行。例如、'paallel_for，例如并行容器，等等。最终一个''并行执行模式指的是为了在计算机中有效的执行一个并行程序,我们应当实行哪些方法。这包括指令的执行模式,例如是MIMD还是SlMD,也包括一些任务调度的策略。这三类模式是紧密联系在一起的。例如，为了解决一个问题，我们可能使用''recursivesplitting的算法模式。而为了实现这个算法，我们很有可能使用''fork-join的实现模式。在执行层面，并行程序库则通常会用''threadpool"的并行执行模式来支持''forkjoin的运行。由于我们在编写程序时，''并行执行模式往往由编译器或并行程序库例如TBB的编写人员考虑,我们并不需要关怀;''实现模式和我们选择的具体并行运算平台有关(OPenMP,TBB,MPI,等等)，不同的平台有不同的API；”计算模式则和具体的问题域联接紧密。而且，看上去伯克利所总结的''计算模式大部分和高性能计算有关，一般的应用程序员并不熟识。所以在本文，我将只选择和并行计算亲密相关的两个''架构模式和六个常见的''算法模式举例进行说明。2.八个常用的并行编程模式2.1AgentandRepository(RepoMorycon<roK¢¢$)这是一个''架构模式，它针对这样一类问题：我们有一组数据，它们会随机的被一些不同的对象进行修改。解决这一类问题的方案是,创建一个集中管理的数据仓库(datarepository),然后定义组自治的agent来操作这些数据，可能还有个manager来对agent的操作进行协调，并保证数据仓库中数据的全都性。我们常见的源代码版本掌握软件例如Perforce就是实现这种架构的典型代表：源代码都存放在一个统一的服务器中(或是一组服务器中，但对Clierlt而言是透亮的)，不同的程序员们使用各自的客户端对源代码文件进行读，写，力口，删的操作。由Perforce负责保证源代码数据的全都性。2.2MapReduceMaPRedUCe这个名词原来是函数式编程里面的个概念，但是自从GoogIe于2004年推出同名的并行计算程序库后，提到这个名词大家大多想到的是Google的这个Framework0在这里，MaPRedUCe是一个''架构模式的名称。当然，我们这里的MaPRedUCe指的就是类似GoogIeMapRedUCe工作原理的类模式。那么什么是MaPRedUCe的模式呢？用较为简洁的语言描述，它指的是这样类问题的解决方案：我们可以分两步来解决这类问题。第一步，使用一个串行的MaPPer函数分别处理一组不同的数据，生成个中间结果。其次步，将第一步的处理结果用一个RedilCer函数进行处理(例如，归并操作)，生成最终的结果。从使用GOOgIe的MaPRedUCe程序库的角度而言，作为应用程序员，我们只需供应一组输入数据，和两个一般的串行函数(MapperReducer),GOOgI6的MaPRedllCe框架就会接管切，保证输入数据有效的在一个分布式的计算机集群里面安排，然后MaPPer和RedUCer函数在其上有效的运行、处理，并最终汇总生成我们想要的处理结果。全部一切的细节，例如并行化、数据的安排、不同机器之间的计算误差，通通被隐蔽在程序库内。那么MapReduce究竟是什么样的一个过程呢？我们讲过，使用MaPRedUce,程序员必需供应一组输入数据，以及一个MaPPer和一个RedUCer函数。在这里，输入数据必需是个按(inpcit_key,input_value)方式组织的歹IJ表。KinPUjkey,iput-value),(input_key,input_value).mapper函数的任务是处理输入列表中的某一个单元数据：mapper(input_key,input_value),并产生如下输出结果:(interaediat«_key,inter*ediate_value),(lnte11Dediatlc4y',lnte(ediate,vlue,)f接下来，把对全部单元数据的处理结果依据intermediate_key归类：同样的intermediate_key放在起，它们的intermediate_value简洁的串接起来，得至U：(intermediate.key,intcrmediate_value_list),(itermediate-key,intermediate_valae_lt$t).Reducer函数的任务是对上述的中间结果进行处理：reducer(intermediate_key,intermediate_value_list),并产生如下最终输出结果：|(output_key,output_value),(OUtPUJkev,output_valueh我们会举两个例子说明这一过程。第个例子是一个简洁的统计单词消失次数的小程序。其次个例子是Google曾经怎样使用MapReduceFrameWork来计算PageRanko第一个例子，假设我们要写一个小程序，来统计在几篇不同文章里全部消失过的单词各自总共消失的次数。我们应当怎么做呢？卜.面描述的采用MapReduce的方法确定不是大多数程序员第一感会想到的方法。但这种方法特别好的揭示了MapReduce的基本思想。并且，这种方法很简洁被扩展处处理上千万甚至是上亿的文件数据，并且能够在一个分布的计算机集群里面运行。这可不是传统的方法能够轻易做到的。具体而言，假设我们有如下三个文本文件，a.txtzEtxt和c.txt：texxa.txt:Thequickbrownfox:overthelzygreydo9.textbtxt:Thatonexallstepforaxaaonei<atleapforacanklnd.textctxc:KrybadaIitclel<ab,Xcflee<vvhcr&ov;ArzieverywherethatMaryYen匕.Thel«abwa>urtogo.对于输入数据而言，inpuJkey就是文件名，inpuJVaIue就是一-个大的String,包含的是文件内容。所以我们的输入数据看上去会是这样的：(*a.txt*,thequickbrownfoxjumped.),(T).txt,*that*sonesmallstepfotaman).('c.rt'MaryhadIMleIamt>,INAeeCe.1我们会写一个简洁的串行的mapper(fileNamezfiIeContent)S<,这个函数做的事情很简洁，读入一个文本文件，把每一个遇到的单词当作一个新的intermediate_key,并赋其intermediate_value为1。将mapper函数处理文件a,我们会得到如下结果：t<,th,1).(<plck,1),(brown,1),(fo,1>,<,utd,1)('ovL,l),<3',",(hwy',1>,<,gey11.-311”将全部三个文件的处理结果放在一起，我们得到：(te,I),(<uick,f1),(brovn,1),(,fM,1),1)，(,ove,1),(,tM,1)，('lzy1),(,qry,<,dofl三r1),(,BAty<,<l,X),(,1).(lttle,14"aab,1).(,c,*,U,v,l)r(,wte<<*1>.(,now,1>«Cd,”,<vryw<r,l)f(tat,”,(三ry,1),(v*nf,l)f<,thel>r(*la*r(*w'.('>ur”,<co1),(,gof”,(*cta,1),Com.Dt(ll,l>v(cp,1),Cfor,1>,”,1)«(,on,1),(,gnc,1),(*l*p“，(for,1<,Bkind'.X>然后将中间结果按intemediate_key归类:<and:(I)9,foxt:(1),iover:(lrte:(1,X),t:goI(11,tXlh1ajU),:C.1)#,giantb:(I)rfors1,IbtjuM>d:(lhad:CLrnowt:(1bto:(1),lepl:Clhwhite*:(lhwas:1“®ary：(1,Ibbrown:(I)ttXxyt:(lror*i:(I)r,tafx(I)rllttl:I)r9nalli:(lh>tep:(1),everywhere*:(1¼eBAAlcind9:(lbventt(1)/an:(1),*t:1】Ibtflwe:(I)9trey:(lbdo>,:(1,quick1x(lhce:(lrlrl)rthats:(1J)最终，由reducer(intermediate-keyzintermediate_valueist)对中间结果进行处理。它做的事也很简洁，仅仅是把某intermediate_key对应的全部intermediate_value相加。我们于是得到最终结果：(<n,”(,fox”，(,ovr,”,ConW,2).(,1),<'9.”,(,lt9,】).(,lMb,2).(g*nt,",(,for,2»(,3upedX),(,h<l”,(,nov,1),(,eo,1),(,lea,(wte,”,(w2),(ry,2),(brom,1),<,lxy.1>»(,8uretl>r(tat,(lttle,1),<*3*11*,1),(*acep',“，('everywhere,1>,('s*nkxnd*,1)<'wnt”，】)，(,2),(*flc,”，(,gxv,.1<,<*o,1),(iick,1),(,te3),<tat,1)其次个例子，怎样使用MapRedUCe计算PageRanko什么是PageRank?可能大家都有所了解，这是G。OgIe用来量度一个网页的.重要性的值。简洁而言，有越多的其它网页链接到这个网页，这个网页的PageRank越高。链接到这个网页的网页PageRank越高，这个网页的PageRank也越高。假设我们一共有n个网页0,1,，nl。对第j个网页我们给它赋一个PageRank值qj。全部的qj组合起来成为一个向量q=(qo,q,.qn-i)。这个向量满意概率分布。即5的值都在0和1之间，并且全部的qj加起来等于1。5越大，网页的重要性越高。那么q是怎么计算出来的呢？答案是使用迭代的方法:我们从一个初始的PageRank向量分布P开头，乘以一个n*n的矩阵M,得到一个新的PageRank向量。把新的PageRank向量连续乘以M得到下一步的PageRank如此迭代有限步后，PageRank向量的值会趋于收敛，于是我们得至U最终的PageRank。这里需要回答两个问题：1.如何确定初始的PageRank,即迭代的起点？答案是任意选择一个概率分布就可以，无论你选择什么初始值，都不影响其收敛到最终的结果。我们通常使用匀称概率分布，即尸Hni42.如何定义M?这个问题稍显简单，有爱好的读者可以参见MiChaelNielsen的博文USingMaDRedUCetoComDUtePageRank了解更具体的内容。在这里，我们将其简化的定义为一个描述网页间相互链接结构的超大矩阵。假设网络里有n个网页，那么我们这个矩阵就是一个n*n的方阵。矩阵的每一列代表一个网页对外的超链接状况。例如，我们定义#(j)为第j个网页对外的全部超链接的数量。那么对于矩阵M的第j列而言，假如网页j对网页k没有超链接，那么第k行元素Mkj=O,否则Mkj=l/#(j)o这里隐含的意思是当一个读者在扫瞄网页j时，有l/#(j)的可能性跳转到网页ko那么如何使用MapReduce来计算PageRank呢？虽然整个迭代的过程必需是串行的，迭代的每一步我们还是可以用MapRedUCe来并行的计算的。这里也必需并行的计算由于这个矩阵和向量的规模是超大的(想象一下整个互联网的网页数量)。使用MapRedUCe来计算迭代的一步实际上是用MapRedUCe来计算矩阵和向量的乘法。假设我们要计算如下一个方阵和向量的乘法。其实质是将第i个向量元素的值Pi乘以矩阵第i列的每一元素，然后放在矩阵元素原来的位置。最终，把矩阵第i行的全部元素相加，得到结果向量的第i个元素的值。“、MoMlM2Pl(也0%M22,Pz)类似的，我们可以得到用MapReduce计算PageRank的方法：第一步,输入的(inpuJkey,inpJjVaIUe)。inpujkey是某个网页的编号，如j。input_value是一个列表，元素值是M矩阵的第j列元素，最终再加上一个pj,就是当前网页j的PageRank值。其次步，MapoMaPPer(inpujkey,inPUjVaIIle)所做的事情很简洁,就是把Pj乘以列表元素的每一个值，然后输出组(intermediate_key,intermediate_va山e)。intermediate_key就是矩阵的行号，k。intermediate_value就是Pj列表元素的值，即Pj乘以矩阵第k行第j列的元素的值。第三步，汇总。把全部intemediate_key相同的中间结果放到一起。即是把第k行全部的intermediate_value放在一个列表intemediate_vaIueJist内。第四步，ReducecRedUCer(intemediate_key,intermediate_value_list)做的事也很简洁，就是把intermediate_value_list内全部的值相加。最终形成的(OUtPIJjkey,OUtPUjVaIUe)就是结果向量第k行的元素值。以上就是采用MapReduce计算PageRank的简略过程。这个过程相当粗略和不精确，只是为了揭示MapReduce的工作过程和Google曾经用来计算PageRank的大致方法。认真的读者应当查阅其它更严谨的著作。最终，和上述计算矩阵和向量乘法的例子相像，MaPRedUCe也可以用来计算两个向量的点乘。具体怎么做留给读者自己去思索，一个提示是我们全部的intermediate_key都是相同的，可以取同一个值例如1。2.3 DataParallelism这是一个''算法模式”。事实上，把DataParallelism和下节将要提到的TaskParallelism都称之为一种''算法模式我觉得有过于笼统之嫌。到最终，哪一种并行算法不是被分解为并行执行的task呢(taskparallelism)?而并行执行的task不都是处理着各自的那份数据吗(dataparallelism)?所以假如硬要把DataParalIeliSm和TaSkParallelism称为两种算法模式,我只能说它们的地位要高于其它的算法模式。它们是其它算法模式的基础。只不过对于有些问题而言，比较明显的我们可以把它看成是DataParallelism的或是TaSkParallelism的。或许DataParallelism模式和TaskParallelism模式特指的就是这类比较明显的问题。那么什么是DataParallelism?顾名思义，就是这类问题可以表达为同样的一组操作被施加在不同的相互独立的数据上。ProblemDataSet个比较典型的例子就是计算机图形学里面的Raytracing算法。Raytracing算法可以大致描述为从一个虚拟相机的光心射出一条射线，透过屏幕的某个像素点，投射在要渲染的几何模型上。找到射线和物体的交点后，再依据该点的材料属性、光照条件等，算出该像素点的颜色值，赋给屏幕上的像素点。由于物体的几何模型许多个小的三角面片表示，算法的第一步就是要求出射线与哪个三角面片有交点。射线与各个单独的三角面片求交明显是相互独立的，所以这可以看做是DataParalIeliSm的例子。2.4 TaskParallelismTaskParallelism的算法模式可以表述为，组相互独立的TaSk各自处理自己的数据。和DataParalIeIiSm不同，这里关注的重点不是数据的划分，而是TaSk的划分。如前所述，TaskParallelism和DataParallelism是密不行分的。相互独立的Task确定也是运行在相互独立的数据上。这主要是看我们以什么样的视角去看问题。例如，上一节RayTracing的例子中，我们也可以把射线和一个独立的三角面片求交看作是一个独立的Tasko这样就也可以当它做是TaSkPaQlleliSm的例子。然而，咬文嚼字的去区分究竟是TaskParalleliSm还是DataParalleliSm不是我们的目的，我们关注的应当是问题本身。对于某一个具体问题，从DataPaallelism动身考虑便利还是从TaSkPaQlleIiSm动身考虑便利，完全取决于问题本身的应用场景以及设计人员自身的阅历、背景。事实上，许多时候，不管你是从TaSkParalIeliSm动身还是从DataParalIeliSm动身，经过不断的优化，最终的解决方案可能是趋同的。下面一个矩阵乘法的例子很好的说明白这个问题。我们都知道矩阵乘法的定义：假如有n行k列的矩阵A乘以k行m列的矩阵B,那么我们可以得到一个n行m列的的矩阵C。矩阵C的第n行第m列的元素的值等于矩阵A的第n行和矩阵B的第m列的点乘。从TaSkParallelism的角度动身,我们可能把计算C的每一个元素当做一个独立的TaS匕接下来，为了提高CPU的缓存采用率，我们可能把邻近几个单元格的计算合并成一个大一点的TaSkO从DataParalIeliSm的角度动身，我们可能一开头把C按行分成不同的块。为了探究究竟怎样的划分更加有效率，我们可能调整划分的方式和大小，最终，可能发觉,最有效率的做法是把A,B,C都分成几个不同的小块，进行分块矩阵的乘法。可以看到，这个结果实际上和从TaSkParallelism动身考虑的方案是殊途同归的。2.5 RecursiveSplittingReCUrSiVeSPlitting指的是这样一种算法模式：为了解决个大问题，把它分解为可以独立求解的小问题。分解出来的小问题，可能又可以进一步分解为更小的问题。把问题分解到足够小的规模后，就可以直接求解了。最终，把各个小问题的解合并为原始的大问题的解。这实际上是我们传统的串行算法领域里面也有的''divideandConqUer的思想。举两个例子。第一个是传统的归并排序。例如，要排序下面的8个元素的数组，我们不管三七二十一先把它一分为二。排序4个元素的数组还是显得太简单了，于是又一分为二。现在，排序2个元素的数组很简洁，依据大小交换挨次就行。最终，把排好序的数组按序依次组合起来，就得到我们最终的输出结果。Mergesortexample:I>Startingpoint:36415732>Splitintwo:3641(5732>Splitintwo:(36(41J5732>Basecase:P61457(23>Sortonmerge:1346(2357>Sortonmerge:1233456其次个例子略微好玩一点，是个如何用程序解''数独嬉戏的例子。数独就是在一个9*9的大九宫格内有9个3*3的小九宫格。里面有些格子已经填入了数字，玩家必需在剩下的空格里也填入1到9的数字，使每个数字在每行、每列以及每个小九宫格内只消失一次。这里作为举例说明,我们考虑一个简洁一点的状况:在一个4*4的格子里填入14的数字,使其在每行、每列以及每个2*2的格子里只消失一次。解''数独嬉戏的算法可以有许多种。假如是人来解，或许会依据上图的次序依次填入1,2,3到相应的格子当中。每填入一个新数字，都会重新按规章评估四周的空格，看能否按现有状况再填入一些数字。这个方法当然没错，不过看上去不太简洁并行化。下面介绍一个依据''recursiveSPlitting的方法可以很简洁做到并行化的解法。1）首先，将二维的数独格子绽开成一个一维的数组。己经有数字的地方是原来的数字，空格子的地方填上''OQ8"*30040002mI2）接下来，从前到后对数组进行扫描。第一格是、'3，已经有数字了，跳过。移动搜寻指针到下一格。300400023）其次格是、'0,意味着我们需要填入个新的数字。这个新的数字有4种可能性：1,2,3,4。所以创建4个新的搜寻分支：4）接下来依据现有的数字信息检查各个搜寻分支。明显，第三和第四个搜寻分支是非法的。由于我们在同一行中已经有了数字''3和、'4。所以忽视这两个分支。第一和其次条分支用现有的数字检查不出冲突,所以连续从这两个分支各派生出4条新的分支进行搜寻这个思路像极了我们之前的归并排序的例子,都是在算法运行的过程中不断产生出新的任务。所以实际上这也是一个''TaskParalleliSm的例子。2.6Pipeline''Pipeline也是一种比较常见的算法模式。通常，我们都会用汽车装配中的流水线、CPU中指令执行的流水线来类比的说明这一模式。它说的是我们会对一批数据进行有序、分阶段的处理，前一阶段处理的输出作为下一阶段处理的输入。每一个阶段永久只重复自己这一阶段的任务，不停的接受新的数据进行处理。用一个软件上的例子打比方，我们要打开一批文本文件，将里面每一个单词的字母全部改成大写，然后写到一批新的文件里面去，就可以创建一条有3个Stage的流水线：读文件，改大写，写文件。Time0000HH000回叵回回回叵''Pipeline模式的概念看上去很简洁理解，可是也不是每一个人都能一下子理解的那么透彻的。例如有这样一个问题：我们有一个for循环，循环体是一条有3个stage的pipeline,每个Stage的运行时间分别是10,40,和10个CPU的时钟间隔。请问这个for循环执行N次或许需要多长时间（N是一个很大的数）？A. 60*NB. 10*NC. 60D. 40*N请认真思索并选择一个答案。：）答案是40*N0流水线总的执行时间是由它最慢的个Stage打算的。缘由请见下图。2.7Geometricdecomposition接下来这两个算法模式看上去都显得比较特别化，只针对某些特定的应用类型。''Geometricdecomposition说的是对于一些线性的数据结构（例如数组），我们可以把数据切分成几个连续的子集。由于这种切分模式看上去和把一块几何区域切分成连续的几块很类似，我们就把它叫做"Geometricdecomposition"。Nciglibor-To-Ncighborcommunication最常用的例子是分块矩阵的乘法。例如，为了计算两个矩阵A,B的乘法。我们可以把他们切分成各自可以相乘的小块。结果矩阵当然也是分块的:结果矩阵每一分块的计算依据如下公式进行:例如：C11=ABtftl=(0I(5X0)三(O).C,ABA1H三(00)|；J*(5X2)=(010).最终的结果就是：下面这幅图显示了两个4*4的分块矩阵A,B进行乘法时，计算结果矩阵C的某一分块时，需要依次访问的A,B矩阵的分块。黑色矩阵分块代表要计算的C的分块，行方向上的灰色矩阵代表要访问的矩阵A的分块，列方向上的灰色分块代表要访问的矩阵B的分块。UPdaysU1UPdagStrP22.8Non-work-efficientParallelism这个模式的名字取得很怪异，也有其他人把它叫做''RecursiveData"。不过相比而言，还是这个名字更为贴切。它指的是这一类模式：有些问题的处理使用传统的方法，必需依靠于对数据进行有序的访问，例如深度优先搜寻，这样就很难并行化。但是假如我们情愿花费一些额外的计算量，我们就能够采纳并行的方法来解决这个问题。常用的一个例子是如下的”查找根节点的问题。假设我们有一个森林，里面每一个节点都只纪录了自己的前向节点，根节点的前向节点就是它自己。我们要给每一个节点找到它的根节点。用传统的方法，我们只能从当前节点动身，依次查找它的前向节点，直到前向节点是它自身。这种算法对每一个节点的时间简单度是O(N)。总的时间简单度是N*O(N).假如我们能换种思路来解这个问题就可以将其并行化了。我们可以给每一个节点定义一个SUCCeSSor(后继结点)，SUCCeSSor的初始值都是其前向节点。然后我们可以同步的更新每一个节点的successor,令其等于"successor的successor7",直到successor的值不再变化为止。这样对于上图的例子，最快两次更新，我们就可以找到每个节点的根节点了。这种方法能同时找到全部节点的根节点，总的时间简单度是N*log(N)o3.后记如前所述，''并行编程中的设计模式”是一个仍在不断变化、进展的领域。这篇博文简要介绍了这一领域当前的进呈现状,并选取八个常用的模式进行了介绍。我涉足并行编程领域不久,许多理解也并不深化。所以文章的缺点错误在所难免，真诚盼望能得到大家的批判指正。4.参考文献本文的写作参考了如下资源，可以作为进一步阅读的材料： UCBerkeley,APattemLdngUageforParallelProgramming Eun-GyuKimzParaIlelProgramminqPattemS JimBrownezDeSignPattemSforParallelCOmDUtation TimMattson,PattemSPaQllelProgramming MichaelNielsen,USingMaDRedUCetoCOmDUtePageRank AaterSulemanzParalIelProgramming:DoyouknowPiDeIineParallelism?标签：并行编程,设计模式