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

Cheng Hung Lin*, Guan Hong Wang, Chun Cheng Huang

*此作品的通信作者

研究成果: 書貢獻/報告類型會議論文篇章

4 引文 斯高帕斯(Scopus)

摘要

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.

原文英語
主出版物標題Proceedings - 2014 Symposium on Computer Applications and Communications, SCAC 2014
發行者Institute of Electrical and Electronics Engineers Inc.
頁面76-81
頁數6
ISBN(電子)9780769553191
DOIs
出版狀態已發佈 - 2014 九月 29
事件2014 Symposium on Computer Applications and Communications, SCAC 2014 - Weihai, 中国
持續時間: 2014 七月 262014 七月 27

出版系列

名字Proceedings - 2014 Symposium on Computer Applications and Communications, SCAC 2014

其他

其他2014 Symposium on Computer Applications and Communications, SCAC 2014
國家/地區中国
城市Weihai
期間2014/07/262014/07/27

ASJC Scopus subject areas

  • 電腦網路與通信
  • 電腦科學應用

指紋

深入研究「Hierarchical parallelism of bit-parallel algorithm for approximate string matching on GPUs」主題。共同形成了獨特的指紋。

引用此