DocumentCode :
258985
Title :
Hierarchical Parallelism of Bit-Parallel Algorithm for Approximate String Matching on GPUs
Author :
Cheng Hung Lin ; Guan Hong Wang ; Chun Cheng Huang
Author_Institution :
Dept. of Electr. Eng., Nat. Taiwan Normal Univ., Taipei, Taiwan
fYear :
2014
fDate :
26-27 July 2014
Firstpage :
76
Lastpage :
81
Abstract :
Approximate string matching has been widely used in many areas, such as web searching, and deoxyribonucleic acid sequence matching, etc. Approximate string matching allows difference between a string and a pattern caused by insertion, deletion and substitution. Because approximate string matching is a data-intensive task, accelerating approximate string matching has become crucial for processing big data. In this paper, we propose a hierarchical parallelism approach to accelerate the bit-parallel algorithm on NVIDIA GPUs. A data parallelism approach is used to accelerate the kernel of the bit-parallel algorithm while a task parallelism approach is used to overlap data transfer with kernel computation. In addition, we propose to use hashing to reduce the memory usage and achieve 98.4% of memory reduction. The experimental results show that the bit-parallel algorithm performed on GPUs achieves 7 to 11 times faster than the multithreaded CPU implementation. Compared to the state-of-the-art approaches, the proposed approach achieves 2.8 to 104.8 times improvement.
Keywords :
Big Data; graphics processing units; parallel algorithms; string matching; Big Data processing; GPUs; NVIDIA GPUs; Web searching; approximate string matching; bit-parallel algorithm; data parallelism approach; data transfer; data-intensive task; deoxyribonucleic acid sequence matching; hierarchical parallelism approach; kernel computation; multithreaded CPU; task parallelism approach; Acceleration; Approximation algorithms; Data transfer; Graphics processing units; Kernel; Parallel processing; Pattern matching; approximate string matching; bit-parallel algorithm; graphic processing units;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer Applications and Communications (SCAC), 2014 IEEE Symposium on
Conference_Location :
Weihai
Type :
conf
DOI :
10.1109/SCAC.2014.23
Filename :
6913171
Link To Document :
بازگشت