论文标题
设计平行后缀排序
Designing a parallel suffix sort
论文作者
论文摘要
后缀排序在包括基因组学以及经常使用的日常软件应用程序在内的各种计算算法中起着至关重要的作用。当我们在字符串中有很多重复的字符在给定的radix中有很多重复的字符时，排序算法变得棘手。该领域（例如Manber Myers）提供了各种创新的实现。我们在这里介绍了一项分析，该分析使用围绕广义多项式分解的概念来对这些后缀进行分类。这些基因特定多项式的初始生成可以使用并行线程和共享内存有效地完成。事先已知一组不同的因素及其顺序，这有助于我们相应地对多项式（相当于字符串）进行分类。
Suffix sort plays a critical role in various computational algorithms including genomics as well as in frequently used day to day software applications. The sorting algorithm becomes tricky when we have lot of repeated characters in the string for a given radix. Various innovative implementations are available in this area e.g., Manber Myers. We present here an analysis that uses a concept around generalized polynomial factorization to sort these suffixes. The initial generation of these substring specific polynomial can be efficiently done using parallel threads and shared memory. The set of distinct factors and their order are known beforehand, and this helps us to sort the polynomials (equivalent of strings) accordingly.
