基于GPU的精确串匹配算法综述  

Survey on GPU-based exact pattern matching algorithms

作　　者：张春燕[1,2,3] 谭建龙[1,3] 刘燕兵[1,3] 郭莉[1,3] 

机构地区：[1]中科院信息工程研究所,北京100093 [2]中国科学院大学,北京100049 [3]信息内容安全技术国家工程实验室,北京100093

出　　处：《计算机应用研究》2016年第7期1921-1928,1935,共9页Application Research of Computers

基　　金：国家自然科学基金资助项目(61202477;61272427);新疆自治区科技专项资助项目(201230123);中国科学院战略性科技先导专项基金资助项目(XDA06031000)

摘　　要：精确串匹配是计算机领域的一个经典问题。在大数据时代,海量的数据给串匹配问题带来巨大的挑战。当前,GPU的应用得到学术界和工业界的广泛关注,基于GPU的串匹配算法研究已成为学术界的焦点。为展示近年的研究,综述了基于GPU的精确串匹配技术,针对不同的算法和GPU架构介绍精确串匹配技术在GPU上的改进:不同算法的改进具有差异性,研究时需扩展具体算法,并比较上述算法的优缺点。最后对评测指标进行介绍,展望其发展趋势。Exact pattern matching problem is a classic problem in computer science. In big data age, exact string matching for solving the massive scale of data faces an enormous challenge. With the development of modern hardware, the application of GPU （graphics processor units） has attracted high attention in academia and industry widespread. GPU-based exact pattern matching has become a hot spot in academia. This paper surveyed the GPU-based exact pattern matching from different algo- rithms, like AC, KMP, Wu-Manber and so on to demonstrate researches about exact pattern matching in recent years. Accor- ding to the different characteristics of algorithms and the unique architecture of GPU, it introduced the improvement aspects of different GPU-based exact string pattern algorithms. The improved methods of different algorithms were not the same, SO the researchers needed to improve the specific algorithm with its feature. At the same time, the paper summarized the advantages and disadvantages of different GPU-based exact string pattern algorithms. Finally, it introduced the present performance and parameters in the field, and it also looked into the future of trends of development for the future of GPU-based exact pattern matching algorithms.

关 键 词：模式串匹配 精确串匹配 GPU加速 计算统一装置结构 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]