algorithm - CREW 和 EREW 婴儿车上的布尔 OR 和 AND 问题

Question

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

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

同样，我们可以解决 CRCW 的布尔 AND

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

Answer 1

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