Engineering Parallel String Sorting
详细信息 查看全文
- 作者：Timo Bingmann ; Andreas Eberle ; Peter Sanders
- 关键词：Parallel string sorting ; String sorting ; Sample sort ; Merge sort ; LCP ; merge sort ; LCP ; insertion sort ; Super scalar string sample sort
- 刊名：Algorithmica
- 出版年：2017
- 出版时间：January 2017
- 年：2017
- 卷：77
- 期：1
- 页码：235-286
- 全文大小：
- 刊物类别：Computer Science
- 刊物主题：Algorithm Analysis and Problem Complexity; Theory of Computation; Mathematics of Computing; Algorithms; Computer Systems Organization and Communication Networks; Data Structures, Cryptology and Inform
- 出版者：Springer US
- ISSN：1432-0541
- 卷排序：77
文摘
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 first propose string sample sort. The algorithm makes effective use of the memory hierarchy, uses additional word level parallelism, and largely avoids branch mispredictions. Then we focus on NUMA architectures, and develop parallel multiway LCP-merge and -mergesort to reduce the number of random memory accesses to remote nodes. Additionally, we parallelize variants of multikey quicksort and radix sort that are also useful in certain situations. As base-case sorter for LCP-aware string sorting we describe sequential LCP-insertion sort which calculates the LCP array and accelerates its insertions using it. Comprehensive experiments on five current multi-core platforms are then reported and discussed. The experiments show that our parallel string sorting implementations scale very well on real-world inputs and modern machines.