排列的奇偶性与并行性
Parity of permutation with parallelism
我有一个长度为 N 的整数数组，包含值 0、1、2、.... (N-1)，表示整数索引的排列。
考虑到我也有 O(N) 的并行计算，确定排列是奇偶校验的最有效方法是什么？
例如，您可以通过并行计算对 log(N) 中的 N 个数求和。我希望也能在 log(N) 中找到排列的奇偶性，但似乎找不到算法。我也不知道这个“并行计算的复杂度顺序”是怎么叫的。
每个数组槽中的数字是该项目的正确槽。将其视为从“从”槽到“到”槽的直接 link。像这样的数组很容易在 O(N) 时间内用单个 CPU 排序，只需跟随 links，所以不得不使用通用排序算法来解决是一种耻辱这个问题。谢天谢地...
您可以使用 Ω(N) CPUs 在 O(log N) 时间内轻松完成此操作。
让 A 成为你的数组。由于每个数组插槽都有一个 link 输出（该插槽中的数字）和一个 link 输入（该插槽的数字在某个插槽中），因此 link 分解为一些循环次数。
排列的奇偶性是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] 中的 link 将最小的 S[i] 传播到循环中的下一个槽。然后每个 link 的长度增加一倍，因此下一次传递会将其传播到 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的元素相加就可以得到排列的循环数，由此我们可以很容易地计算出它的奇偶性。
您没有指定机器 model，所以我假设我们正在使用 EREW PRAM。您关心的复杂性度量称为“跨度”，即计算所需的轮数。还有“工作量”（操作数，所有处理器的总和）和“成本”（跨度乘以处理器数）。
从理论的角度来看，显而易见的答案是 mod 化一个 O(log n) 深度的排序网络（AKS 或古德里奇之字形排序）来计算交换，然后 return (交换次数) mod 2.代码很复杂，常数因子比较大
一个更实用的算法是改用 Batcher 的双调排序网络，它将跨度提高到 O(log2 n) 但有合理的常数因子（这样人们实际使用它实际上是在 GPU 上排序）。
我想不出跨度为 O(log n) 的实用确定性算法，但这是一个具有高概率的跨度 O(log n) 的随机算法。假设有 n 个处理器并让 (modifiable) 输入为 Perm。设 Coin 为 n 个布尔值数组。
在每次 O(log n) 遍中，处理器并行执行以下操作，其中 i ∈ {0…n-1} 标识处理器，并最初交换 ← 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)
然后，我们将交换的本地值和 mod 相加 2。
每遍减少i的个数，使得Perm[i]≠i，减少当前期望总数的1/4。由于期望的线性，期望总数最多为 n(3/4)r，所以在 r = 2 log4/3 之后n = O(log n) 通过，预期总数最多为 1/n，这又限制了算法未按要求收敛到恒等排列的概率。失败时，我们可以切换到 O(n)-跨度串行算法而不破坏预期的跨度，或者再试一次。
我有一个长度为 N 的整数数组，包含值 0、1、2、.... (N-1)，表示整数索引的排列。
考虑到我也有 O(N) 的并行计算，确定排列是奇偶校验的最有效方法是什么？
例如，您可以通过并行计算对 log(N) 中的 N 个数求和。我希望也能在 log(N) 中找到排列的奇偶性，但似乎找不到算法。我也不知道这个“并行计算的复杂度顺序”是怎么叫的。
每个数组槽中的数字是该项目的正确槽。将其视为从“从”槽到“到”槽的直接 link。像这样的数组很容易在 O(N) 时间内用单个 CPU 排序，只需跟随 links，所以不得不使用通用排序算法来解决是一种耻辱这个问题。谢天谢地...
您可以使用 Ω(N) CPUs 在 O(log N) 时间内轻松完成此操作。
让 A 成为你的数组。由于每个数组插槽都有一个 link 输出（该插槽中的数字）和一个 link 输入（该插槽的数字在某个插槽中），因此 link 分解为一些循环次数。
排列的奇偶性是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] 中的 link 将最小的 S[i] 传播到循环中的下一个槽。然后每个 link 的长度增加一倍，因此下一次传递会将其传播到 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的元素相加就可以得到排列的循环数，由此我们可以很容易地计算出它的奇偶性。
您没有指定机器 model，所以我假设我们正在使用 EREW PRAM。您关心的复杂性度量称为“跨度”，即计算所需的轮数。还有“工作量”（操作数，所有处理器的总和）和“成本”（跨度乘以处理器数）。
从理论的角度来看，显而易见的答案是 mod 化一个 O(log n) 深度的排序网络（AKS 或古德里奇之字形排序）来计算交换，然后 return (交换次数) mod 2.代码很复杂，常数因子比较大
一个更实用的算法是改用 Batcher 的双调排序网络，它将跨度提高到 O(log2 n) 但有合理的常数因子（这样人们实际使用它实际上是在 GPU 上排序）。
我想不出跨度为 O(log n) 的实用确定性算法，但这是一个具有高概率的跨度 O(log n) 的随机算法。假设有 n 个处理器并让 (modifiable) 输入为 Perm。设 Coin 为 n 个布尔值数组。
在每次 O(log n) 遍中，处理器并行执行以下操作，其中 i ∈ {0…n-1} 标识处理器，并最初交换 ← 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)
然后，我们将交换的本地值和 mod 相加 2。
每遍减少i的个数，使得Perm[i]≠i，减少当前期望总数的1/4。由于期望的线性，期望总数最多为 n(3/4)r，所以在 r = 2 log4/3 之后n = O(log n) 通过，预期总数最多为 1/n，这又限制了算法未按要求收敛到恒等排列的概率。失败时，我们可以切换到 O(n)-跨度串行算法而不破坏预期的跨度，或者再试一次。