一种适合于GPU计算的并行后缀数组构造算法  

Parallel Suffix Array Construction Algorithm for GPU Computing

作　　者：孙伟东[1,2] 马宗民[2] 

机构地区：[1]沈阳航空航天大学计算机学院,辽宁沈阳110136 [2]东北大学信息科学与工程学院,辽宁沈阳110004

出　　处：《小型微型计算机系统》2011年第5期830-836,共7页Journal of Chinese Computer Systems

基　　金：教育部高等学校博士学科点专项科研基金项目(20050145024)资助

摘　　要：后缀数组广泛应用于序列分析、字符串匹配和文本压缩,近年来,有关后缀数组构造和应用算法的不断探索构成了计算机科学中一个非常活跃的研究领域.在对现有串行算法进行了分析和对比之后,提出了一种新的、简洁的适合于GPU计算的并行后缀数组倍增构造算法,以排序方法替代传统的分组策略,不但能独立完成后缀数组的并行构造,还可与现存的串行倍增算法结合使用,以达到最高的执行效率.实验结果表明该算法在解决实际应用问题时,具有易于实现、执行速度快和可扩展性强等优点,尤其在处理小字符集的数据时效率更高.Suffix array is widely used in sequence analysis,string matching and text compression,over the last few years,suffix array algorithms for construction and application have constituted an intense area of research within computer science.After the analysis and comparison of existing serial algorithms,we propose a new compact parallel prefix-doubling suffix array construction algorithm fit for GPU computing by replacing group with sort.The algorithm can run independently for parallel suffix array construction,and it is also compatible and cooperative with existing prefix-doubling algorithms for peak performance.The experiment results show that the algorithm is simple,fast and scalable for real-world data processing,and especially efficient for small alphabet data.

关 键 词：后缀数组构造 倍增法 GPGPU CUDA 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]