Multiple string matching on a GPU using CUDA

被引：0
作者：
Kouzinopoulos, Charalampos S. [1 ]
Michailidis, Panagiotis D. [2 ]
Margaritis, Konstantinos G. [3 ]
机构：
[1] Department of Balkan, Slavic and Oriental Studies, University of Macedonia
[2] Department of Applied Informatics, University of Macedonia
来源：
Scalable Computing | 2015年 / 16卷 / 02期
关键词：
CUDA; GPU; Many-core computing; Multiple pattern matching; Parallel computing;
D O I：
10.12694/scpe.v16i2.1085
中图分类号：
学科分类号：
摘要：
Multiple pattern matching algorithms are used to locate the occurrences of patterns from a finite pattern set in a large input string. Aho-Corasick, Set Horspool, Set Backward Oracle Matching, Wu-Manber and SOG, five of the most well known algorithms for multiple matching require an increased computing power, particularly in cases where large-size datasets must be processed, as is common in computational biology applications. Over the past years, Graphics Processing Units (GPUs) have evolved to powerful parallel processors outperforming CPUs in scientific applications. This paper evaluates the speedup of the basic parallel strategy and the different optimization strategies for parallelization of Aho-Corasick, Set Horspool, Set Backward Oracle Matching, Wu-Manber and SOG algorithms on a GPU. © 2015 SCPE.
引用
收藏
页码：121 / 137
页数：16
相关论文
共 46 条
[1]  
Aho A., Corasick M., Efficient String Matching: An Aid to Bibliographic Search, 18, pp. 333-340, (1975)
[2]  
Allauzen C., Crochemore M., Raffinot M., Factor Oracle: A New Structure for Pattern Matching, 1725, pp. 758-758, (1999)
[3]  
Apostolico A., Galil Z., Pattern Matching Algorithms, (1997)
[4]  
Arudchutha S., Nishanthy T., Ragel R., String matching with multicore cpus: Performing better with the aho-corasick algorithm, pp. 231-236
[5]  
Yates-Baeza R., Gonnet G., A New Approach to Text Searching, Communications of the ACM, 35, pp. 74-82, (1992)
[6]  
Boyer R., Moore J., A Fast String Searching Algorithm, Communications of the ACM, 20, pp. 762-772, (1977)
[7]  
Chen X., Fang B., Li L., Jiang Y., WM+: An Optimal Multi-pattern String Matching Algorithm Based on the WM Algorithm, pp. 515-523, (2005)
[8]  
Commentz-Walter B., A String Matching Algorithm Fast on the Average, pp. 118-132, (1979)
[9]  
Crochemore M., Czumaj A., Gasieniec L., Jarominek S., Lecroq T., Plandowski W., Rytter W., Speeding Up Two String-matching Algorithms, Algorithmica, 12, pp. 247-267, (1994)
[10]  
Crochemore M., Czumaj A., Gasieniec L., Lecroq T., Plandowski W., Rytter W., Fast Practical Multi-pattern Matching, Information Processing Letters, 71, pp. 107-113, (1999)
12345