[发明专利]并行合并

摘要

提供了用于改进的高性能并行数据排序的方法、装置和系统。在第一阶段，要排序的多个无序数据元素被划分为K个无序列表，这K个无序列表优选地各自具有大约M个元素。这K个无序列表中的每一个可以使用任何算法(诸如快速排序)来并行排序，以生成K个有序列表。在第二阶段，通过使用由最大迭代次数限制的迭代收敛过程，从K个有序列表中确定N个均衡的工作负荷。因此，任何非均匀或偏斜的数据分布都可以以最少的处理时间得以负荷均衡。一旦确定了N个均衡的工作负荷，它们就可以例如通过使用合并排序被并行地独立排序，并且然后利用快速级联组合，以提供最终的经排序的结果。因此，排序操作完全并行化，同时避免了任何昂贵的数据扫描步骤。

主权项

一种方法，包括：接收K个有序列表，其中M表示所述K个有序列表中的每一个中的元素数量；为N个均衡的工作负荷定义目标大小范围，所述目标大小范围背离目标大小KM/N不超出预定阈值；将所述N个均衡的工作负荷确定为包括来自所述K个有序列表中的每一个的子集，所述子集由特定索引范围界定，其中所述确定调整用于每个所述子集的特定索引范围最多达最大迭代次数，以使每个所述N个均衡的工作负荷的大小朝所述目标大小范围收敛；并行地对所述N个均衡的工作负荷中的每一个进行排序；及组合所述N个均衡的工作负荷，以输出经排序的结果；其中所述方法由一个或多个计算设备执行。