HykSort: a new variant of hypercube quicksort on distributed memory architectures
HykSort: a new variant of hypercube quicksort on distributed memory architectures
复制标题
HykSort：分布式内存架构上超立方体快速排序的新变体
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
G. Biros
中科院分区：
文献类型：
--
作者：
H. Sundar;D. Malhotra;G. Biros
在本文中，我们提出了Hyksort，这是针对分布式存储器体系结构的优化比较，该比较比Bitonic排序和样品相比，该算法超过2倍。使用迭代算法准确选择枢轴的递归Hyksort的优势是较低的沟通成本，更好的负载平衡，并且避免了O（p）的沟通原语，我们还提供了一个分阶段的交流采样器，这比我们进行的大型核心计数更强大。在其中比较了超立方体排序，比特孔排序，原始的采样器，分阶段的采样器和Hyksort。事实证明，在我们在262,144 AMD的最大实验上，没有单个算法可以表现最好，并且必须采用杂交策略。 - 位于37秒内实现0.9TB/s的有效吞吐量的位置整数键。
In this paper, we present HykSort, an optimized comparison sort for distributed memory architectures that attains more than 2× improvement over bitonic sort and samplesort. The algorithm is based on the hypercube quicksort, but instead of a binary recursion, we perform a k-way recursion in which the pivots are selected accurately with an iterative parallel select algorithm. The single-node sort is performed using a vectorized and multithreaded merge sort. The advantages of HykSort are lower communication costs, better load balancing, and avoidance of O(p)-collective communication primitives. We also present a staged communication samplesort, which is more robust than the original samplesort for large core counts. We conduct an experimental study in which we compare hypercube sort, bitonic sort, the original samplesort, the staged samplesort, and HykSort. We report weak and strong scaling results and study the effect of the grain size. It turns out that no single algorithm performs best and a hybridization strategy is necessary. As a highlight of our study, on our largest experiment on 262,144 AMD cores of the CRAY XK7 "Titan" platform at the Oak Ridge National Laboratory we sorted 8 trillion 32-bit integer keys in 37 seconds achieving 0.9TB/s effective throughput.