随着并行处理硬件性能的迅速提高，人们对并行算法的兴趣也日益增加。所谓并行算法是指一次可执行多个操作的算法。对并行算法的研究现在已发展为一个独立的研究领域。很多用串行算法解决的问题也已经有了相应的并行算法。在本文中，我们将阐述一些简单的并行算法以说明一些基本概念和技术。
这里介绍的并行算法将用一种流行的理论模型即并行随机存取计算机(PRAM)来描述。很多关于数组、表、树和图的并行算法都可以很容易地用PRAM模型来描述。如果一个PRAM算法在性能上超过另一个PRAM算法，则当两个算法在一台实际的并行计算机上运行时其相对性能不会有很大变化。
PRAM模型
图1说明了PRAM的基本结构。其中有n个普通的串行处理器p0,p1,...,pn-1共享一个全局存储器。所有处理器都可以“并行地”(同时)从全局存储器读出信息或向全局存储器写入信息。各处理器也可以并行地执行各种算术和逻辑操作。
图l PRAM的基本构造
在PRAM模型中关于算法性能的最关键的一点是：假设运行时间可以用算法执行的并行的存储器存取次数来衡量。这一假设是对普通的RAM模型的直接推广，并且用存储器存取次数来衡量运行时间对PRAM模型也是很适合的。这一简单的假设对于我们研究并行算法有很大帮助，不过真正的并行计算机并不能做到在单位时间内对全局存储器并行地执行存取操作：对存储器进行存取操作所需的时间随着并行计算机中处理器数目的增加而相应增加。
然而，对于以任意方式对数据进行存取的并行计算机来说，可以证明存取操作为单位时间的假设是成立的。实际中的并行计算机都包含一个通讯网络以便支持一个抽象的全局存储器。与算术操作等其他操作相比，通过网络存取数据是相当慢的。因此，计算出两种并行算法所执行的并行的存储器存取次数就可以对其相对性能作出精确的估计。实际的计算机与 PRAM的单位时间抽象不一致，主要在于某种存储器存取模式可能比其他模式快。但是，作为一种近似描述，PRAM模型的单位时间存取的假设还是合乎情理的。
并行算法的运行时间既依赖于执行算法的处理器数目，也依赖于输入问题本身的规模。一般来说，在分析PRAM算法时我们必须同时讨论其时间和处理器数目，这与串行算法完全不同，在串行算法中我们主要集中于对时间的分析。当然，我们在算法使用的处理器数目与其运行时间之间要进行权衡。第3节中将会讨论这一权衡问题。
并发存储器存取方式与互斥存储器存取方式
并发读算法是指在算法执行过程中多处理器可以同时对共享存储器的同一位置进行读操作的一种PRAM算法。互斥读算法是指在算法执行中任何两个处理器都不能同时对共享存储器的同一位置进行读操作的一种PRAM算法。
类似地，我们根据多处理器能否在同一时刻对共享存储器的同一位置执行写操作也可以把PRAM算法划分为并发写算法和互斥写算法。我们所遇到的算法类型一般采用以下缩写形式：
EREW：互斥读且互斥写
CREW：并发读且互斥写
ERCW：互斥读且并发写
CRCW：并发读且并发写
在这些算法类型中，最常见的是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类型，包括：
任意型：实际存储的是写入的这些值中的一个任意值；
优先级型：存储的是具有最高优先级的处理器所写入的值；
组合型：实际存储的值是写入值的某个特定组合。
在最后一种情况中，特定组合是指满足结合律的某种函数，如加法(存储写入值的和)或最大值函数(仅存储写入值中的最大值)。
同步与控制
PRAM算法必须高度同步以保证其正确执行。如何获得这一同步特征？另外，PRAM算法中的处理器常常必须测试循环的终止条件，而这一终止条件又往往取决于所有处理器的状态。如何实现这种控制功能？
许多并行计算机采用了一种连接各处理器的控制网络，以帮助实现同步和对终止条件进行测试。在特定情况下，控制网络实现这些功能的速度可以与路径选择网络实现对全局存储语句的速度一样快。
为方便起见，我们假设各个处理器固有严格同步的特征。所有处理器同时执行相同的语句。处理器执行代码的进度也保持一致。当我们学习第一个并行算法时，我们将指出在何处我们需要假设处理器是同步执行的。
为了能对依赖于所有处理器状态的并行循环终止条件进行测试，我们假定控制网络能够在O(1)的运行时间内对并行的终止条件进行测试。在一些文件中的EREW PRAM模型没有作这一假设，并且测试循环终止条件所需的(对数)时间必定包含在整个运行时间内。在第2节中我们将看到，CRCW PRAM不需要用控制网络来测试终止条件：它们通过采用并发写操作就能在O(1)的运行时间内测试一个并行循环是否终止。
本文概述
第1节 指针转移技术
这一技术提供了一种并行地控制表操作的快速方法。我们将介绍如何运用指针转移技术对表执行前缀计算，如何尽快把表的算法改写为适用于树的算法。
第2节 CRCW算法和EREW算法
对CRCW算法和EREW算法的相对性能作了比较，并说明了采用并发存储器有取操作可以增加算法解决问题的能力。
第3节 Brent定理
该定理说明如何用PRAM来有效地模拟组合电路。这一节还讨论了关于工作效率的重要问题。并给出了把p个处理器的PRAM算法有效地转化为p个处理器的PRAM算法的条件。
第4节 高效的并行前缀计算
重新讨论了对链表执行前缀计算的问题，并说明如何运用一种随机算法来高效率地进行计算。
第5节 确定的打破对称性问题
讨论了如何运用一种确定的算法在远小于对数时间的运行时间内并行地打破对称性。
本文中阐述的并行算法主要来之于图论的研究领域。它们仅仅是从现存的大量并行算法中选出少量代表算法。但是，本文中所介绍的一些技术却是很有代表性的技术，它们也适用于计算机科学的其他领域中的并行算法。
第一节 指针转移
在各种PRAM算法中，涉及指针的算法是非常有趣的。在本节中，我们要讨论一种称为指针转移的技术，应用这一技术可以获得有关链表操作的快速算法。我们要特别介绍一种O(lgn)时间的算法，该算法用于计算n个对象组成的链表中每个对象到表尾的距离。然后，我们对该算法进行修改，以在O(lgn)的时间内对n个对象组成的链表执行“并行前缀”计算。最后，我们探讨一种把有关树的问题转化为关于链表问题的技术，后一种问题可用指针转移技术来解决。本节中的所有算法都是EREW算法：不需要对全局存储器进行并发存取。
1.1 表排序
1.2 列表的并行前缀
1.3 欧拉回路技术
1.1 表排序
我们介绍的第一个并行算法是有关列表的。列表在PRAM中的存储方式与普通的 RAM相同。为了便于并行地对列表中的对象进行操作，我们为每个对象分配一个“响应”处理器。假定处理器数目与列表中的对象一样多，并且第i个处理器负责处理第i个对象。例如，图2(a)说明了一个由对象序列<3,4,6,1,0,5>组成的链表。由于每个对象对应于一个处理器，所以表中的每个对象都可由其响应处理器在O(1)的时间内对其进行操作。
图2 运用指针转移在O(lgn)时间内求出n个对象组成的链表中每个对象到表尾的距离
假定已知一个包含n个对象的单链表L，我们希望计算出表L中的每个对象到表尾的距离。更形式地说，如果next是指针域，我们希望计算出表中每个对象i的值d，使得：
我们把这一计算d值的问题称为表排序问题。
解决表排序问题的一种方法是从表尾把距离往回传输。因为表中从末端开始的第k个对象必须等到其后的k-1个对象确定了它们到表尾的距离后才能确定其自身到表尾的距离，所以这一方法需要O(n)的运行时间。实际上，这一解决方法是一种串行算法。
下面的代码给出了一种有效的并行算法，其运行时间仅为O(lgn)。
List-Rank(L)
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];
图2说明了算法是如何计算出各个距离值的。图中的每个部分说明了执行第5-9行的while循环的迭代操作以前列表的状态。在第一次迭代中，表中开头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行的测试。
除了并行的运行时间外，对于并行算法还存在另一种有趣的性能评价方法。我们定义并行算法执行的工作为其运行时间与所需的处理器数目的积。从直观上看，工作是一个串行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节中阐述一个关于表排序的高效的并行算法。
1.2 列表的并行前缀
指针转移技术远不止应用于表排序问题。在算术电路中可以运用“前缀”计算来执行快速二进制加法。现在我们来探讨如何运用指针转移技术来进行前缀计算。有关前缀问题的EREW算法对由n个对象组成的表的运行时间为O(lgn)。
前缀计算是根据二进制中满足结合律的运算符Ä来决定的。计算时输入为序列并产生一个输出序列，满足y1=x1，并且对k=2,3,...,n，有
换句话说，每个yk是序列的头k个元素一起“相乘”而得到的。因此才有“前缀”这一意义。
作为前缀计算的一个实例，假定n个对象组成的表中的每个元素包含的值为1，并设Ä表示普通加法运算。因为对k=1,2,...,n，表中第k个元素包含的值为xk=1。所以前缀计算后的结果为yk=k，即为第k个元素的下标。因此，进行表排序的另一种方法是先把表颠倒(可以在O(1)的时间内完成)，执行前缀计算，然后把计算所得的每个值减1。
我们现在说明EREW算法是如何在O(lgn)的运行时间里对n个对象组成的表进行前缀计算的。为了方便起见，我们定义符号记法：
其中整数i和j满足1≤i≤j≤n。则对k=1,2,..,n，有[k,k]=xk，并且对0≤i≤j≤k≤n，
根据这一符号记法，前缀计算的目标就是计算yk=[1,k]，k=1,2,..n。
当我们对表进行前缀计算时，我们希望输入序列的顺序由对象在链表中的链接关系来确定，而不是由存储对象的存储器阵列中对象的下标来确定。下列EREW算法开始时，表L中每个对象i都有一个相应的值x。如果对象i是从表头开始的第k个对象，则x=xk为输入序列中的第k个元素。因此，并行前缀计算产生y=yk=[1,k]。
List-Prefix(L)
1. for 每个处理器i，并行地执行
2. do y ← x
3. while 存在一个对象i满灶next≠NIL
4. do for 每个处理器i,并行地执行
5. do if next≠NIL
6 then y[next]← yÄy[next];
7 next← next[next];
上述伪代码和图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能够工作的关键是在每一步，如果我们对每一个存在的表进行先缀计算，则每个对象均包含正确的值。
图3 在链表上并行前缀算法List-Prefix的执行过程
因为上面介绍的两种算法运用了同样的指针转移技术，所以对List-Prefix的分析与List-Rank相同：在EREW PRAM上的运行时间为O(lgn)，算法执行的全部工作为O(nlgn)。
|
