并行算法

随着并行处理硬件性能的迅速提高，人们对并行算法的兴趣也日益增加。所谓并行算法是指一次可执行多个操作的算法。对并行算法 的研究现在已发展为一个独立的研究领域。很多用串行算法解决的问题也已经有了相应的并行算法。在本文中，我们将阐述一些简单的并行算法以说明一些基本概念 和技术。 这里介绍的并行算法将用一种流行的理论模型即并行随机存取计算机(PRAM)来描述。很多关于数组、表、树和图的并行算法都 可以很容易地用PRAM模型来描述。如果一个PRAM算法在性能上超过另一个PRAM算法，则当两个算法在一台实际的并行计算机上运行时其相对性能不会有 很大变化。 PRAM模型 图1说明了PRAM的基本结构。其中有n个普通的串行处理器p0,p1,...,pn-1共享一个全局存储器。所有处理器都可以“并行地”（同时）从全局存储器读出信息或向全局存储器写入信息。各处理器也可以并行地执行各种算术和逻辑操作。 图l PRAM的基本构造 在PRAM模型中关于算法性能的最关键的一点是：假设运行时间可以用算法执行的并行的存储器存取次数来衡量。这一假设是对普通的RAM模型的直接推 广，并且用存储器存取次数来衡量运行时间对PRAM模型也是很适合的。这一简单的假设对于我们研究并行算法有很大帮助，不过真正的并行计算机并不能做到在 单位时间内对全局存储器并行地执行存取操作：对存储器进行存取操作所需的时间随着并行计算机中处理器数目的增加而相应增加。 然而，对于以任意方式对数据进行存取的并行计算机来说，可以证明存取操作为单位时间的假设是成立的。实际中的并行计算机都包含一个通讯网络以便支持一个抽象的全局存储器。与算术操作等其他操作相比，通过网络存取数据是相当慢的。 因此，计算出两种并行算法所执行的并行的存储器存取次数就可以对其相对性能作出精确的估计。实际的计算机与 PRAM的单位时间抽象不一致，主要在于某种存储器存取模式可能比其他模式快。但是，作为一种近似描述，PRAM模型的单位时间存取的假设还是合乎情理的。 并行算法的运行时间既依赖于执行算法的处理器数目，也依赖于输入问题本身的规模。一般来说，在分析PRAM算法时我们必须同时讨论其时间和处理器数目， 这与串行算法完全不同，在串行算法中我们主要集中于对时间的分析。当然，我们在算法使用的处理器数目与其运行时间之间要进行权衡。 并发存储器存取方式与互斥存储器存取方式 并发读算法是指在算法执行过程中多处理器可以同时对共享存储器的同一位置进行读操作的一种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模型没有作这一假设，并且测试循环终止条件所需的（对数）时间必定包含在整个运行时间内。