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

《并行编程中的设计模式.docx》由会员分享，可在线阅读，更多相关《并行编程中的设计模式.docx（15页珍藏版）》请在课桌文档上搜索。

1、并行编程中的设计模式这篇文章是对这段时间学习并行编程中的设计模式的一个总结。有不当之处，盼望得到大家的批判、指正。首先，所谓并行编程中的设计模式(patternsinparallelprogramming)仍处于不断的被发觉、发掘的阶段。当前已经有各路人马对这一领域进行了讨论，但远远没有达到统一熟识的高度。也没有一套业界普遍认同的体系或者描述。这就造成了当前这领域的现状:从事讨论的人有不同的背景，他们各自总结出的模式种类不尽相同。即使是同个模式，不同的团队给它们取得名字也可能不一样。不过这并不阻碍我们对并行编程中的设计模式进行肯定的了解，并在实际的软件开发工作中有所借鉴。本文分两部分，第一部分

2、会简洁介绍这一领域的进呈现状：首先是进行讨论的主要团体及其代表人物，然后介绍一下他们各自总结的模式体系，最终着重介绍一下加州高校伯克利分校的体系，Apatternlanguageforparallelprogramming,=其次部分则从该体系中挑出八个常用的设计模式作略微具体一点的介绍。每个设计模式都附有实际的应用例子来关心理解。我始终信任，通过例子的学习是最简洁理解的一种方式。1.并行编程模式的进呈现状在这一领域比较活跃的讨论团体包括：1 .加州高校伯克利分校。其代表人物是KilrtKeUtZe教授，他曾是SynoPSyS公司的CTOo2 .Intel公司。代表人物是TimMattSon,

3、他是Intel的PrincipleEngineer和并行计算的布道师(evangelist),是PatternsforParallelProgramming一书的作者。3 .伊利诺伊高校。代表人物是RaIphJohnson教授。他是闻名的设计模式GangofFour中的一员4 .其他团体：包括微软、麻省理工高校等等。他们总结出的并行编程模式体系不尽相同，相互之间又有着紧密的联系。主要有：1,加州高校伯克利分校的APattemLangUag6ParallelProgrammingver2.02 .伊利诺伊高校的ParallelPrOqramminqPdtternS3 .TimMattson的著作

4、PattemSforParallelProgramming这其中，我最为喜爱加州高校伯克利分校的体系：伯克利的讨论人员认为，写出高质量并行软件的关键在于拥有好的软件设计：从软件的总体架构，始终到系统的底层实现。将这些好的设计以一种系统的方式描述出来，并在各个不同的软件项目当中重用是解决构建高质量并行软件问题的关键。这远比各种具体的编程模型以及其支撑环境来得重要。由于拥有了一个好的设计之后，我们可以很简洁的在各种开发平台上编写源代码。伯克利的模式体系包含了几个不同的层次，上自软件架构，下至程序指令执行的策略。最上面的两块分别是架构模式(StnJCtUralPattemS)和计算模式(COmPUt

5、ationalpatterns),这两块并不单单包括并行软件，也包括传统的串行软件模式。用我们常用来表达系统架构的线框图打比方，”架构模式指的就是那些箭头和框框，它们表示的是程序总体的组织结构，以及各部分之间是怎么交互的计算模式指的是框框里面的计算类型。例如，是基于图的算法，还是有限状态机，还是线性代数运算，等等。程序设计师通常需要在这两大类模式之间翻来覆去的进行选择。例如，我们可能先选择了一种架构模式，然后考虑使用某些合适的计算模式。但是选择的计算模式可能更适合于在另一种架构模式下运行，所以我们又得重新选择一种架构模式.如此反复。上面这张图在架构模式和计算模式”这两大块之间画了两个反复的箭头

6、，表达的就是这个意思。这张图下方的三大块就专指并行编程当中的模式了。它们包括“算法模式(AlgoHthmstrategypatterns),实现模式(ImplementationstrategyPatternS)和并行执行模式”(Parallelexecutionpatterns)o顾名思义，算法模式指的是程序算法层面的模式。它们表达的是，为了解决某一类实际问题，怎么样在较高的算法层面实现并行。实现模式指的是我们在编写源代码的时候，采用什么样的一些程序掌握结构利数据结构来实现并行。例如、paallel_for，例如并行容器，等等。最终一个并行执行模式指的是为了在计算机中有效的执行一个并行程序,

7、我们应当实行哪些方法。这包括指令的执行模式,例如是MIMD还是SlMD,也包括一些任务调度的策略。这三类模式是紧密联系在一起的。例如，为了解决一个问题，我们可能使用recursivesplitting的算法模式。而为了实现这个算法，我们很有可能使用fork-join的实现模式。在执行层面，并行程序库则通常会用threadpool的并行执行模式来支持forkjoin的运行。由于我们在编写程序时，并行执行模式往往由编译器或并行程序库例如TBB的编写人员考虑,我们并不需要关怀;实现模式和我们选择的具体并行运算平台有关(OPenMP,TBB,MPI,等等)，不同的平台有不同的API；”计算模式则和具体

8、的问题域联接紧密。而且，看上去伯克利所总结的计算模式大部分和高性能计算有关，一般的应用程序员并不熟识。所以在本文，我将只选择和并行计算亲密相关的两个架构模式和六个常见的算法模式举例进行说明。2.八个常用的并行编程模式2.1AgentandRepository(RepoMoryconroK$)这是一个架构模式，它针对这样一类问题：我们有一组数据，它们会随机的被一些不同的对象进行修改。解决这一类问题的方案是,创建一个集中管理的数据仓库(datarepository),然后定义组自治的agent来操作这些数据，可能还有个manager来对agent的操作进行协调，并保证数据仓库中数据的全都性。我们常

9、见的源代码版本掌握软件例如Perforce就是实现这种架构的典型代表：源代码都存放在一个统一的服务器中(或是一组服务器中，但对Clierlt而言是透亮的)，不同的程序员们使用各自的客户端对源代码文件进行读，写，力口，删的操作。由Perforce负责保证源代码数据的全都性。2.2MapReduceMaPRedUCe这个名词原来是函数式编程里面的个概念，但是自从GoogIe于2004年推出同名的并行计算程序库后，提到这个名词大家大多想到的是Google的这个Framework0在这里，MaPRedUCe是一个架构模式的名称。当然，我们这里的MaPRedUCe指的就是类似GoogIeMapRedUC

10、e工作原理的类模式。那么什么是MaPRedUCe的模式呢？用较为简洁的语言描述，它指的是这样类问题的解决方案：我们可以分两步来解决这类问题。第一步，使用一个串行的MaPPer函数分别处理一组不同的数据，生成个中间结果。其次步，将第一步的处理结果用一个RedilCer函数进行处理(例如，归并操作)，生成最终的结果。从使用GOOgIe的MaPRedUCe程序库的角度而言，作为应用程序员，我们只需供应一组输入数据，和两个一般的串行函数(MapperReducer),GOOgI6的MaPRedllCe框架就会接管切，保证输入数据有效的在一个分布式的计算机集群里面安排，然后MaPPer和RedUCer函

11、数在其上有效的运行、处理，并最终汇总生成我们想要的处理结果。全部一切的细节，例如并行化、数据的安排、不同机器之间的计算误差，通通被隐蔽在程序库内。那么MapReduce究竟是什么样的一个过程呢？我们讲过，使用MaPRedUce,程序员必需供应一组输入数据，以及一个MaPPer和一个RedUCer函数。在这里，输入数据必需是个按(inpcit_key,input_value)方式组织的歹IJ表。KinPUjkey,iput-value),(input_key,input_value).mapper函数的任务是处理输入列表中的某一个单元数据：mapper(input_key,input_value

12、),并产生如下输出结果:(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(i

13、ntermediate_key,intermediate_value_list),并产生如下最终输出结果：|(output_key,output_value),(OUtPUJkev,output_valueh我们会举两个例子说明这一过程。第个例子是一个简洁的统计单词消失次数的小程序。其次个例子是Google曾经怎样使用MapReduceFrameWork来计算PageRanko第一个例子，假设我们要写一个小程序，来统计在几篇不同文章里全部消失过的单词各自总共消失的次数。我们应当怎么做呢？卜.面描述的采用MapReduce的方法确定不是大多数程序员第一感会想到的方法。但这种方法特别好的揭示了Ma

14、pReduce的基本思想。并且，这种方法很简洁被扩展处处理上千万甚至是上亿的文件数据，并且能够在一个分布的计算机集群里面运行。这可不是传统的方法能够轻易做到的。具体而言，假设我们有如下三个文本文件，a.txtzEtxt和c.txt：texxa.txt:Thequickbrownfox:overthelzygreydo9.textbtxt:Thatonexallstepforaxaaoneiatleapforacanklnd.textctxc:KrybadaIitclelab,Xcfleeurtogo.对于输入数据而言，inpuJkey就是文件名，inpuJVaIue就是一-个大的String,

15、包含的是文件内容。所以我们的输入数据看上去会是这样的：(*a.txt*,thequickbrownfoxjumped.),(T).txt,*that*sonesmallstepfotaman).(c.rtMaryhadIMleIamt,INAeeCe.1我们会写一个简洁的串行的mapper(fileNamezfiIeContent)S,这个函数做的事情很简洁，读入一个文本文件，把每一个遇到的单词当作一个新的intermediate_key,并赋其intermediate_value为1。将mapper函数处理文件a,我们会得到如下结果：t,th,1).(,utd,1)(ovL,l),gey11

16、.-311”将全部三个文件的处理结果放在一起，我们得到：(te,I),(uick,f1),(brovn,1),(,fM,1),1)，(,ove,1),(,tM,1)，(lzy1),(,qry,dofl三r1),(,BAty,l,X),(,1).(lttle,14aab,1).(,c,*,U,v,l)r(,wte.(,now,1Cd,”,vrywr,l)f(tat,”,(三ry,1),(v*nf,l)fr(*la*r(*w.(ur”,v(cp,1),Cfor,1,”,1)(,on,1),(,gnc,1),(*l*p“，(for,1然后将中间结果按intemediate_key归类:d:(lhad

17、:CLrnowt:(1bto:(1),lepl:Clhwhite*:(lhwas:1“ary：(1,Ibbrown:(I)ttXxyt:(lror*i:(I)r,tafx(I)rllttl:I)r9nalli:(lhtep:(1),everywhere*:(1eBAAlcind9:(lbventt(1)/an:(1),*t:1】Ibtflwe:(I)9trey:(lbdo,:(1,quick1x(lhce:(lrlrl)rthats:(1J)最终，由reducer(intermediate-keyzintermediate_valueist)对中间结果进行处理。它做的事也很简洁，仅仅是把某in

18、termediate_key对应的全部intermediate_value相加。我们于是得到最终结果：(n,”(,fox”，(,ovr,”,ConW,2).(,1),9.”,(,lt9,】).(,lMb,2).(g*nt,(,for,2(,3upedX),(,hl”,(,nov,1),(,eo,1),(,lea,(wte,”,(w2),(ry,2),(brom,1),(,8uretlr(tat,(lttle,1),(s*nkxnd*,1)wnt”，】)，(,2),(*flc,”，(,gxv,.1,*o,1),(iick,1),(,te3),Startingpoint:36415732Split

19、intwo:3641(5732Splitintwo:(36(41J5732Basecase:P61457(23Sortonmerge:1346(2357Sortonmerge:1233456其次个例子略微好玩一点，是个如何用程序解数独嬉戏的例子。数独就是在一个9*9的大九宫格内有9个3*3的小九宫格。里面有些格子已经填入了数字，玩家必需在剩下的空格里也填入1到9的数字，使每个数字在每行、每列以及每个小九宫格内只消失一次。这里作为举例说明,我们考虑一个简洁一点的状况:在一个4*4的格子里填入14的数字,使其在每行、每列以及每个2*2的格子里只消失一次。解数独嬉戏的算法可以有许多种。假如是人来解，

20、或许会依据上图的次序依次填入1,2,3到相应的格子当中。每填入一个新数字，都会重新按规章评估四周的空格，看能否按现有状况再填入一些数字。这个方法当然没错，不过看上去不太简洁并行化。下面介绍一个依据recursiveSPlitting的方法可以很简洁做到并行化的解法。1）首先，将二维的数独格子绽开成一个一维的数组。己经有数字的地方是原来的数字，空格子的地方填上OQ8*30040002mI2）接下来，从前到后对数组进行扫描。第一格是、3，已经有数字了，跳过。移动搜寻指针到下一格。300400023）其次格是、0,意味着我们需要填入个新的数字。这个新的数字有4种可能性：1,2,3,4。所以创建4个新

21、的搜寻分支：4）接下来依据现有的数字信息检查各个搜寻分支。明显，第三和第四个搜寻分支是非法的。由于我们在同一行中已经有了数字3和、4。所以忽视这两个分支。第一和其次条分支用现有的数字检查不出冲突,所以连续从这两个分支各派生出4条新的分支进行搜寻这个思路像极了我们之前的归并排序的例子,都是在算法运行的过程中不断产生出新的任务。所以实际上这也是一个TaskParalleliSm的例子。2.6PipelinePipeline也是一种比较常见的算法模式。通常，我们都会用汽车装配中的流水线、CPU中指令执行的流水线来类比的说明这一模式。它说的是我们会对一批数据进行有序、分阶段的处理，前一阶段处理的输出作

22、为下一阶段处理的输入。每一个阶段永久只重复自己这一阶段的任务，不停的接受新的数据进行处理。用一个软件上的例子打比方，我们要打开一批文本文件，将里面每一个单词的字母全部改成大写，然后写到一批新的文件里面去，就可以创建一条有3个Stage的流水线：读文件，改大写，写文件。Time0000HH000回叵回回回叵Pipeline模式的概念看上去很简洁理解，可是也不是每一个人都能一下子理解的那么透彻的。例如有这样一个问题：我们有一个for循环，循环体是一条有3个stage的pipeline,每个Stage的运行时间分别是10,40,和10个CPU的时钟间隔。请问这个for循环执行N次或许需要多长时间（N

23、是一个很大的数）？A. 60*NB. 10*NC. 60D. 40*N请认真思索并选择一个答案。：）答案是40*N0流水线总的执行时间是由它最慢的个Stage打算的。缘由请见下图。2.7Geometricdecomposition接下来这两个算法模式看上去都显得比较特别化，只针对某些特定的应用类型。Geometricdecomposition说的是对于一些线性的数据结构（例如数组），我们可以把数据切分成几个连续的子集。由于这种切分模式看上去和把一块几何区域切分成连续的几块很类似，我们就把它叫做Geometricdecomposition。Nciglibor-To-Ncighborcommuni

24、cation最常用的例子是分块矩阵的乘法。例如，为了计算两个矩阵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-wor

25、k-efficientParallelism这个模式的名字取得很怪异，也有其他人把它叫做RecursiveData。不过相比而言，还是这个名字更为贴切。它指的是这一类模式：有些问题的处理使用传统的方法，必需依靠于对数据进行有序的访问，例如深度优先搜寻，这样就很难并行化。但是假如我们情愿花费一些额外的计算量，我们就能够采纳并行的方法来解决这个问题。常用的一个例子是如下的”查找根节点的问题。假设我们有一个森林，里面每一个节点都只纪录了自己的前向节点，根节点的前向节点就是它自己。我们要给每一个节点找到它的根节点。用传统的方法，我们只能从当前节点动身，依次查找它的前向节点，直到前向节点是它自身。这种算

26、法对每一个节点的时间简单度是O(N)。总的时间简单度是N*O(N).假如我们能换种思路来解这个问题就可以将其并行化了。我们可以给每一个节点定义一个SUCCeSSor(后继结点)，SUCCeSSor的初始值都是其前向节点。然后我们可以同步的更新每一个节点的successor,令其等于successor的successor7,直到successor的值不再变化为止。这样对于上图的例子，最快两次更新，我们就可以找到每个节点的根节点了。这种方法能同时找到全部节点的根节点，总的时间简单度是N*log(N)o3.后记如前所述，并行编程中的设计模式”是一个仍在不断变化、进展的领域。这篇博文简要介绍了这一领域

27、当前的进呈现状,并选取八个常用的模式进行了介绍。我涉足并行编程领域不久,许多理解也并不深化。所以文章的缺点错误在所难免，真诚盼望能得到大家的批判指正。4.参考文献本文的写作参考了如下资源，可以作为进一步阅读的材料： UCBerkeley,APattemLdngUageforParallelProgramming Eun-GyuKimzParaIlelProgramminqPattemS JimBrownezDeSignPattemSforParallelCOmDUtation TimMattson,PattemSPaQllelProgramming MichaelNielsen,USingMaDRedUCetoCOmDUtePageRank AaterSulemanzParalIelProgramming:DoyouknowPiDeIineParallelism?标签：并行编程,设计模式