Fast In-Place Suffix Sorting on a Multicore Computer
Fast In-Place Suffix Sorting on a Multicore Computer
复制标题
DOI：
10.1109/tc.2018.2842050
复制
发表时间：
2018-12
影响因子：
3.7
通讯作者：
Bin Lao;Ge Nong;W. H. Chan;J. Xie
中科院分区：
文献类型：
--
作者：
Bin Lao;Ge Nong;W. H. Chan;J. Xie
对输入字符串$X$的所有后缀进行排序将生成后缀数组，该数组是在$X$上进行全文搜索的基本数据结构。为了利用具有共享内存的多核机器的并行计算能力，本文设计了一种称为pSACAK的快速线性时间就地并行算法，用于用常量字母表对输入字符串的后缀进行排序。该算法是顺序后缀排序算法SACAK的并行变体，SACAK改进了线性时间SAIS，使其适用于恒定字母，因此对于字母大小$K$只需要$\mathcal {O}(K)$的工作空间。虽然我们最近的工作已经成功地在多核机器上设计了SAIS的并行变体，但由于就地约束导致的强数据依赖性，对SACAK的并行化仍然是一个挑战。本文提出了一些新技术来克服从序列SACAK设计pSACAK的困难。通过实验研究，比较了pSACAK算法与其他并行后缀排序算法的性能。实验结果表明，在所有算法中，pSACAK算法的时间和空间效率最高。据我们所知，pSACAK是迄今为止报道的唯一用于常量字母的线性时间和就地并行后缀排序算法。
Sorting all suffixes of an input string $X$ will produce the suffix array that is a fundamental data structure for full-text search on $X$ . To utilize the parallel computing power of a multicore machine with shared memory, this article designs a fast linear-time and in-place parallel algorithm called pSACAK, for sorting the suffixes of an input string with a constant alphabet. This algorithm is a parallel variant of the sequential suffix sorting algorithm SACAK which improved the linear-time SAIS to be in-place for constant alphabets, and hence requires only a workspace of $\mathcal {O}(K)$ for alphabet size $K$ . While our recent work has successfully designed the parallel variant of SAIS on a multicore machine, it remains a challenge to parallelize SACAK due to the strong data dependencies caused by the in-place constraint. A number of new techniques are proposed here to overcome the difficulties for designing pSACAK from the sequential SACAK. An experimental study is conducted to evaluate the performance of pSACAK versus other existing parallel suffix sorting algorithms. Our experimental results show that pSACAK is the most time and space efficient among all in comparison. To the best of our knowledge, pSACAK is the only linear-time and in-place parallel suffix sorting algorithm for constant alphabets reported so far.