并行算法

b · 发表于 2004-5-28 03:09:27

<

>随着并行处理硬件性能的迅速提高，人们对并行算法的兴趣也日益增加。所谓并行算法是指一次可执行多个操作的算法。对并行算法的研究现在已发展为一个独立的研究领域。很多用串行算法解决的问题也已经有了相应的并行算法。在本文中，我们将阐述一些简单的并行算法以说明一些基本概念和技术。
<

>这里介绍的并行算法将用一种流行的理论模型即并行随机存取计算机(PRAM)来描述。很多关于数组、表、树和图的并行算法都可以很容易地用PRAM模型来描述。如果一个PRAM算法在性能上超过另一个PRAM算法，则当两个算法在一台实际的并行计算机上运行时其相对性能不会有很大变化。
<H2>

RAM模型</H2>
图1说明了PRAM的基本结构。其中有n个普通的串行处理器p0,p1,...,pn-1共享一个全局存储器。所有处理器都可以“并行地”(同时)从全局存储器读出信息或向全局存储器写入信息。各处理器也可以并行地执行各种算术和逻辑操作。
<IMG src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/fig1.gif" border=0>
图l PRAM的基本构造
在PRAM模型中关于算法性能的最关键的一点是：假设运行时间可以用算法执行的并行的存储器存取次数来衡量。这一假设是对普通的RAM模型的直接推广，并且用存储器存取次数来衡量运行时间对PRAM模型也是很适合的。这一简单的假设对于我们研究并行算法有很大帮助，不过真正的并行计算机并不能做到在单位时间内对全局存储器并行地执行存取操作：对存储器进行存取操作所需的时间随着并行计算机中处理器数目的增加而相应增加。
然而，对于以任意方式对数据进行存取的并行计算机来说，可以证明存取操作为单位时间的假设是成立的。实际中的并行计算机都包含一个通讯网络以便支持一个抽象的全局存储器。与算术操作等其他操作相比，通过网络存取数据是相当慢的。因此，计算出两种并行算法所执行的并行的存储器存取次数就可以对其相对性能作出精确的估计。实际的计算机与 PRAM的单位时间抽象不一致，主要在于某种存储器存取模式可能比其他模式快。但是，作为一种近似描述，PRAM模型的单位时间存取的假设还是合乎情理的。
并行算法的运行时间既依赖于执行算法的处理器数目，也依赖于输入问题本身的规模。一般来说，在分析PRAM算法时我们必须同时讨论其时间和处理器数目，这与串行算法完全不同，在串行算法中我们主要集中于对时间的分析。当然，我们在算法使用的处理器数目与其运行时间之间要进行权衡。第3节中将会讨论这一权衡问题。
<H2>并发存储器存取方式与互斥存储器存取方式</H2>
并发读算法是指在算法执行过程中多处理器可以同时对共享存储器的同一位置进行读操作的一种PRAM算法。互斥读算法是指在算法执行中任何两个处理器都不能同时对共享存储器的同一位置进行读操作的一种PRAM算法。
类似地，我们根据多处理器能否在同一时刻对共享存储器的同一位置执行写操作也可以把PRAM算法划分为并发写算法和互斥写算法。我们所遇到的算法类型一般采用以下缩写形式：
<UL>
<LI>EREW：互斥读且互斥写
<LI>CREW：并发读且互斥写
<LI>ERCW：互斥读且并发写
<LI>CRCW：并发读且并发写 </LI></UL>
在这些算法类型中，最常见的是EREW和CRCW。仅支持EREW算法的PRAM称为EREW PRAM，仅支持CRCW算法的PRAM称为CRCW PRAM。一个CRCW PRAM当然能够执行EREW算法，但EREW PRAM不能直接支持CRCW算法所要求的并发存储器存取操作。EREW PRAM的底层硬件相对来说比较简单，并且因为它无需对相互冲突的存储器读写操作进行处理，因此运行速度也比较快。如果单位时间假设能相当精确地衡量算法的性能，则CRCW PRAM就需要更多的硬件支持，但可以证明它能够提供一种比EREW PRAM更直接的操作设计模型。
在剩下的两种算法类型CREW和ERCW中，有关的论文书籍更重视CREW。但是从实际应用的角度来看，要支持并发写操作并不比支持并发读操作更困难，在本文中，如果算法包含并发读或并发写操作，我们一般就把它作为CREW而不再进行细分。我们将在第2节中更详细地讨论这一区分方法。
在CREW算法中当多处理器对同一存储器位置进行写操作时，如果我们不作详细论述，并行写的结果就没有完备的定义。在本文中，我们使用公用CREW模型：当多个处理器对存储器的同一位置进行写操作时，它们写入的必须是公用值(相同的值)。在处理这个问题的有关文献中，在与上述不同的假设前提下存在着几种可选择的PRAM类型，包括：
<UL>
<LI>任意型：实际存储的是写入的这些值中的一个任意值；
<LI>优先级型：存储的是具有最高优先级的处理器所写入的值；
<LI>组合型：实际存储的值是写入值的某个特定组合。 </LI></UL>
在最后一种情况中，特定组合是指满足结合律的某种函数，如加法(存储写入值的和)或最大值函数(仅存储写入值中的最大值)。
<H2>同步与控制</H2>
PRAM算法必须高度同步以保证其正确执行。如何获得这一同步特征？另外，PRAM算法中的处理器常常必须测试循环的终止条件，而这一终止条件又往往取决于所有处理器的状态。如何实现这种控制功能？
许多并行计算机采用了一种连接各处理器的控制网络，以帮助实现同步和对终止条件进行测试。在特定情况下，控制网络实现这些功能的速度可以与路径选择网络实现对全局存储语句的速度一样快。
为方便起见，我们假设各个处理器固有严格同步的特征。所有处理器同时执行相同的语句。处理器执行代码的进度也保持一致。当我们学习第一个并行算法时，我们将指出在何处我们需要假设处理器是同步执行的。
为了能对依赖于所有处理器状态的并行循环终止条件进行测试，我们假定控制网络能够在O(1)的运行时间内对并行的终止条件进行测试。在一些文件中的EREW PRAM模型没有作这一假设，并且测试循环终止条件所需的(对数)时间必定包含在整个运行时间内。在第2节中我们将看到，CRCW PRAM不需要用控制网络来测试终止条件：它们通过采用并发写操作就能在O(1)的运行时间内测试一个并行循环是否终止。
<H2>本文概述</H2>
<H3><a href="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/chapter1.htm" target="_blank" >第1节指针转移技术</A></H3>
<BLOCKQUOTE>
这一技术提供了一种并行地控制表操作的快速方法。我们将介绍如何运用指针转移技术对表执行前缀计算，如何尽快把表的算法改写为适用于树的算法。</BLOCKQUOTE>
<H3><a href="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/chapter2.htm" target="_blank" >第2节 CRCW算法和EREW算法</A></H3>
<BLOCKQUOTE>
对CRCW算法和EREW算法的相对性能作了比较，并说明了采用并发存储器有取操作可以增加算法解决问题的能力。</BLOCKQUOTE>
<H3><a href="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/chapter3.htm" target="_blank" >第3节 Brent定理</A></H3>
<BLOCKQUOTE>
该定理说明如何用PRAM来有效地模拟组合电路。这一节还讨论了关于工作效率的重要问题。并给出了把p个处理器的PRAM算法有效地转化为p个处理器的PRAM算法的条件。</BLOCKQUOTE>
<H3>第4节高效的并行前缀计算</H3>
<BLOCKQUOTE>
重新讨论了对链表执行前缀计算的问题，并说明如何运用一种随机算法来高效率地进行计算。</BLOCKQUOTE>
<H3>第5节确定的打破对称性问题</H3>
<BLOCKQUOTE>
讨论了如何运用一种确定的算法在远小于对数时间的运行时间内并行地打破对称性。</BLOCKQUOTE>
本文中阐述的并行算法主要来之于图论的研究领域。它们仅仅是从现存的大量并行算法中选出少量代表算法。但是，本文中所介绍的一些技术却是很有代表性的技术，它们也适用于计算机科学的其他领域中的并行算法。

b · 发表于 2004-5-28 03:09:43

<H2>第一节指针转移</H2><

>在各种PRAM算法中，涉及指针的算法是非常有趣的。在本节中，我们要讨论一种称为指针转移的技术，应用这一技术可以获得有关链表操作的快速算法。我们要特别介绍一种O(lgn)时间的算法，该算法用于计算n个对象组成的链表中每个对象到表尾的距离。然后，我们对该算法进行修改，以在O(lgn)的时间内对n个对象组成的链表执行“并行前缀”计算。最后，我们探讨一种把有关树的问题转化为关于链表问题的技术，后一种问题可用指针转移技术来解决。本节中的所有算法都是EREW算法：不需要对全局存储器进行并发存取。<UL><LI><a href="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/chapter1_1.htm" target="_blank" >1.1 表排序</A> <LI><a href="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/chapter1_2.htm" target="_blank" >1.2 列表的并行前缀</A> <LI><a href="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/chapter1_3.htm" target="_blank" >1.3 欧拉回路技术</A> </LI></UL>

b · 发表于 2004-5-28 03:10:04

<H3>1.1 表排序</H3>
<

>我们介绍的第一个并行算法是有关列表的。列表在PRAM中的存储方式与普通的 RAM相同。为了便于并行地对列表中的对象进行操作，我们为每个对象分配一个“响应”处理器。假定处理器数目与列表中的对象一样多，并且第i个处理器负责处理第i个对象。例如，图2(a)说明了一个由对象序列<3,4,6,1,0,5>组成的链表。由于每个对象对应于一个处理器，所以表中的每个对象都可由其响应处理器在O(1)的时间内对其进行操作。
<

align=center><IMG src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/fig2a.gif">
<

align=center>(a)
<IMG src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/fig2b.gif">
(b)
<IMG src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/fig2c.gif">
(c)
<IMG src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/fig2d.gif">
(d)
图2 运用指针转移在O(lgn)时间内求出n个对象组成的链表中每个对象到表尾的距离
假定已知一个包含n个对象的单链表L，我们希望计算出表L中的每个对象到表尾的距离。更形式地说，如果next是指针域，我们希望计算出表中每个对象i的值d，使得：
<BLOCKQUOTE>
<IMG src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/Eqn1.gif"></BLOCKQUOTE>
我们把这一计算d值的问题称为表排序问题。
解决表排序问题的一种方法是从表尾把距离往回传输。因为表中从末端开始的第k个对象必须等到其后的k-1个对象确定了它们到表尾的距离后才能确定其自身到表尾的距离，所以这一方法需要O(n)的运行时间。实际上，这一解决方法是一种串行算法。
下面的代码给出了一种有效的并行算法，其运行时间仅为O(lgn)。<CODE class=pseudocode><PRE>下面的算法使用了伪代码进行描述，请参见<a href="http://iprai.hust.edu.cn/icl2002/algorithm/algorithm/pseudocode.htm" target="_blank" >伪代码的使用</A></PRE><PRE>
List-Rank(L)</PRE>
1. for 每个处理器i，并行地执行
2. do if next=NIL
3. then d←0
4. else d←1;
5. while 存在一个对象i，满足next≠NIL
6. do for 每个处理器i，并行地执行
7. do if next≠NIL 
8. then d←d+d[next];
9. next←next[next];
</CODE>代操作以前列表的状态。在第一次迭代中，表中开头5个对象的指针不为NIL，所以由其响应处理器分别执行第8-9行的操作。其操作结果见图中的(b)部分。在第二次迭代中，只有前面4个对象的指针不是NIL，该次迭代后的结果见图中的(c)部分，在第3次迭代中，只对表中开头2个对象进行操作，最后所有对象的指针均变为NIL，其结果见图中的(d)部分。
在第9行中，对所有非NIL指针next，我们置next← next[next]，它实现的设计思想称为指针转移。注意，由于指针转移操作改变了指针域，因而也就破坏了链表的结构。如果必须保持链表结构，则我们可以对next指针做备份并使用该备份来计算距离的值。
正确性
List-Rank维持以下不变条件：在第5-9行while循环中每次迭代开始时，对每个对象i，如果对以i作表头的子表的各个d值求和，就得到了从i到初始表L尾的正确距离。例如，在图2(b)中，对象3作表头的子表是序列<3,6,0>，其d值分别为2,2,和1，它们的和为5，这就是该对象到初始表尾的距离。上述不变条件成立的原因是当每个对象与其在表中的后继进行“拼接”时，它把其后继的d值加到自身的d值中。
必须注意，为使指针转移算法能正确执行，必须使并行的存储器存取保持同步。每次执行第9行代码可以对数个next指针进行更新。我们要求赋值式右边的存储器读操作（读 next[next]）出现在赋值式左边的任何存储器写操作（写next）之前。
现在让我们看看List-Rank是一个EREW算法的原因。因为每个处理器至多响应一个对象，所以第2-7行的每个读操作和写操作都是互斥的，第8-9行的写操作也是如此。请注意指针转移维持下列不变条件：对任意两个不同的对象i和j，或者有next≠next[j]，或者有next=next[j]=NIL。对初始表这一条件显然成立，并且通过第9行操作该条件一直保持成立。因为所有非NIL的next值都是不同的，所以第9行中的读操作也是互斤的。
如果所有读操作都是互斥的，我们就无需假设在第8行中执行了某种同步操作。特定地，我们要求所有处理i只能先读d，然后才能读d[next]。有了这种同步要求，如果一个对象i有next≠NIL，并且有另外一个对象j指向i（即next[j]=i），则第1个读操作为处理器i取得值d，然后第 2个读操作才能为处理器j取得值d。因此，所以 List-Rank是一种EREW算法。
从现在起，我们忽略有关同步的细节描述并假定PRAM与其伪代码设计环境都以始终如一的同步方式进行操作，所有处理器可同时执行读操作与写操作。
分析
我们现在来证明如果表L中有n个对象，则List-Rank的运行时间为O(lgn)。因为初始化占用的时间为O(1)，并且while循环中的每次迭代所需时间也是O(1)，所以只需证明总共有「lgn」次迭代操作就可以了。我们注意到关键是：指针转移的每一步把每个表转化为交错的两个表：一个表由偶数位置上的对象构成，另一个表由奇数位置上的对象构成。因此每个指针转移步使表的数目增加一倍而使其长度减为一半。因此，在「lgn」次迭代结束时，所有的表均包含一个对象。
第5行中的终止条件测试所需时间为O(1)。事实上，只要在循环体内用一个变量记录next≠NIL的i的个数，就可以在O(1)的时间内完成第5行的测试。
除了并行的运行时间外，对于并行算法还存在另一种有趣的性能评价方法。我们定义并行算法执行的<DFN>工作</DFN>为其运行时间与所需的处理器数目的积。从直观上看，工作是一个串行RAM模拟并行算法时所执行的计算量。
过程List-Rank执行了O(nlgn)的工作，这是因为它需要n个处理器且其运行时间为O(lgn)。关于表排序问题的简单的串行算法的运行时间为O(n)，这说明List-Rank执行的某些工作并不是必需的，但两者仅差一个对数因子。
已知一个PRAM算法A和求解同一个问题的另一种(串行或并行)算法B，如果A执行的工作不超过B执行的工作乘以一个常数因子，我们就说算法A对于算法B来说高效。如果算法A对于串行RAM上最好的算法来说是高效的，我们就更简单地称PRAM算法A高效。因为在串行RAM上关于表排序的最好算法的运行时间为O(n)，所以List-Rank不是高效的算法。我们将在第4节中阐述一个关于表排序的高效的并行算法。

b · 发表于 2004-5-28 03:10:47

<H3>1.2 列表的并行前缀</H3>
<

>指针转移技术远不止应用于表排序问题。在算术电路中可以运用“前缀”计算来执行快速二进制加法。现在我们来探讨如何运用指针转移技术来进行前缀计算。有关前缀问题的EREW算法对由n个对象组成的表的运行时间为O(lgn)。
<

>前缀计算是根据二进制中满足结合律的运算符Ä来决定的。计算时输入为序列<x1,x2,...,xn>并产生一个输出序列<y1,y2,...,yn>，满足y1=x1，并且对k=2,3,...,n，有
<BLOCKQUOTE>
<

><IMG src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/Eqn2.gif"></BLOCKQUOTE>
换句话说，每个yk是序列的头k个元素一起“相乘”而得到的。因此才有“前缀”这一意义。
作为前缀计算的一个实例，假定n个对象组成的表中的每个元素包含的值为1，并设Ä表示普通加法运算。因为对k=1,2,...,n，表中第k个元素包含的值为xk=1。所以前缀计算后的结果为yk=k，即为第k个元素的下标。因此，进行表排序的另一种方法是先把表颠倒(可以在O(1)的时间内完成)，执行前缀计算，然后把计算所得的每个值减1。
我们现在说明EREW算法是如何在O(lgn)的运行时间里对n个对象组成的表进行前缀计算的。为了方便起见，我们定义符号记法：
<BLOCKQUOTE>
<IMG src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/Eqn3.gif"></BLOCKQUOTE>
其中整数i和j满足1≤i≤j≤n。则对k=1,2,..,n，有[k,k]=xk，并且对0≤i≤j≤k≤n，
<BLOCKQUOTE>
<IMG src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/Eqn4.gif"></BLOCKQUOTE>
根据这一符号记法，前缀计算的目标就是计算yk=[1,k]，k=1,2,..n。
当我们对表进行前缀计算时，我们希望输入序列<x1,x2,...,xn>的顺序由对象在链表中的链接关系来确定，而不是由存储对象的存储器阵列中对象的下标来确定。下列EREW算法开始时，表L中每个对象i都有一个相应的值x。如果对象i是从表头开始的第k个对象，则x=xk为输入序列中的第k个元素。因此，并行前缀计算产生y=yk=[1,k]。<CODE class=pseudocode><PRE>下面的算法使用了伪代码进行描述，请参见<a href="http://iprai.hust.edu.cn/icl2002/algorithm/algorithm/pseudocode.htm" target="_blank" >伪代码的使用</A></PRE><PRE>
List-Prefix(L)</PRE><PRE>1. for 每个处理器i，并行地执行</PRE><PRE>2. do y ← x</PRE><PRE>3. while 存在一个对象i满灶next≠NIL</PRE><PRE>4. do for 每个处理器i,并行地执行</PRE><PRE>5. do if next≠NIL</PRE><PRE>6 then y[next]← yÄy[next];</PRE><PRE>7 next← next[next];</CODE></PRE>
上述伪代码和图3说明了这个算法和List-Rank的相似之处。仅有的差别在于初始化以及更新值的不同（d或y）。在List-Rank中，处理器i更新其自身的d；在List-Prefix中，处理器i更新的是另一个处理器的y[next]。注意，List-Prefix与List-Rank一样也是EREW算法，因为指针转移技术维持以下条件不变：对不同的对象i和j，或者next≠next[j]，或者next=next[j]=NIL。
图3说明了while循环中的每一次迭代执行前表的状态。这一过程保持下列条件不变：在第t次while循环执行结束时，第k个处理器中存放了[max(1，k-2t+1)，k]，k=1,2,..,n。在第一次迭代过程中，除最后一个对象的指针为NIL外，表中第k个对象均指向初始时的第k+1个对象。第6行使得第k个对象(k=1,2,..,n-1)从其后继中取得值[k+1,k+1]。然后执行运算[k,k]Ä[k+1,k+1]，得到[k,k+1]，再把它存储回其后继中。然后，next指针与在List-Rank中一样进行转移，得到图3(b)所示的第一次迭代后的结果。第二次迭代也是类似的。对k=1,2,...,n-2，第k个对象从其后继（由其next域的新的值所定义）取得值[k+1,k+2]，然后把[k-1,k]Ä[k+1,k+2]=[k-1,k+2]存入其后继中。结果如图3(c)所示。在第三次也是最后一次迭代中，只有表的开头两个对象的指针不是NIL，它们从其各自的表中分别从其后继取得相应的值。最后的结果如图3(d)所示。我们注意到使算法List-Prefix能够工作的关键是在每一步，如果我们对每一个存在的表进行先缀计算，则每个对象均包含正确的值。
<IMG src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/fig3a.gif">
(a)
<IMG src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/fig3b.gif">
(b)
<IMG src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/fig3c.gif">
(c)
<IMG src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/fig3d.gif">
(d)
图3 在链表上并行前缀算法List-Prefix的执行过程
因为上面介绍的两种算法运用了同样的指针转移技术，所以对List-Prefix的分析与List-Rank相同：在EREW PRAM上的运行时间为O(lgn)，算法执行的全部工作为O(nlgn)。[

b · 发表于 2004-5-28 03:14:50

<H3>1.3 欧拉回路技术</H3><

>在本节中，我们将介绍欧拉回路技术，并说明如何运用这一技术在n个结点的二叉树中计算出每个结点的深度。在这个O(lgn)时间的EREW算法中，关键的一步就是并行前缀计算。<

>为了在PRAM中存储二叉树，我们采用了简单的二叉树表示法。每个结点i有三个域parent,left,right，分别指向结点i的父母、左子女和右子女。假定每个结点用一个非负整数来表示。我们为每个结点联接三个而不是一个处理器，其原因我们在下面将会明白。称这三个处理器为结点的A，B和C处理器，我们可以很容易地在结点与其三个处理器之司找出对应关系。例如，结点i可以与处理器3i，3i+1和3i+2相联接。<>在串行RAM上，计算包含n个结点的树中每个结点的深度所需运行时间为O(n)。采用一种简单的并行算法来计算结点深度时，算法可以从树的根结点开始把一种“波”向下传输。这种波同时到达深度相同的所有结点，因此通过对波载计数器增值，我们就能计算出每个结点的深度。这种并行算法对完全二叉树很适用，这是因为其运行时间与树的高度成正此。而树的高度最大为n-1，这时算法的运行时间为O(n)，这并不优于串行算法。但是，如果我们运用欧拉回路技术，不论树的高度是多少，都能够在EREW PRAM上用O(lgn)的运行时间计算出结点的深度。一个图的欧拉回路是通过图的每条边一次一个回路，当然，在此过程中它可以多次访问一个结点。根据图论算法可知，一个有向连通图具有欧拉回路当且仅当对所有结点v，v的出度等于v的入度。因为无向图每条无向边(u，v)对应于相应的有向图中的两条边(u，v)和(v，u)，因此任何无向连通图改成的有向图均包含欧拉回路，这对无向树也自然成立。<img src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/fig4a.gif">(a)<img src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/fig4b.gif">(b)
图4 运用欧拉回路技术来计算每个结点在二叉树中的深度为了计算二叉树T中结点的深度，首先在改写的有向树T中形成一个欧拉回路。该回路对应于树的遍历过程，如图4(a)所示，它可以用一个连接树中所有结点的链表来表示。其结构如下：<UL><LI>如果结点的左子女存在，则结点的A处理器指向其左子女的A处理器，否则就指向自身的B处理器。 <LI>如果结点存在右子女，则结点的B处理器指向其右子女的A处理器，否则就指向其自身的C处理器。 <LI>如果一个结点是其父母结点的左子女，则结点的C处理器指向其父母的B处理器，如果该结点是其父母结点的右子女，则结点的C处理器指向其父母的C处理器。根结点的C处理器指向NIL。 </LI></UL>因此，根据欧拉回路形成的链表的表头是根结点的A处理器，表尾是根节点的C处理器。如果已知构成原始树的指针，则我们可以在O(1)的时间内构造出欧拉回路。在我们获得表示T的欧拉回路的链表后，我们在每个A处理器中放入值1，在每个B处理器中放入值0，在每个C处理器中放入值-1，如图4(a)所示。然后如第1.2节中那样，我们运用满足结合律的普通加法来执行并行前缀计算。图4(b)说明了并行前缀计算的结果。我们说，在执行完并行前缀计算过程后，每个结点的深度值在结点的C处理器中。为什么呢？我们按以下要求把数放入A，B和C三个处理器中：访问子树的最后结果是把运行和加上0。每个结点i的A处理器对其左子女树的运行和加1，这表明i的左子女的深度比i的深度大1。B处理器对运行和没有影响，这是因为i的左子女的深度与其右子女的深度相等。C处理器使运行和减1，以便对i的父母结点来说，对以i为根结点的子树进行访问后运行和不会改变。我们可以在O(1)的时间内计算出表示欧拉回路的列表。列表中包含3n个对象，所以执行并行前缀计算过程仅需O(lgn)的运行时间。因此，计算所有结点深度所花费的全部运行时间为O(lgn)。又因为算法执行中不需要对有存储器执行并发存取操作，所以该算法是一个EREW算法。

b · 发表于 2004-5-28 03:15:05

<H2>第二节 CRCW 算法与 EREW 算法</H2>
<

>并行计算机的硬件是否应该提供并发的存储器存取操作？一些人认为支持CRCW算法的硬件系统过分昂贵，且使用过于频繁，另外一些人则抱怨说EREW PRAM提供的程序设计模型局限性太大。也许这场争论的最终答案在于两者之间的权衡，实际上也出现了数种折衷模型。下面我们来考察一下并发的存储器存取操作究竟给算法带来了哪些优越性能。
<

>在本节中，我们将证明用CRCW算法来解决某些问题要比用最好的EREW算法来解决同样的问题要好。例如，对于在树林中寻找树根的问题，允许并发读操作可以使人们获得一种更快的算法。对于在一个数组中寻找最大元素的问题，允许并发写操作也可以使算法的执行速度更快。
<UL>
<LI><a href="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/chapter2_1.htm" target="_blank" >2.1 并发操作发挥作用的有关问题</A>
<LI><a href="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/chapter2_2.htm" target="_blank" >2.2 并发写操作发挥作用的一个问题</A>
<LI><a href="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/chapter2_3.htm" target="_blank" >2.3 用EREW算法来模拟CRCW算法</A> </LI></UL>

b · 发表于 2004-5-28 03:16:04

<H3>2.1 并发操作发挥作用的有关问题</H3><

>假定已知一个二叉树组成的森林，其中每个结点都有一个指针parent指向其父母结点，我们希望每个结点能找出它所在的树的根结点。我们把处理器i与森林F中的每个结点i相联结，下列指针转移算法把每个结i所在的树的根结点的值存储在root中。<>Find-Roots(F)
1 for 每个处理器i，并行地执行
2 do if parent=NIL
3 then root←i
4 while 存在一个结点i满足parent≠NIL
5 do for 每个处理器i，并行地执行
6 do if parent≠NIL
7 then root← root[parent]
8 parent← parent[parent]
<>图5说明了该算法的操作过程。在第1-3行执行初始化操作后，如图5(a)所示，知道根的值的唯一结点是根结点自身。第4-8行的while循环执行<a href="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/chapter1.htm" target="_blank" >指针转移</A>操作，并填入root域。图5(b)-(d)分别说明了循环中的第1，第2和第3次迭代后森林的状态。我们可以看出，算法保持下列条件不变：如果parent=NIL，则把该结点的根的值赋给root。<img src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/fig5a.gif">(a)<img src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/fig5b.gif">(b)<img src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/fig5c.gif">(c)<img src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/fig5d.gif">(d)图5 用一台CREW PRAM在二叉树森林中寻找根的过程我们说Find-Roots是一个运行时间为O(lgd)的CREW算法，其中d是森林中具有最大深度的树的深度。写操作仅出现在第3，7和8行，并且因为在每个写操作中处理器仅对结点i写入，所以这些写操作都是互斥性的。但是，第7-8行的读操作是并发执行的，这是因为数个结点的指针可能指向同一个结点。例如在图5(b)中，我们可以看到在while循环的第二次迭代中，root[4]和parent[4]同时被处理器18，2和7读出。Find-Roots的运行时间为O(lgd)，其理由与<a href="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/chapter1_1.htm#ListRank" target="_blank" >List-Rank</A>相同：每次迭代使每条路径的长度缩短一半。图5明显地说明了这一特征。如果只允许互斥读操作，则树林中的n个结点要找出其所在二叉树的根又需要多少时间？我们可以简单地证明需要O(lgn)运行时间。关键的一点是：当读操作互斥时，PRAM的每一步只允许把一条已知信息复制到存储器中的至多一个其他存储单元，因此每一步执行后包含该信息的存储单元数至多增加一倍。在单棵树的情况下，初始时至多有一个存储器单元保存着根的值；在第一步执行后，至多有两个存储器单元包含根的值；执行k步后，至多有2k个存储单元包含根的值。如果树的规模为O(n)，则算法结束时就需要O(n)个存储单元来存储根的值。因此，总共要执行的步数是O(lgn)。每当森林中各个树的最大深度d为2O(lgn)时，从渐近意义上来说，CREW算法Find-Roots要超过任何EREW算法。特别地，在一个由n个结点组成的森林中，最大深度的树是一棵具有O(n)个结点平衡二叉树，d = O(lgn)，在这种情形下Find-Roots的运行时间为：O(lglgn)。用任何EREW算法解决这一问题则要Ω(lgn)的运行时间。因此，在这一问题中允许并发读对于我们是有帮助的。

b · 发表于 2004-5-28 03:17:11

.2 并发写操作发挥作用的一个问题<

>为了证明并发写操作提供的性能要优于互斥写操作所能提供的性能，我们来考察一个在实数组成的数组中寻找最大元素的问题。我们将会看到，关于这个问题的任何EREW算法都需要Ω(lgn)的运行时间，没有任何CREW算法能获得更好的性能。但是，采用一个普通的CRCW算法来解决这一问题仅需要O(1)时间。在这个算法中数个处理器可以对同一个存储单元进行写操作，且写出的值相同。<

>找出n个数组元素中的最大值的CRCW算法假定输入的数组为A[0..n-1]。该算法使用了n2个处理器。对0≤i≤j≤n-1，每个处理器对A和A[j]的值进行比较。实际上，算法是对一个比较矩阵进行操作，因此我们不仅可以把这n2个处理器赋予一个一维下标，也可以把它们理解为具有二维下标(i,j)。<>Fast-Max(A)
1 n ← length(A)
2 for i←0 to n-1 并行地执行
3 do m← TRUE
4 for i←0 to n-1 and j←0 to n-1 并行地执行
5 do if A < A[j]
6 then m ← FALSE
7 for i←0 to n-1 并行地执行
8 do if m = TRUE
9 then max←A
10 return max第1行确定了数组A的长度；它仅需在一个处理器(如处理器0)上执行。我们设置了一个数组m[0..n-1]，m由处理器i响应。我们希望m=TRUE当且仅当A是数组A中元素的最大值。开始时(第2-3行)，我们把每个元素都当作可能的最大值处理，并且依靠第5行中的比较操作以确定哪些元素不是值最大的元素。图6说明了算法的余下部分在第4-6行的循环代码中，我们对数组A中排序的每对元素进行检查。对每对元素A和A[j]，第5行专看是否有A<A[j]。如果这一比较式为真，我们就知道A不可能是最大元素，于是在第6行中置m←FALSE以便记录下这一事实。可能有数个(i,j)处理器同时对m进行写操作，但它们要写入的都是相同的值：FALSE。<DIV align=center><TABLE border=0><TR><TD></TD><TD>A[j] </TD></TR><TR><TD>A</TD><TD><DIV align=center><CENTER><TABLE borderColor=#000000 cellSpacing=0 borderColorLight=#000000 border=1><TR><TD align=middle>　</TD><TD align=middle><DIV align=center><TABLE width="100%" border=0><TR><TD align=middle width="20%">5</TD><TD align=middle width="20%">6</TD><TD align=middle width="20%">9</TD><TD align=middle width="18%">2</TD><TD align=middle width="22%">9</TD></TR></TABLE></DIV></TD><TD align=middle>m</TD></TR><TR><TD vAlign=top align=middle><DIV align=center><TABLE width="100%" border=0><TR><TD align=middle width="100%">5</TD></TR><TR><TD align=middle width="100%">6</TD></TR><TR><TD align=middle width="100%">9</TD></TR><TR><TD align=middle width="100%">2</TD></TR><TR><TD align=middle width="100%">9</TD></TR></TABLE></DIV></TD><TD align=middle><TABLE width="100%" border=0><TR><TD align=middle width="20%">F</TD><TD align=middle width="20%">T</TD><TD align=middle width="20%">T</TD><TD align=middle width="20%">F</TD><TD align=middle width="20%">T</TD></TR><TR><TD align=middle width="20%">F</TD><TD align=middle width="20%">F</TD><TD align=middle width="20%">T</TD><TD align=middle width="20%">F</TD><TD align=middle width="20%">T</TD></TR><TR><TD align=middle width="20%">F</TD><TD align=middle width="20%">F</TD><TD align=middle width="20%">F</TD><TD align=middle width="20%">F</TD><TD align=middle width="20%">F</TD></TR><TR><TD align=middle width="20%">T</TD><TD align=middle width="20%">T</TD><TD align=middle width="20%">T</TD><TD align=middle width="20%">F</TD><TD align=middle width="20%">T</TD></TR><TR><TD align=middle width="20%">F</TD><TD align=middle width="20%">F</TD><TD align=middle width="20%">F</TD><TD align=middle width="20%">F</TD><TD align=middle width="20%">F</TD></TR></TABLE></TD><TD align=middle><TABLE width="127%" border=0><TR><TD align=middle width="100%">F</TD></TR><TR><TD align=middle width="100%">F</TD></TR><TR><TD align=middle width="100%">T</TD></TR><TR><TD align=middle width="100%">F</TD></TR><TR><TD align=middle width="100%">T</TD></TR></TABLE></TD></TR></TABLE></CENTER></DIV></TD></TR><TR><TD> </TD><TD>max 9 </TD></TR></TABLE></DIV>图6 用CRCW算法Fast-Max在O(1)的时间内求出n个值中的最大值因此，在执行完第6行代码后，只有对A是最大值的下标i，才有m=TRUE。第7到9行把这一最大值存入变量max中，并返回。可能有数个处理器对变量max进行写操作，但如果是这样，它们要写入的都是相同的值，这个条件对于普通的CREW PRAM模型是必须一贯保持的。由于算法中的三个循环均是并发执行，所以Fast-Max的运行时间为O(1)。当然，它并不是高效的算法，这是因为它需要n2个处理器，而用串行算法解决这个问题所需的运行时间为O(n)。在某种意义上说，过程Fast-Max的关键在于一台CRCW PRAM用了n个处理器在O(1)的时间内执行关于n个变量的布尔型“与”操作（因为普通的CRCW模型具备这种性能，所以具有更大效力的CRCW PRAM模型更应具备这一性能）。实际上，上述代码一次执行了数个“与”操作，它对i=0,1,....n-1，计算：　<img src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/Eqn5.gif">上式可由DeMorgan定理推出。这一“与”功能也可用于其他方面。例如，CRCW PRAM具有在O(1)的时间内执行“与”操作的功能，因而不需要用一个独立的控制网络来测试全部处理器是否都完成了一次循环。是否结束循环仅由对所有处理器结束循环的要求进行“与”操作的结果来决定。EREW模型不具备这种强有力的“与”工具。计算n个元素中的最大值的任何EREW算法均需要Ω(lgn)的运行时间。关于这一点的证明从概念上说类似于寻找二叉树根结点的下界的论证。在那个证明里，我们观察有多少结点“知道”其根的值，并证明了每一步操作至多使“知道”的结点数增加一倍。对于计算n个元素中的最大值问题，我们观察哪些元素“知道”它们不是最大值，从直观上说，在EREW PRAM上的每一步操作后，这一“知道”的元素数目至多减少一半，这样我们就得了下界Ω(lgn)。令人惊异的是，即使我们允许执行并发读操作，计算最大值的运行时间的下界依然是Ω(lgn)。亦即，对CREW算法该下界也保持不变。Cook，Dwork和Reischuk已经证明：实际上，即使处理器数目不受限制且存储器容量也不受限制，寻找n个元素中最大值的任何CREW算法都必须运行O(lgn)的时间。对于计算n个布尔值的“与”问题，该下界Ω(lgn)也适用。

b · 发表于 2004-5-28 03:18:12

<H3>2.3 用EREW算法来模拟CRCW算法</H3><

>现在我们已经知道CRCW算法能够比EREW算法更快地解决某些问题。并且，任何 EREW算法都能在CRCW PRAM上执行。因此，严格地说CRCW模型要比EREW模型更有效力。但是其效力究竟有多大？在第3节中，我们将会证明具有p个处理器的EREW PRAM能够在O(lg p)的运行时间内对p个数进行排序。现在我们先运用这一结论来说明相对于EREW PRAM来说CRCW PRAM的效力的上界。<

>定理1<

>具有p个处理器的CRCW算法的运行速度至多比解决同一问题的最好的具有p个处理器的EREW算法快O(lg p)倍。证明：我们采用模拟论证。用一个运行时间为O(lgP)的EREW计算过程来模拟CRCW算法的每一步操作。因为两种计算机的处理能力是相同的，所以我们仅重点讨论存储器存取操作。在此我们仅对并发写操作进行模拟以证明定理。对并发读操作的模拟与此类似。我们引入一个长度为p的数组A，使EREW PRAM中的p个处理器模拟CRCW算法中的并发写操作。图7说明了这一思想。对i=0,1,..,p-1，当CRCW处理器pi要求把一个数据xi写入存储单元li时；每个相应的EREW处理器pi把序对(li,xi)写入存储单元 A中。因为每个处理器对不同的存储单元进行写操作，所以这些写操作都是互斥的。然后，把数组A按其有序对的第一个坐标在O(lg p)的时间内进行排序(<a href="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/chapter3.htm#deduction3" target="_blank" >参见Brent定理的推论3</A>)，这样就使得写到同一个存储单元的所有数据在输出时被放在一起。现在，对i=1,2,..,p-1，每个EREW处理器pi检查A=(lj,xj)，A[i-1]=(lk,xk)其中0≤j,k≤p-1。如果lj≠lk或i=O，则对i=1,2,...,p-1，处理器pi把数据xj写到全局存储器的存储单元lj中。否则处理器不作任何操作。因为数组A已按其第一个坐标排序，所以实际上只有一个对任何给定存储单元执行写操作的处理器成功地执行操作，因此该写操作是互斥的。所以这一过程在O(lg p)时间里实现了普通的CRCW模型中的并、发写操作中的每个步骤。(证毕)有关并发写的其他模型也可以同样被模拟。<img src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/fig7a.gif">
(a)<img src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/fig7b.gif">(b)图7 在一台EREW PRAM上模拟并发写操作于是，又出现了这样一个问题：在CRCW和EREW中究竟应选择哪一种模型？如果选择CRCW，则应选择什么样的CRCW模型？CRCW模型的支持者指出，CRCW模型的程序设计要比EREW模型简单，并且运行速度快。CRCW模型的批评者则争论说实现并发存储的硬件要比实现互斥存储器操作的硬件速度慢，因此CRCW算法的运行速度是不现实的，在现实中无法用O(1)的运行时间找出n个值中的最大值。另外还有一部分人认为PRAM，不论是EREW还是CRCW，都是完全不合适的模型。各处理必须由一个通讯网络互相连接，而这个通讯网络也应该是模型的一部分。在网络中，处理器应当仅能与其相邻的处理器进行通讯。很清楚，不可能马上就能找出各种观点的人都赞同的“正确”并行模型。但是，重要的一点是我们必须认识到：模型仅仅是模型。在现实世界中，各种模型的应用都要受到不同程度的限制。模型在多大程度上与工程学的情形相匹配，在此模型上的算法分析就能在多大程度上预示现实世界中的现象。因此学习各种并行模型和相应的算法是相当重要的，随着对并行计算领域的研究不断发展，最终将会产生趋于一致的并且适合于实现的并行计算模型的规范。

b · 发表于 2004-5-28 03:18:37

<H2>第三节 Brent定理与工作效率</H2><

>Brent定理说明我们如何用PRAM来有效地模拟组合电路。运用这一定理，我们就能把许多关于排序网络的结论和许多关于运算电路的结论进行改写以适合PRAM模型。对组合电路知识不太熟悉的读者也许希望复习一下相关的内容。<

><DFN>组合电路</DFN>是由组合元件构成的无回路网络。每个组合元件都具有一个或多个输入，在本节中，我们假定每个组合元件仅有1个输出(具有k>1个输出的组合元件可以看成是k个独立的元件)。输入的数目称为元件的扇入，其输出馈送到的地点个数称为元件的扇出。在本节中我们一般假定电路中的每个组合元件具有有限的扇入，但扇出数可以不受限制。<

>组合电路的<DFN>规模</DFN>是指它所包含的组合元件个数。从电路的输入到某组合元件的输出的最长路径中组合元件的数目称为该元件的<DFN>深度</DFN>。整个电路的深度是其任何元件的最大深度。定理2 Brent定理任何深度为d，规模为n并具有有限扇入的组合电路都能由一种p个处理器的CREW算法在O(n/p+d)的时间内对其进行模拟。证明：我们把组合电路的输入存储于PRAM的全局存储器中，并且我们为电路中的每个组合元件保留了一个存储单元以有效经过计算后的输出值。这样，我们就能够在O(1)的时间内用单个PRAM处理器对指定的组合电路模拟如下：处理器仅仅为元件从相应于电路输入存储器单元中读入输入值，或馈送给它的其他元件的输出值，这样就模拟出电路中的线路。然后处理器计算出组合元件实现的函数并把结果写到存储器的适当存储单元中去。由于每个组合元件的扇入是有限的，所以可以在O(1)的运行时间内计算出每个函数。因此，我们的任务就是找出关于p个处理器的PRAM的一种调度方法，使得所有的组合元件都能在O(n/p+d)的时间被模拟。主要的约束条件是：对于一个组合元件，直至对其有馈送的所有元件的输出都计算出后，才能对该元件进行模拟。每当被并行模拟的数个组合元件需要同一个值时，我们就运用并发读操作。由于深度为1的所有元件仅依赖于电路的输入，所以初始时仅能对这些元件进行模拟；一旦对它们的模拟完成后，就可以对深度为2的所有元件进行模拟，如此下去，直至完成对深度为d的所有元件的模拟操作。其中最关键的思想在于：如果从深度为1到深度为i的所有元件均已被模拟，则我们就能并行地对深度为i+l的元件的任何子集进行模拟，这是因为它们各自的计算过程是相互独立的。因此，调度策略是非常朴素的。我们在对深度为i的所有元件进行模拟后才继续对深度为i+1的那些元件进行模拟。在给定的深度i内，我们一次可模拟p个元件。现在让我们来分析这种模拟策略。对i=1,2,...,d，设ni是电路中深度为i的元件数，因此<BLOCKQUOTE><img src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/Eqn6.gif"></BLOCKQUOTE>考察深度为i的ni个组合元件。把这些元件分成<img src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/parall1.gif">个组，其中前<img src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/parall2.gif">个组每组包含p个元件，剩下的元件(如果有的话)放在最后一组中，这样PRAM就可以在<img src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/parall3.gif">的时间内对这些组合元件执行的运算进行模拟。因此整个模拟时间与下式相似：<BLOCKQUOTE><img src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/Eqn7.gif"></BLOCKQUOTE>当一个组合电路中每个组合元件的扇出为O(1)时，Brent定理可以推广到应用EREW进行模拟。推论3任何深度为d，规模为n且具有有限的扇入与扇出的组合电路都能在p个处理器的EREW PRAM上在O(n/p+d)的运行时间内对其进行模拟。证明：运用与Brent定理的证明过程中相类似的模拟方法，区别仅在于对线路的模拟方法不同，因为在Brent定理中要求执行并发读操作。对于EREW模拟方法来说，在计算出组合元件的输出后，该输出值并没有直接被需要该值的处理器读出，而是由模拟读元件的处理器把其输出值复制到需要其值的O(1)个输入中去。这样一来，需要读值的处理器就可以读出该值，而此间不会相互干扰。(证毕)这种EREW模拟策略不适用于扇出不受限制的元件，因为每一步中的复制操作所需时间大于常数。因此，对于元件的扇出不受限制的组合电路，我们就需要并发读操作。(如果组合元件足够简单，则扇入不受限制的情形有时可以用同一种CRCW模拟方法来进行处理。)推论3为我们提供了一种快速的EREW排序算法。AKS排序网络使用O(nlgn)个比较器能对深度为O(lgn)的n个数进行排序。由于比较器均有有限扇入，所以存在一种EREW算法，该算法使用n个处理器可以在O(lgn)的运行时间内对n个数进行排序。(<a href="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/chapter2_3.htm#theorem1" target="_blank" >我们在定理1中运用了这个结论以证明一台EREW PRAM可以模拟一台CRCW PRAM，其速度至多降低一个对数因子。</A>)不幸的是，O - 记号中所隐藏的常数太大，以致于这种排序算法仅有理论上的意义。但是，目前已发现很多实用的EREW排序算法，特别值得一提的是由Cole发现的并行合并排序算法。假定有一个至多使用p个处理器的PRAM算法，但我们的PRAM仅有p'< p个处理器。我们非常希望能以一种高效的方式在p'个处理器的PRAM上运行p个处理器的算法。通过应用Brent定理证明中用到的思想，就能给出能否运行的条件。定理4如果用到p个处理器的PRAM算法A的运行时间为t，则对任意p'< p，存在一个能解决相同问题的具有p'个处理器的PRAM算法，该算法的运行时间为O(pt/p')。证明：设算法A的时间步被编号为1,2,...,t。算法A'能在<img src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/parall4.gif">的时间内模拟出A的每个时间步i=1,2,..,t的执行。因为总共有t个时间步，所以由于p'< p，整个模拟过程需要的时间为：<img src="http://iprai.hust.edu.cn/icl2002/algorithm/advanced/parallel_algorithm/images/parall5.gif">。(证毕)算法A完成的工作为pt，算法A'完成的工作为(pt/p')p'=pt；因此模拟过程是高效的。因此，如果算法A本身是高效的算法，则算法A'也同样是高效的。因此，当对于某一问题开发高效的算法时，我们无需对不同数目的处理器建立不同的算法。例如，假设我们能够证明不论处理器数目是多少，解决某给定问题的任何并行算法的运行时间有严格下界t，再假设解决该问题最好的串行算法所做的工作为w，则为了获得所有可能的处理数目下的高效的算法，我们对这一问题只需开发一种使用p=Θ(w/t)个处理器的高效的算法就可以了。对p'=o(p)，定理4保证存在一个高效的算法。对p'=ω(p)，不存在高效的算法；这是因为如果t是任何并行算法运行时间的下界，则有p't=ω(pt)=ω(w)。

		自动登录	找回密码
密码			注-册-帐-号