Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: 并行算法
发信站: 哈工大紫丁香 (2002年03月22日14:50:05 星期五), 站内信件

并行算法
随着并行处理硬件性能的迅速提高，人们对并行算法的兴趣也日益增加。所谓并行算法
是指一次可执行多个操作的算法。对并行算法的研究现在已发展为一个独立的研究领域
。很多用串行算法解决的问题也已经有了相应的并行算法。在本文中，我们将阐述一些
简单的并行算法以说明一些基本概念和技术。
这里介绍的并行算法将用一种流行的理论模型即并行随机存取计算机(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 P
RAM不能直接支持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节 确定的打破对称性问题
讨论了如何运用一种确定的算法在远小于对数时间的运行时间内并行地打破对称性。
本文中阐述的并行算法主要来之于图论的研究领域。它们仅仅是从现存的大量并行算法
中选出少量代表算法。但是，本文中所介绍的一些技术却是很有代表性的技术，它们也
适用于计算机科学的其他领域中的并行算法。


--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]