并行处理的计算顺序

Question

给定一个未排序的数组，我已经读过一篇文章，可以使用n平方处理器来获得O（1）复杂度中数组的最大元素。任何人都可以解释它背后的机制吗？

Answer 1

该算法背后的机制是基于我只能称之为肮脏的伎俩。也就是说，我们允许所有处理器同时写入相同的共享内存位置。如果它们都写入相同的值，则结果被认为是明确的。

这可以用来实现并行运算符和并行运算符。这里是例如parallel-OR：

result := false 
for i in 0 to N-1 parallel do 
    if a[i] then 
    result := a[i] 

我们还允许同时读取。

这里的MAX算法：

N := a.length 

for i in 0 to N-1 parallel do 
    m[i] := true 

for i in 0 to N-1 parallel do 
    for j in 0 to N-1 parallel do 
    if a[i] < a[j]    /* dirty trick: simultaneous read by many processors */ 
     then m[i] := false   /* dirty trick: many processors write to m[i] at once */ 

for i in 0 to N-1 parallel do 
    if m[i] 
     then max := a[i]   /* dirty trick: many processors write to max at once */ 

return max 

抽象的体系结构，允许这些技巧被称为CRCW PRAM。

Answer 2

这是一个后续| V |广告的答案（这已被删除），

您使用大小n的附加阵列（让叫它B）， 现在你使用n-1处理器比较任意元素a[i], i=0,...,n-1与所有其他元素a[0],...,a[i-1],a[i+1],...,a[n-1]，每一个发现，即发现a[0] > a[j]，处理器j={1,...,n-1}将适用B[i]=B[i]+1，此外，它会检查是否B[i]=n-1，如果是的话，它会宣布元素我是最大的元素。