在 C[i]=A[B[i]] 的 EREW 机器中使用 n 个处理器的算法

Question

设 A 是一个大小为 n 的数组，它只包含正数。

令 B 为大小为 n 的数组，它包含 [1,n] 范围内的数字。

令 C 为大小为 n 的数组，我们将在 EREW 机器中使用 n 个处理器在 O(log^2(n)) 中执行 C[i]=A[B[i]]。

请注意，由于 B 可能包含重复项，因此可能会发生读取冲突。

我的策略是用B的信息放大A，这样我们就可以做C[i]=A[B[i]+i]来解决读冲突问题。然而，经过几个小时的尝试，我发现用这种方式放大 A 是不可能不发生读冲突的。我在这里寻求一些提示或建议。因此，不需要详细的解决方案。

Answer 1

当 B 不减时，你能解决这个问题吗？配料器 bitonic mergesort在 EREW 上以 O(log^2 n) 的时间运行。