PARADIS: An Efficient Parallel Algorithm for In-place Radix Sort
PARADIS: An Efficient Parallel Algorithm for In-place Radix Sort
复制标题
PARADIS：一种高效的就地基数排序并行算法
DOI：
--
复制
发表时间：
2015
影响因子：
2.5
通讯作者：
R. Puri
中科院分区：
文献类型：
--
作者：
Minsik Cho;D. Brand;R. Bordawekar;Ulrich Finkler;Vincent KulandaiSamy;R. Puri
就地基数排序是一种流行的基于分布的排序算法，用于短数字或字符串键，因为它具有线性运行时和恒定的内存复杂性。然而，由于两个原因，就地基数排序的高效并行化非常具有挑战性。首先，将元素排列到桶中的初始阶段遭受其就地性质固有的读写依赖。其次，当桶的大小差异很大时，算法的递归应用程序对结果桶的负载平衡是困难的，这种情况发生在输入数据的倾斜分布中。在本文中，我们提出了一种新的并行原地基数排序算法PARADIS，它解决了两个问题：a)“推测置换”通过为每个处理器分配多个非连续阵列条纹来解决第一个问题。最终的无共享方案实现了完全并行化。由于我们推测的排列还没有完成，接下来是一个“修复”阶段，这个阶段可以再次并行完成，而处理器之间没有任何数据共享。B)“分布自适应负载平衡”解决了第二个问题。我们在基数排序上下文中动态地分配处理器，以最小化总体完成时间。我们的实验结果表明，PARADIS在广泛的输入数据集上提供了出色的性能/可扩展性。
In-place radix sort is a popular distribution-based sorting algorithm for short numeric or string keys due to its linear run-time and constant memory complexity. However, efficient parallelization of in-place radix sort is very challenging for two reasons. First, the initial phase of permuting elements into buckets suffers read-write dependency inherent in its in-place nature. Secondly, load balancing of the recursive application of the algorithm to the resulting buckets is difficult when the buckets are of very different sizes, which happens for skewed distributions of the input data. In this paper, we present a novel parallel in-place radix sort algorithm, PARADIS, which addresses both problems: a) "speculative permutation" solves the first problem by assigning multiple non-continuous array stripes to each processor. The resulting shared-nothing scheme achieves full parallelization. Since our speculative permutation is not complete, it is followed by a "repair" phase, which can again be done in parallel without any data sharing among the processors. b) "distribution-adaptive load balancing" solves the second problem. We dynamically allocate processors in the context of radix sort, so as to minimize the overall completion time. Our experimental results show that PARADIS offers excellent performance/scalability on a wide range of input data sets.