algorithm - 并行处理的计算顺序

Question

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

Answer 1

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

这可用于实现并行 AND 和并行 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 .