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.
| Original language | English |
|---|---|
| Title of host publication | Proceedings - 2014 Symposium on Computer Applications and Communications, SCAC 2014 |
| Publisher | Institute of Electrical and Electronics Engineers Inc. |
| Pages | 76-81 |
| Number of pages | 6 |
| ISBN (Electronic) | 9780769553191 |
| DOIs | |
| Publication status | Published - 2014 Sep 29 |
| Event | 2014 Symposium on Computer Applications and Communications, SCAC 2014 - Weihai, China Duration: 2014 Jul 26 → 2014 Jul 27 |
Other
| Other | 2014 Symposium on Computer Applications and Communications, SCAC 2014 |
|---|---|
| Country | China |
| City | Weihai |
| Period | 14/7/26 → 14/7/27 |
Fingerprint
Keywords
- approximate string matching
- bit-parallel algorithm
- graphic processing units
ASJC Scopus subject areas
- Computer Networks and Communications
- Computer Science Applications
Cite this
Hierarchical parallelism of bit-parallel algorithm for approximate string matching on GPUs. / Lin, Cheng Hung; Wang, Guan Hong; Huang, Chun Cheng.
Proceedings - 2014 Symposium on Computer Applications and Communications, SCAC 2014. Institute of Electrical and Electronics Engineers Inc., 2014. p. 76-81 6913171.Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
}
TY - GEN
T1 - Hierarchical parallelism of bit-parallel algorithm for approximate string matching on GPUs
AU - Lin, Cheng Hung
AU - Wang, Guan Hong
AU - Huang, Chun Cheng
PY - 2014/9/29
Y1 - 2014/9/29
N2 - 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.
AB - 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.
KW - approximate string matching
KW - bit-parallel algorithm
KW - graphic processing units
UR - http://www.scopus.com/inward/record.url?scp=84910054319&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84910054319&partnerID=8YFLogxK
U2 - 10.1109/SCAC.2014.23
DO - 10.1109/SCAC.2014.23
M3 - Conference contribution
AN - SCOPUS:84910054319
SP - 76
EP - 81
BT - Proceedings - 2014 Symposium on Computer Applications and Communications, SCAC 2014
PB - Institute of Electrical and Electronics Engineers Inc.
ER -