可重复使用的并行数据结构和算法

可重复使用的并行数据结构和算法9种可重复使用的并行数据结构和算法目录本专栏并未涉及很多公共语言运行库(CLR)功能的机制问题，而是更多介绍了如何有效使用您手头所具有的工具。身为一名程序员，必须做出很多决策，而选择正确的数据结构和算法无疑是最常见的，也是最重要的决策之一。错误的选择可能导致程序无法运行，而大多数情况下，则决定了性能的好坏。鉴于并行编程通常旨在改进性能，并且要难于串行编程，因此所作的选择对您程序的成功就更为重要。在本专栏中，我们将介绍九种可重复使用的数据结构和算法，这些结构和算法是许多并行程序所常用的，您应该能够轻松将它们应用到自己...

9种可重复使用的并行数据结构和算法目录本专栏并未涉及很多公共语言运行库(CLR)功能的机制问题，而是更多介绍了如何有效使用您手头所具有的工具。身为一名程序员，必须做出很多决策，而选择正确的数据结构和算法无疑是最常见的，也是最重要的决策之一。错误的选择可能导致程序无法运行，而大多数情况下，则决定了性能的好坏。鉴于并行编程通常旨在改进性能，并且要难于串行编程，因此所作的选择对您程序的成功就更为重要。在本专栏中，我们将介绍九种可重复使用的数据结构和算法，这些结构和算法是许多并行程序所常用的，您应该能够轻松将它们应用到自己的.NET软件中。专栏中每个示例随附的代码都是可用的，但尚未经过完全定型、测试和优化。这里列举的模式虽然并不详尽，但却代表了一些较为常见的模式。如您所见，很多示例都是互为补充的。在开始前，我想还是先介绍一些相关内容。Microsoft.NETFramework提供了几个现有的并发基元。虽然我要为您讲解如何构建自己的基元，但实际上现有基元是足以应付大多数情况的。我只是想说某些可选的方案有时也是有参考价值的。此外，了解这些技巧如何应用于实际操作也有助于加深您对并行编程的整体理解。在开始讲解前，我假定您对现有基元已经有了一个基本的了解。您也可以参阅《MSDN杂志》2005年8月版的文章“”，以全面了解其概念。一、倒计数锁存(CountdownLatch)Semaphore之所以成为并发编程中一种较为知名的数据结构，原因是多方面的，而并不只是因为它在计算机科学领域有着悠久的历史（可以追溯到19世纪60年代的操作系统设计）。Semaphore只是一种带有一个计数字段的数据结构，它只支持两种操作：放置和取走（通常分别称为P和V）。一次放置操作会增加一个semaphore计数，而一次取走操作会减少一个semaphore计数。当semaphore计数为零时，除非执行一项并发的放置操作使计数变为非零值，否则任何后续的取走尝试都将阻塞（等待）。这两种操作均为不可再分(atomic)操作，并发时不会产生错误，能够确保并发的放置和取走操作有序地进行。Windows具有基础内核和对semaphore对象的Win32支持（请参阅CreateSemaphore和相关API），并且在.NETFramework中这些对象可以通过类公开到上层。Mutex和Monitor所支持的临界区，通常被认为是一种特殊的semaphore，其计数会在0和1之间来回切换，换句话说，是一个二进制的semaphore。另外还有一种“反向semaphore”也是非常有用。也就是说，有时您需要数据结构能够等待数据结构计数归零。Fork/join式并行模式在数据并行编程中是极为常见的，其中由单个“主”线程控制执行若干“辅助”线程并等待线程执行完毕。在这类情况下，使用反向semaphore会很有帮助。大多数时候，您其实并不想唤醒线程来修改计数。因此在这种情况下，我们将结构称为倒计数“锁存”，用来表示计数的减少，同时还表明一旦设置为“Signaled”状态，锁存将保持“signaled”（这是一个与锁存相关的属性）。遗憾的是，Windows和.NETFramework均不支持这种数据结构。但令人欣慰的是，构建这种数据闭锁并不难。要构建倒计数锁存，只需将其计数器初始值设为n，并让每项辅助任务在完成时不可再分地将n减掉一个计数，这可以通过为减量操作加上“锁”或调用来实现。接下来，线程可以不执行取走操作，而是减少计数并等待计数器归零；而当线程被唤醒时，它就可以得知已经有n个信号向锁存注册。在while(count!=0)循环中，让等待的线程阻塞通常是不错的选择（这种情况下，您稍后将不得不使用事件），而不是使用旋转。publicclassCountdownLatch{privateintm_remain;privateEventWaitHandlem_event;publicCountdownLatch(intcount){m_remain=count;m_event=newManualResetEvent(false);}publicvoidSignal(){if(refm_remain)==0)();}publicvoidWait(){();}}这看上去极为简单，但要正确运用还需要技巧。稍后我们将通过一些示例来讲解如何使用这种数据结构。请注意，此处所示基本实现还有很多可以改进地方，例如：在事件上调用WaitOne之前添加某种程度的旋转等待、缓慢分配事件而不是在构造器中进行分配（以防足够的旋转会避免出现阻塞，如本专栏稍后介绍的ThinEvent演示的那样）、添加重置功能以及提供Dispose方法（以便在不再需要内部事件对象时将对象关闭）。二、可重用旋转等待(SpinWait)虽然忙碌等待(busywaiting)更容易实现阻塞，但在某些情况下，您也许的确想在退回到真正的等待状态前先旋转(spin)一段时间。我们很难理解为何这样做会有帮助，而大多数人之所以一开始就避免旋转等待，是因为旋转看上去像是在做无用功；如果上下文切换（每当线程等待内核事件时都会发生）需要几千个周期（在Windows上确实是这样），我们称之为c，并且线程所等待的条件出现的时间少于2c周期时间（1c用于等待自身，1c用于唤醒），则旋转可以降低等待所造成的系统开销和滞后时间，从而提升算法的整体吞吐量和可伸缩性。如果您决定使用旋转等待，就必须谨慎行事。因为如果这样做，您可能需要注意很多问题，比如：要确保在旋转循环内调用，以提高Intel超线程技术的计算机上硬件对其他硬件线程的可用性；偶尔使用参数1而非0来调用，以避免优先级反向问题；通过轻微的回退(back-off)来引入随机选择，从而改善访问的局部性（假定调用方持续重读共享状态）并可能避免活锁；当然，在单CPU的计算机最好不要采用这种方法（因为在这种环境下旋转是非常浪费资源的）。SpinWait类需要被定义为值类型，以便分配起来更加节省资源。现在，我们可以使用此算法来避免前述CountdownLatch算法中出现的阻塞。publicstructSpinWait{privateintm_count;privatestaticreadonlybools_isSingleProc===1);privateconstints_yieldFrequency=4000;privateconstints_yieldOneFrequency=3*s_yieldFrequency;publicintSpin(){intoldCount=m_count;m_count+=(s_isSingleProcs_yieldFrequency:1);intcountModFrequency=m_count%s_yieldFrequency;if(countModFrequency>0)((int)(1+(countModFrequency*0.05f)));else(m_count<=s_yieldOneFrequency0:1);returnoldCount;}privatevoidYield(){(m_count0){if()>=s_spinCount)();}}不可否认，选择频率和旋转计数是不确定的。与Win32临界区旋转计数类似，我们应该根据测试和实验的结果来选择合理的数值，而且即使合理的数值在不同系统中也会发生变化。例如，根据MicrosoftMediaCenter和Windowskernel团队的经验，MSDN文档建议临界区旋转计数为4,000，但您的选择可以有所不同。理想的计数取决于多种因素，包括在给定时间等待事件的线程数和事件出现的频率等。大多数情况下，您会希望通过等待事件来消除显式让出时间，如锁存的示例中所示。您甚至可以选择动态调整计数：例如，从中等数量的旋转开始，每次旋转失败就增加计数。一旦计数达到预定的最大值，就完全停止旋转并立即发出WaitOne。逻辑如下所示：您希望立即增加达到预定的最大周期数，但却无法超过最大周期数。如果您发现此最大值不足以阻止上下文切换，那么立即执行上下文切换总的算来占用的资源更少。慢慢您就会希望旋转计数能够达到一个稳定的值。三、屏障(Barrier)屏障，又称集合点，是一种并发性基元，它无需另一“主”线程控制即可实现各线程之间简单的互相协调。每个线程在到达屏障时都会不可再分地发出信号并等待。仅当所有n都到达屏障时，才允许所有线程继续。这种方法可用于协调算法(cooperativealgorithms)，该算法广泛应用于科学、数学和图形领域。很多计算中都适合使用屏障，实际上，甚至CLR的垃圾收集器都在使用它们。屏障只是将较大的计算分割为若干较小的协作阶段(cooperativephase)，例如：constintP=...;Barrierbarrier=newBarrier(P);Data[]partitions=newData[P];.}您会很快发现在这种情况下是可以使用倒计数锁存的。每个线程都可以在调用Signal后立即调用Wait，而不是调用Await；在到达屏障后，所有线程都会被释放。但这里存在一个问题：前面所讲的锁存并不支持多次重复使用同一对象，而这却是所有屏障都支持的一个常用属性。实际上，上述示例就需要使用此属性。您可以通过单独的屏障对象来实现这一点，但这样做非常浪费资源；而由于所有线程每次只出现在一个阶段，因此根本无需多个屏障对象。要解决这个问题，您可以使用相同的基础倒计数锁存算法来处理减少计数器计数、发信号指示事件、等待等方面的问题，从而将其扩展为可重复使用。要实现这一点，您需要使用所谓的感应反向屏障(sensereversingbarrier)，该屏障需要在“偶数”和“奇数”阶段之间交替。在交替阶段需要使用单独的事件。usingSystem;;publicclassBarrier{privatevolatileintm_count;privateintm_originalCount;privateEventWaitHandlem_oddEvent;privateEventWaitHandlem_evenEvent;privatevolatileboolm_sense=false;publicBarrier(intcount){m_count=count;m_originalCount=count;m_oddEvent=newManualResetEvent(false);m_evenEvent=newManualResetEvent(false);}publicvoidAwait(){boolsense=m_sense;if(m_count==1||(refm_count)==0){m_count=m_originalCount;m_sense=!sense;if(sense==true){if(m_count==1||(refm_count)==0){m_count=m_originalCount;m_sense=!sense;if(sense==true){privateEventWaitHandlem_eventObj;privateconstints_spinCount=4000;publicvoidSet(){m_state=1;();if(m_eventObj!=null)();}publicvoidReset(){m_state=0;if(m_eventObj!=null)();}publicvoidWait(){SpinWaits=newSpinWait();while(m_state==0){if()>=s_spinCount){if(m_eventObj==null){ManualResetEventnewEvent=newManualResetEvent(m_state==1);if(refm_eventObj,newEvent,null)==null){if(m_state==1)();}else{();}}();}}}}这基本上反映了m_state变量中的事件状态，其中值为0表示未设置，值为1表示已设置。现在，等待一个已设置事件耗费资源是很低的；如果m_state在Wait例程的入口处值为1，我们会立即返回，无需任何内核跳转。但如果线程在事件设置完毕之前进入等待状态，处理上就需要很多技巧。要等待的首个线程必须分配一个新的事件对象，并对其进行比较后交换至m_eventObj字段中；如果CAS失败，则意味着其他等待者对事件进行了初始化，所以我们只可重复使用它；否则就必须重新检查自上次看到m_state后其值是否发生更改。不然的话，m_state的值也许会为1，那么m_eventObj就无法收到信号通知，这将导致在调用WaitOne时出现死锁。调用Set的线程必须首先设置m_state，随后如果发现值为非空的m_eventObj，就会调用其上的Set。这里需要两个内存屏障：需要注意的是切不可提前移动m_state的第二次读取，我们会使用设置m_eventObj来保证这点；在写入m_eventObj之前，不可移动Set中的对m_eventObj的读取（这是一种在某些Intel和AMD处理器以及内存模型上出现的奇怪的合法转换，并未显式调用）。并行重置事件通常是不安全的，因此调用方需要进行额外的同步化。现在您可以轻松在其他地方使用它，例如在上述的CountdownLatch示例和队列示例中，而且通常这样做可以大幅度提升性能，尤其是当您可以巧妙地运用旋转时。我们上面介绍了一个技巧性很强的实现方式。请注意，您可以使用单个标志和监视器来实现自动和手动重置类型，这远比本示例简单（但效率方面有时会不及本例）。无锁定LIFO堆栈使用锁定构建线程安全的集合是相当直接明了的，即使限制和阻塞方面会有些复杂（如上面看到的）。但是，当所有协调均通过简单的后进先出(LIFO)堆栈数据结构实现时，使用锁定的开销会比实际所需的高。线程的临界区（即保持锁定的时间）有开始点和结束点，其持续时间可能会跨越许多指令的有效期。保持锁定可阻止其他线程同时进行读取和写入操作。这样做可以实现序列化，这当然是我们所想要的结果，但严格地讲，这种序列化要比我们所需的序列化强很多。我们的目的是要在堆栈上推入和弹出元素，而这两项操作只需通过常规读取和单一的比较－交换写入即可实现。我们可以利用这点来构建伸缩性更强的无锁定堆栈，从而不会强制线程进行没必要的等待。我们的算法工作方式如下。使用有链接的列表代表堆栈，其标头代表堆栈的顶端，并存储在m_head字段中。在将一个新项推入堆栈时，要构造一个新节点，其值等于您要推入堆栈的值，然后从本地读取m_head字段，并将其存储至新节点的m_next字段，随后执行不可再分的来替换堆栈当前的头部。如果顶端自首次读取后在序列中的任何点发生更改，CompareExchange都会失败，并且线程必须返回循环并再次尝试整个序列。弹出同样是比较直截了当的。读取m_head并尝试将其与m_next引用的本地副本交换；如果失败，您只需一直尝试，如图8中所示。Win32提供了一种名为SList的类比数据结构，其构建方法采用了类似的算法。Figure8无锁定堆栈复制代码publicclassLockFreeStack{privatevolatileStackNodem_head;publicvoidPush(Titem){StackNodenode=newStackNode(item);StackNodehead;do{head=m_head;=head;}while(m_head!=head||(refm_head,node,head)!=head);}publicTPop(){StackNodehead;SpinWaits=newSpinWait();while(true){StackNodenext;do{head=m_head;if(head==null)gotoemptySpin;next=;}while(m_head!=head||(refm_head,next,head)!=head);break;emptySpin:();};}}classStackNode{internalTm_value;internalStackNodem_next;internalStackNode(Tval){m_value=val;}}请注意，这是理想的并发控制的一种形式：无需阻止其他线程存取数据，只需抱着会在争用中“胜出”的信念继续即可。如果事实证明无法“胜出”，您将会遇到一些变化不定的问题，例如活锁。这种设计方案还表明您无法确保能够实现FIFO调度。根据概率统计，系统中所有线程都将向前推进。而实际上从整体来看，系统进度总是向前推进的，因为其中一个线程的失败总是意味着至少有一个其他线程是推进的（这是调用该“无锁定”的一个条件）。有些情况下，当CompareExchange无法避免m_head大量争用内存时，使用指数回退算法会很有用。同时，我们还对堆栈变空的情况采取了相当直截了当的方法。我们只是一直旋转，等待有新项目推入。将Pop重新写入处于非等待状态的TryPop是很简单易懂的，但是要利用事件进行等待则会有一些复杂。这两个功能都是十分重要的，所以留给那些喜欢动手的读者作为练习之用。我们为每个Push都分配了对象，这让我们无需担心所谓的ABA问题。在内部重复使用已从列表中弹出的节点就会导致ABA问题。开发人员有时会尝试将节点集中到池中以减少对象分配的数目，但这样做是有问题的：结果会是，即使对m_head执行了大量干扰性写入操作，一个不可再分割的操作也可以实现，但实际上却是不正确的。（例如：线程1读取节点A，然后由线程2将节点A删除并置入池中；线程2将节点B作为新的头推入，然后节点A从池中返回到线程2并被推入；随后，线程1会成功执行CompareExchange，但现在作为头的A已经与先前所读取的不同了。）尝试以本机C/C++编写此算法时也会出现类似问题；因为一旦地址被释放，内存分配器就会立即重复使用这些地址，节点会被弹出并释放，然后该节点的地址会被用于新的节点分配，结果导致与上面相同的问题。接下来我们不再讨论ABA，有关它的详细介绍我们可以从其他的资源获得。最后，可以使用类似的无锁定技术编写一个FIFO队列。它的优势在于并行推入和弹出的线程之间并不一定发生冲突，而在上述LockFreeStack中，推入者和弹出者始终会争用同一m_head字段。然而，这种算法相当复杂，如果您好奇的话，我推荐您阅读和在1996年撰写的文章“”。循环分块循环分块是指对循环的输入范围或数据进行分区，并将每个分区分配给单独的线程以实现并发。这是某些编程模型（例如OpenMP）实现并行性的一项基本技术（请参阅），通常称为并行Forall循环，是从高性能的FORTRAN术语中得到启发而创造的。无论如何，范围都只是一组索引：复制代码for(inti=0;ia,intp){ForAll(null,from,to,null,a,p);}publicstaticvoidForAll(IListdata,Actiona,intp){ForAll(data,0,,a,null,p);}privatestaticvoidForAll(IListdata,intfrom,intto,Actiona0,Actiona1,intp){intsize=from-to;intstride=(size+p-1)/p;CountdownLatchlatch=newCountdownLatch(p);for(inti=0;i（类似于C#中的Foreach循环）。两者都转发到同一帮助程序重载，重载可调用从给定索引的列表传递元素这一操作，或者传递索引本身。您应使用第一个重载（通常在此加入一个普通For循环）。例如，下面的代码复制代码for(inti=0;i<10;i++){S;}将变为：复制代码(0,10,delegate(inti){S;},;现在可以使用第二个重载（通常在此加入一个C#foreach循环），这样，复制代码Listlist=...;foreach(Teinlist){S;}将变为：复制代码(list,delegate(Te){S;},;您需要谨慎以确保S中的语句不会写入共享内存；否则您需要向并行版本添加合适的同步操作。当然可以编写相应版本来支持IEnumerable、以其他方式对迭代空间进行分区等（为了节省空间，本专栏省略了这些内容）。在本示例中，在n项子任务的持续时间内调用线程被“浪费”了。更好的方法是使用调用线程来运行其中一项任务，然后在其完成时加入其他任务。没有必要通过扩展ForAll方法来执行此操作。并行分拆有一类操作可使用分拆（又称为折叠或聚合）来执行，其中会以某种方式将许多值进行组合以便生成单一输出。一般分拆的工作方式如下。使用一个二元运算符（即包含两个参数的函数），并对照向量或一组大小为n的元素从左至右对其进行计算。对于j=0至n–1，调用该二元运算符，作为输入传递至jth迭代，并将在元素j–1上调用运算符得到的输出作为第一个参数，将jth元素本身作为第二个参数。由于没有预先给定的值可用，因此会将一个特殊的种子值用作第0个元素的第一个参数。然后使用最终（可选）结果选择器将中间值转换为最终结果。我们来看一个示例。如果二元运算符为+，输入为包含5个元素{1,2,3,4,5}的向量，那么展开的计算应类似于((((1+2)+3)+4)+5)。如果将此展开式转换为函数调用格式，则类似于以下形式（假定种子值为0）：+(+(+(+(+(0,1),2),3),4),5)换句话说，您只需计算所有输入数字的总和即可。这称为总和分拆。有种直接的方法可以将这种一般化的算法转换为串行算法，如下所示：复制代码delegateTFunc(Targ0,Targ1);TReduce(T[]input,Tseed,Funcr){Tresult=seed;foreach(Teininput)result=r(result,e);returnresult;}调用它时，您只需求得一组数字的和即可，如下所示（在C#中）：复制代码int[]nums=...somesetofnumbers...;intsum=Reduce(nums,0,(x,y)=>x+y;);所有这些内容都很抽象，但除了求和之外，还有很多操作也可以通过拆分表示，如图10中所示。Figure10表示为拆分的操作种子二元运算符结果选择器计数0(a,b)=>a+1N/A和0(a,b)=>a+bN/A最小值NaN(a,b)=>aa>ba:bN/A平均{0,0}(a,b)=>new{a[0]+b,a[1]+1}(a)=>a[0]/a[1]如果给定上面的nums数组，我们就可以使用拆分例程找到数组的最小值和最大值：复制代码intmin=Reduce(nums,,(x,y)=>xx>yx:y;);（省略Count是因为必须对部分结果求和，而这需要两个单独的二元运算符；省略Average是因为它还需要一些其他步骤。）您可以使用与讨论循环分块时论述的技术相类似的技术来分割输入数据和并行执行拆分。每个分区都将计算其自己的中间值，然后我们会使用与计算中间值相同的运算符把这些值合并为单个最终值。这样为何可行呢因为上述的所有操作都是相关联的；回想一下初等数学中学过的知识：关联性二元运算符+意味着(a+b)+c=a+(b+c)；也就是说，计算顺序不会影响计算结果的正确性。例如，考虑一下总和拆分。如果您将输入数据{1,2,3,4}分为两个分区（{1,2}和{3,4}），那么由于+是关联的，因此当您将各独立求和的结果加到一起时，结果是保持不变：(1+2)+(3+4)=((((1+2)+3)+4).实际上，任何非连续的输入分区都会产生正确的结果。图11所展示的一般化Reduce方法将种子值和二元运算符作为参数，它使用的是前面所述的跨距分区法。Figure11Reduce方法复制代码publicdelegateTFunc(Targ0,Targ1);publicstaticTReduce(IListdata,intp,Tseed,Funcr){T[]partial=newT[p];intstride=+p-1)/p;CountdownLatchlatch=newCountdownLatch(p);for(inti=0;i

                    本文档为【可重复使用的并行数据结构和算法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

可重复使用的并行数据结构和算法

你可能还喜欢