Hierarchical parallelism of bit-parallel algorithm for approximate string matching on GPUs

Cheng Hung Lin, Guan Hong Wang, Chun Cheng Huang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)

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 languageEnglish
Title of host publicationProceedings - 2014 Symposium on Computer Applications and Communications, SCAC 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages76-81
Number of pages6
ISBN (Electronic)9780769553191
DOIs
Publication statusPublished - 2014 Sep 29
Event2014 Symposium on Computer Applications and Communications, SCAC 2014 - Weihai, China
Duration: 2014 Jul 262014 Jul 27

Other

Other2014 Symposium on Computer Applications and Communications, SCAC 2014
CountryChina
CityWeihai
Period14/7/2614/7/27

Fingerprint

Parallel algorithms
Data storage equipment
Data transfer
Program processors
DNA
Substitution reactions
Processing
Graphics processing unit

Keywords

  • approximate string matching
  • bit-parallel algorithm
  • graphic processing units

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Computer Science Applications

Cite this

Lin, C. H., Wang, G. H., & Huang, C. C. (2014). Hierarchical parallelism of bit-parallel algorithm for approximate string matching on GPUs. In Proceedings - 2014 Symposium on Computer Applications and Communications, SCAC 2014 (pp. 76-81). [6913171] Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SCAC.2014.23

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 proceedingConference contribution

Lin, CH, Wang, GH & Huang, CC 2014, Hierarchical parallelism of bit-parallel algorithm for approximate string matching on GPUs. in Proceedings - 2014 Symposium on Computer Applications and Communications, SCAC 2014., 6913171, Institute of Electrical and Electronics Engineers Inc., pp. 76-81, 2014 Symposium on Computer Applications and Communications, SCAC 2014, Weihai, China, 14/7/26. https://doi.org/10.1109/SCAC.2014.23
Lin CH, Wang GH, Huang CC. Hierarchical parallelism of bit-parallel algorithm for approximate string matching on GPUs. In Proceedings - 2014 Symposium on Computer Applications and Communications, SCAC 2014. Institute of Electrical and Electronics Engineers Inc. 2014. p. 76-81. 6913171 https://doi.org/10.1109/SCAC.2014.23
Lin, Cheng Hung ; Wang, Guan Hong ; Huang, Chun Cheng. / Hierarchical parallelism of bit-parallel algorithm for approximate string matching on GPUs. Proceedings - 2014 Symposium on Computer Applications and Communications, SCAC 2014. Institute of Electrical and Electronics Engineers Inc., 2014. pp. 76-81
@inproceedings{c55220f9eeb24ca083ee5532f27e5f61,
title = "Hierarchical parallelism of bit-parallel algorithm for approximate string matching on GPUs",
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 = "approximate string matching, bit-parallel algorithm, graphic processing units",
author = "Lin, {Cheng Hung} and Wang, {Guan Hong} and Huang, {Chun Cheng}",
year = "2014",
month = "9",
day = "29",
doi = "10.1109/SCAC.2014.23",
language = "English",
pages = "76--81",
booktitle = "Proceedings - 2014 Symposium on Computer Applications and Communications, SCAC 2014",
publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

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 -