问比较所有元素的并行排序算法

EN

如果比较度量是布尔值(如注释中所示)，则有两种可能性。

1. 度量是传递的(如果comp(A, B)生成true，而comp(B, C)生成true，那么comp(A, C)也必须生成true)。在这种情况下，对任意两个随机元素的比较度量几乎都是从这些元素在排序序列中结束的位置得到的。唯一的复杂因素可能来自应该被视为平等的要素。
2. 该度量不是传递的(如果comp(A, B)生成true，而comp(B, C)生成true，那么根据定义，comp(A, C)不会产生true)。在这种情况下，度量实际上不适合对元素进行排序，因为它没有正确地定义元素的顺序。

我正在实现一个需要并行实现排序和综合集比较的算法

不，您需要做的是先以串行方式实现，然后才能知道如何将其转换为并行。你不会用并行开发的算法来启动大门，而不是先做一个串行的算法。

你之所以不以平行方式开始，是因为列出了很多原因，但我会告诉你一些最重要的原因：

• 你不知道你的程序是否真的会并行地翻译，除非你真的先用串行方式写你的程序
• 你不知道你的程序是否会执行得更好/任何部分实际上会在并行的情况下表现得更好，而不知道你的程序是否会先用串行方式编写。
• 如果没有一个真正以串行方式工作的程序，你就无法很好地测试你的程序。

一般来说，如果你没有先按顺序实现你的程序，那么就会有太多的问题，所以，不要跳过它，并且假设所有的事情都会并行的更好，它很可能不会。

(这将在GPU上完成，但这并不重要)

是的，是的，这很重要。CPU并行具有与GPU并行完全不同的边界，线程是完全独立的，如果一个线程碰巧碰到发散指令，则不会序列化您的程序。

另一方面，如果您正在处理相同的任务，则通常需要复制数据以供CPU共享，而且在DDRN中，与GDDRN不同，在DDRN中实际上不能并行访问ram。与GPU不同的是，您不能承担O(N)任务，它们可以被平均分配，而是必须承担O(N/(小常数))(这在GPU上也不是一个有效的假设，但这是处理数据时必须具备的一种想法，因为它看起来更像O(N/20,000))。

简而言之，CPU并行操作可以很好地处理多指令、多数据(MIMD)任务，

GPU将很好地处理单指令多数据(SIMD)任务。

您的问题可能比另一种架构更好，或者在其中一种架构中不能工作/放弃速度(因为CPU上的上下文切换，或者GPU中的隐式序列化)。

我最初的计划是在第一步中使用bitonic排序，但我不认为bitonic排序会比较每一对元素。另外，首先执行双离子排序，然后计算每一对元素的度量似乎有点效率低下，因为在第二步中将重复计算在双离子排序期间计算的所有比较。

Bitonic排序的串行运行时复杂度为O(n log^2(n))，这是必须进行的比较次数，并行地，运行时为O(log^2(n))，即对每个元素进行的比较数。

现在，你是说你需要做所有的比较。如果N是，比如说256，那么对于每个元素，在实际比较的256个元素中，有64个是比较的.因此，无论如何，只有1/4的比较可以用双离子排序，所以如果你用一个头和每个元素进行比较，你最多只能获得25%的效率，但是只有在整个程序的那一部分(虽然每个元素的比较将是O(N)而不是O(log^2(n))和O(N) >O(log^2(N)。

这对你来说可能是很多，但现在让我们把它移到4096。现在您正在对每个元素进行12^2 = 144的比较.在总共需要4096个.

你会拯救..。3%的比较.这真的值得存那么多钱吗？你甚至可能得慢慢来。

但现在让我们看看问题，想一想.如果你无论如何都需要做N^2比较，因为你需要每对明智的比较…您甚至可以完全摆脱双离子排序，并通过将比较与其他项相加来找到该项的位置，假设您在比较中有一个确定性的断系机制。

编辑:您的比较度量实际上是一个集合的主导地位，但您也希望保持排序(换句话说，排序必须是稳定的)，所以如果您正在进行最大排序，则还必须考虑到每个元素的索引。正因为如此，您需要以一种与主导地位不匹配的方式更改您的比较度量，如双离子排序不稳定。

您还可能需要包括一种编码方式，而不是控制方式。

class DominationEnum(Enum):
    DOMINATES = 1
    DOMINATED = 0
    NODOMINATION = -1


def foo(items)
    n = len(items);
    items_sorted= [null * n]
    items_dominance= [[false for j in range(n)] for i in range(n)]
    number_better_than = 0
    for i_index, i in enumerate(items):
        for j_index, j in enumerate(items):
            domination = is_dominant(i, j)
            items_dominance[i][j] = domination == DominationEnum.DOMINATES
            number_better_than += int(items_dominance[i][j]  or ((domination == DominationEnum.NODOMINATION) and (i_index < j_index))

        items_sorted[number_better_than] = i

以上是这种算法的串行代码，为了使其并行，您可以删除外部循环，并在每个线程实例中运行它。

#i_index is thread index
def foo(items, items_sorted, items_dominance, i_index)
    number_better_than = 0
    for j_index, j in enumerate(items):
            domination = is_dominant(i, j)
            items_dominance[i][j] = domination == DominationEnum.DOMINATES
            number_better_than += int(items_dominance[i][j]  or ((domination == DominationEnum.NODOMINATION) and (i_index < j_index)))

    items_sorted[number_better_than] = i

或将双声速排序比较度量更改为

( i dominates j ) or (if neither i nor j dominates on another and index of i is before index of j) 

然后跑：

def foo(items, items_dominance, i_index)
    number_better_than = 0
    for j_index, j in enumerate(items):
         domination = is_dominant(i, j)
         items_dominance[i][j] = domination == DominationEnum.DOMINATES

此外，通过找到[i][j]的控制并使用它来确定其他控制是什么，您可以将所需操作的数量减半(您可以知道我是控制j、是主导还是不占主导或支配j，这也给出了[j][i]的结果)。