面向大数据的可扩展正则采样并行排序算法

Abstract

排序算法是计算机科学领域的一个基础算法，是大量应用的算法核心。在大数据时代，随着数据量的极速增长，并行排序算法受到广泛关注。现有的并行排序算法普遍存在通信开销过大、负载不均衡等问题，导致算法难以大规模扩展。针对以上问题，提出一种大规模可扩展的正则采样并行排序（scalable parallel sorting by regular sampling，ScaPSRS）算法，摒弃传统正则采样并行排序（parallel sorting by regular sampling，PSRS）算法中由一个进程负责采样的做法，转而让所有进程参与正则采样，选出p-1个分隔元素，将整个数据集划分成p个不相交的子集，然后实施并行排序，避免了单一进程的采样瓶颈。此外， ScaPSRS采用一种新的迭代更新策略选择p-1个分隔元素，保证划分的p个子集尽可能大小相同，从而确保p个进程对各自的子集进行本地排序时的负载均衡。在天河二号超级计算机上进行的大量实验表明， ScaPSRS算法能够成功地扩展到32 000个内核，性能比PSRS算法和Hofmann等人提出的分区算法分别提升了3.7倍和11.7倍。

Keywords

• 并行排序
• 正则采样
• 负载均衡
• 大数据