Parallel String Sample Sort
Parallel String Sample Sort
复制标题
并行字符串样本排序
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
P. Sanders
中科院分区：
文献类型：
--
作者：
Timo Bingmann;P. Sanders
我们讨论如何在现代多核共享内存机器上并行化字符串排序算法。作为最佳顺序字符串排序算法和原子对象成功并行排序算法的综合，我们提出了字符串样本排序。该算法有效地利用了内存层次结构，使用了额外的字级并行性，并在很大程度上避免了分支错误预测。此外，我们还并行化了多键快速排序和基数排序的变体，这些变体在某些情况下也很有用。
We discuss how string sorting algorithms can be parallelized on modern multi-core shared memory machines. As a synthesis of the best sequential string sorting algorithms and successful parallel sorting algorithms for atomic objects, we propose string sample sort. The algorithm makes effective use of the memory hierarchy, uses additional word level parallelism, and largely avoids branch mispredictions. Additionally, we parallelize variants of multikey quicksort and radix sort that are also useful in certain situations.