algorithm - 并行处理的计算顺序

Question

给定一个未排序的数组，我在一篇文章中读到 n 方处理器可用于在 O(1) 复杂度内获取数组的最大元素。谁能解释它背后的机制？

Answer 1

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

这可用于实现并行与和并行或运算符。例如，并行或：

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|ad 的回答（已删除）的后续行动，

您使用了一个额外的大小数组n（让我们称之为 B），现在您使用n-1处理器将任何元素a[i], i=0,...,n-1与所有其他元素进行比较a[0],...,a[i-1],a[i+1],...,a[n-1]，每个j={1,...,n-1}发现找到的处理器a[0] > a[j]将应用B[i]=B[i]+1，此外，它将检查是否B[i]=n-1，如果是，它将宣布元素 i 是最大元素。