algorithm - 并行 EREW 后缀最小值

Question

我不确定如何解决这个问题。

我有一个序列 A={x1,x2....xn}

问题是求B:B= {min(x1,x2....xn),min(x2....xn),(x3,x4....xn)............min(xn- 1,xn),xn}

我需要找到一个并行算法 EREW 来解决 O(logn) 中的问题。

到目前为止，我知道需要 log(n) 才能在 n/2 个处理器的 n 个元素列表中找到最小值。 (树的深处)但是因为我需要算法是 EREW(独占读取和独占写入)每个处理器必须单独读取每个元素，这就是为什么我有一个问题要解决它..在 logn..

在我附上的图片中，我正在查看 n=8 的示例。所以我有 A={1,5,4,3,6,9,10,3}我试图从树中获取后缀(在 logn 中)..但我只能得到后缀分钟(a7，a8}分钟{a5,a6,a7,a8}最小{a1,a2,a3,a4,a5,a6,a7,a8}

Answer 1

你确实可以用你的二叉树来解决这个问题:

第 1 阶段:构建您在问题中绘制的树。逐层这样做，从上到下。所有访问都是独立的，因此您可以在 O(1) 中处理一层。您现在已经在每个节点中写入了范围最小值。

伪代码:

for i in [0..log n]:   # layer 0 = top level in your drawing
    parallel for each node in layer i:
        node.min = min(node.left.min, node.right.min)

第 2 阶段:从下到上处理树。将同一层中从它右边的所有节点中的最小值写入每个节点。阶段 1 的范围最小值可用于该目的。

叶子现在拥有计算各自后缀最小值所需的所有信息。

伪代码:

root.right_min = infinity
for i in [log n..1]:
    parallel for each node in layer i:
        node.right.right_min = node.right_min
        node.left.right_min = min(node.right.min, node.right_min)

B = [min(node.min, node.right_min) for each node in layer 0]