发信人: Lerry (想不开·撞树), 信区: Algorithm
标 题: 并发写操作发挥作用的一个问题
发信站: 哈工大紫丁香 (2002年03月22日14:55:03 星期五), 站内信件
并发写操作发挥作用的一个问题
为了证明并发写操作提供的性能要优于互斥写操作所能提供的性能，我们来考察一个在
实数组成的数组中寻找最大元素的问题。我们将会看到，关于这个问题的任何EREW算法
都需要Ω(lgn)的运行时间，没有任何CREW算法能获得更好的性能。但是，采用一个普通
的CRCW算法来解决这一问题仅需要O(1)时间。在这个算法中数个处理器可以对同一个存
储单元进行写操作，且写出的值相同。
找出n个数组元素中的最大值的CRCW算法假定输入的数组为A[0..n-1]。该算法使用了n2
个处理器。对0≤i≤j≤n-1，每个处理器对A[i]和A[j]的值进行比较。实际上，算法是
对一个比较矩阵进行操作，因此我们不仅可以把这n2个处理器赋予一个一维下标，也可
以把它们理解为具有二维下标(i,j)。
Fast-Max(A)
1 n ← length(A)
2 for i←0 to n-1 并行地执行
3 do m[i]← TRUE
4 for i←0 to n-1 and j←0 to n-1 并行地执行
5 do if A[i] < A[j]
6 then m[i] ← FALSE
7 for i←0 to n-1 并行地执行
8 do if m[i] = TRUE
9 then max←A[i]
10 return max
第1行确定了数组A的长度；它仅需在一个处理器(如处理器0)上执行。我们设置了一个数
组m[0..n-1]，m[i]由处理器i响应。我们希望m[i]=TRUE当且仅当A[i]是数组A中元素的
最大值。开始时(第2-3行)，我们把每个元素都当作可能的最大值处理，并且依靠第5行
中的比较操作以确定哪些元素不是值最大的元素。
图6说明了算法的余下部分在第4-6行的循环代码中，我们对数组A中排序的每对元素进行
检查。对每对元素A[i]和A[j]，第5行专看是否有A[i]<A[j]。如果这一比较式为真，我
们就知道A[i]不可能是最大元素，于是在第6行中置m[i]←FALSE以便记录下这一事实。
可能有数个(i,j)处理器同时对m[i]进行写操作，但它们要写入的都是相同的值：FALSE
。
A[j]
A[i] 5 6 9 2 9
m
5
6
9
2
9
F T T F T
F F T F T
F F F F F
T T T F T
F F F F F
F
F
T
F
T
max 9
图6 用CRCW算法Fast-Max在O(1)的时间内求出n个值中的最大值
因此，在执行完第6行代码后，只有对A[i]是最大值的下标i，才有m[i]=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，计算：
上式可由DeMorgan定理推出。这一“与”功能也可用于其他方面。例如，CRCW PRAM具有
在O(1)的时间内执行“与”操作的功能，因而不需要用一个独立的控制网络来测试全部
处理器是否都完成了一次循环。是否结束循环仅由对所有处理器结束循环的要求进行“
与”操作的结果来决定。
EREW模型不具备这种强有力的“与”工具。计算n个元素中的最大值的任何EREW算法均需
要Ω(lgn)的运行时间。关于这一点的证明从概念上说类似于寻找二叉树根结点的下界的
论证。在那个证明里，我们观察有多少结点“知道”其根的值，并证明了每一步操作至
多使“知道”的结点数增加一倍。对于计算n个元素中的最大值问题，我们观察哪些元素
“知道”它们不是最大值，从直观上说，在EREW PRAM上的每一步操作后，这一“知道”
的元素数目至多减少一半，这样我们就得了下界Ω(lgn)。
令人惊异的是，即使我们允许执行并发读操作，计算最大值的运行时间的下界依然是Ω
(lgn)。亦即，对CREW算法该下界也保持不变。Cook，Dwork和Reischuk已经证明：实际
上，即使处理器数目不受限制且存储器容量也不受限制，寻找n个元素中最大值的任何C
REW算法都必须运行O(lgn)的时间。对于计算n个布尔值的“与”问题，该下界Ω(lgn)也
适用。
--
不在乎天长地久，就怕你从来没有！
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]