置换的奇偶性与并行性

Question

我有一个长度为N的整数数组，包含值0、1、2、... (N-1)，表示整数索引的排列。

如果给定了O(N)的并行计算，确定排列的奇偶性，最有效的方法是什么？

例如，您可以使用并行计算在log(N)时间内对N个数字进行求和。我期望以log(N)的时间找到排列的奇偶性，但似乎找不到一种算法。我也不知道如何称呼这种"具有并行计算复杂度顺序"的方法。

- 317070

---

并行快速排序，跟踪交换的奇偶性，在这里似乎是一个很好的选择，因为在中间分割是微不足道的。https://arxiv.org/pdf/1511.03404.pdf - Dave

Answer 1

每个数组单元格中的数字是该项的适当位置。可以将其视为从“from”槽到“to”槽的直接链接。使用单个CPU按照链接很容易在O(N)时间内对此类数组进行排序，因此使用通用排序算法来解决此问题是可惜的。谢天谢地...

您可以使用Ω(N)个CPU以O(log N)的时间轻松完成此操作。

让A成为您的数组。由于每个数组插槽都有一个单一的出链路（在该插槽中的数字）和一个单一的入链路（该插槽的数字位于某个插槽中），因此链接会分解成若干个周期。

置换的奇偶性是N-m的奇偶性，其中N是数组的长度，m是循环数，因此我们可以通过计算循环次数来得到答案。

首先，创建一个长度为N的数组S，并设置S[i] = i。然后：

Repeat ceil(log_2(N)) times:
    foreach i in [0,N), in parallel:
        if S[i] < S[A[i]] then:
            S[A[i]] = S[i]
        A[i] = A[A[i]]

完成后，每个S[i]将包含包含i的循环中最小的索引。内层循环的第一次通过通过跟随A[i]中的链接将最小的S[i]传播到循环中的下一个槽位。然后将每个链接扩展两倍长，因此下一次传播它会传播到2个新的槽位，以此类推。最多需要ceil(log_2(N))次传播来在整个循环中传播最小的S[i]。

让我们称每个循环中最小的槽位为该循环的“领袖”。领袖的数量即为循环的数量。我们可以像这样找到领袖：

foreach i in [0,N), in parallel:
    if (S[i] == i) then:
        S[i] = 1  //leader
    else
        S[i] = 0  //not leader

最后，我们只需要将S的元素相加，就可以得到排列中循环的数量，从而轻松计算其奇偶性。

- Matt Timmermans

Answer 2

您没有指定机器型号，因此我假设我们正在使用EREW PRAM进行工作。您关心的复杂度度量称为“跨度”，即计算所需的轮数。还有“工作”（所有处理器上的操作次数之和）和“成本”（跨度乘以处理器数量）。

从理论的角度来看，显而易见的答案是修改O(log n)深度的排序网络（AKS或Goodrich的Zigzag Sort）来计算交换次数，然后返回（交换次数）模2。代码非常复杂，常数因子相当大。

更实用的算法是改用Batcher的双调排序网络，这将跨度提高到O(log^2 n)，但具有合理的常数因子（人们实际上会在GPU上使用它进行排序）。

我想不出一个跨度为O(log n)的实用确定性算法，但是下面是一个跨度为O(log n)且概率很高的随机算法。假设有n个处理器，让（可修改的）输入为Perm。让Coin成为n个布尔值的数组。

在每个O(log n)通行证中，处理器并行执行以下操作，其中i ∈ {0…n-1}标识处理器，初始时swaps ← 0。小写变量表示处理器本地变量。

Coin[i] ← true with probability 1/2, false with probability 1/2
(barrier synchronization required in asynchronous models)
if Coin[i]
    j ← Perm[i]
    if not Coin[j]
        Perm[i] ← Perm[j]
        Perm[j] ← j
        swaps ← swaps + 1
    end if
end if
(barrier synchronization required in asynchronous models)

接下来，我们将交换的本地值相加并对2取模。

每次传递期望减少i数量，使得Perm[i] ≠ i，当前总数的1/4。由于期望的线性性，预期总数最多为n(3/4)^r，因此经过r = 2log_4/3n = O(log n)次传递后，预期总数最多为1/n，这反过来又限制了算法未收敛到标识排列所需的概率。失败时，我们可以切换到O(n)-span串行算法，而不会使期望跨度增加，或者重试。

- David Eisenstat

---

（Matt的答案更好，但我会保留这个，因为它展示了一些技巧。） - David Eisenstat