具有并行性的置换奇偶性

Question

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

鉴于我也有 O(N) 的并行计算，确定排列是否具有奇偶校验的最有效方法是什么？

例如，您可以使用并行计算对 log(N) 中的 N 个数字求和。我也希望在 log(N) 中找到排列的奇偶校验，但似乎找不到算法。我也不知道这个“并行计算的复杂度顺序”是如何调用的。

Answer 1

每个数组槽中的数字是该项目的正确槽。将其视为从“from”槽到“to”槽的直接链接。像这样的数组很容易在 O(N) 时间内用单个 CPU 只需按照链接进行排序，因此必须使用通用排序算法来解决这个问题将是一种耻辱。值得庆幸的是...

\n

您可以使用 \xce\xa9(N) 个 CPU 在 O(log N) 时间内轻松完成此操作。

\n

让A成为你的数组。由于每个阵列插槽都有一个单独的输出链接（该插槽中的编号）和一个单独的链接输入（该插槽的编号位于某个插槽中），因此链接会分解为一定数量的周期。

\n

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

\n

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

\n

然后：

\n

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

\n

完成后，每个S[i]将包含包含 的循环中的最小索引i。内循环的第一遍S[i]通过遵循 中的链接将最小的值传播到循环中的下一个槽A[i]。然后每个链接的长度都是原来的两倍，因此下一次遍历会将其传播到 2 个新插槽，依此类推。最多需要遍历才能在循环中ceil(log_2(N))传播最小的链接。S[i]

\n

我们将每个周期中的最小槽称为周期的“领导者”。领导者的数量就是周期数。我们可以这样找到领导者：

\n

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

\n

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

\n