algorithm - CREW 和 EREW 婴儿车的 bool OR 和 AND 问题

Question

我正在学习 PRAM 算法。因为我们可以使用以下方法在 O(1) 时间内为 CRCW PRAM 计算 bool 或。

令 A[0]= A[1]|A[2]|A[3]...|A[n] 是 n 位 A[1..n] 的 bool 或运算。假设 A[0] 一开始是零。在第一个时间步中，处理器 i (1<= i <= n) 读取内存位置 A[i]，如果 A[i] 是 1，则继续在内存位置 A[0] 中写入 1。由于几个A[i] 可能为 1，多个处理器可能同时写入 A[0]。因此，对于 CRCW，我们可以在 O(1) 时间内计算 bool 或。

同样我们可以解决CRCW的Boolean AND

我想知道我们如何为 CREW 和 EREW 解决这个问题。算法的时间和处理器界限是什么？

Answer 1

我认为独占读取不是问题，因为每个处理器都在读取自己的位。问题出在独占写入部分，因为它们都必须写入 A[0]。我认为最好的方法是制作一种锦标赛树。因此，您可以对位进行 OR 操作并将结果提升到下一个级别，直到您获得冠军。然后就可以将最终结果写入A[0]。这将是 O(log n)。