High-performance parallel location-aware algorithms for approximate string matching on GPUs

Cheng Hung Lin, Chun Cheng Huang

研究成果: 書貢獻/報告類型會議貢獻

摘要

Approximate string matching has been widely used in many applications, including deoxyribonucleic acid sequence searching, spell checking, text mining, and spam filters. The method is designed to find all locations of strings that approximately match a pattern in accordance with the number of insertion, deletion, and substitution operations. Among the proposed algorithms, the bit-parallel algorithms are considered to be the best and highly efficient algorithms. However, the traditional bit-parallel algorithms lacks the ability of identifying the start and end positions of a matched pattern. Furthermore, acceleration of the bit-parallel algorithms has become a crucial issue for processing big data nowadays. In this paper, we propose two kinds of parallel location-aware algorithms called data-segmented parallelism and high-degree parallelism as means to accelerate approximate string matching using graphic processing units. Experimental results show that the high-degree parallelism on GPUs achieves significant improvement in system and kernel throughputs compared to CPU counterparts. Compared to state-of-the-art approaches, the proposed high-degree parallelism achieves 11 to 105 times improvement.

原文英語
主出版物標題Proceedings - 2015 IEEE 21st International Conference on Parallel and Distributed Systems, ICPADS 2015
發行者IEEE Computer Society
頁面570-575
頁數6
ISBN(電子)9780769557854
DOIs
出版狀態已發佈 - 2016 一月 15
事件21st IEEE International Conference on Parallel and Distributed Systems, ICPADS 2015 - Melbourne, 澳大利亚
持續時間: 2015 十二月 142015 十二月 17

出版系列

名字Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS
2016-January
ISSN(列印)1521-9097

其他

其他21st IEEE International Conference on Parallel and Distributed Systems, ICPADS 2015
國家澳大利亚
城市Melbourne
期間15/12/1415/12/17

ASJC Scopus subject areas

  • Hardware and Architecture

指紋 深入研究「High-performance parallel location-aware algorithms for approximate string matching on GPUs」主題。共同形成了獨特的指紋。

  • 引用此

    Lin, C. H., & Huang, C. C. (2016). High-performance parallel location-aware algorithms for approximate string matching on GPUs. 於 Proceedings - 2015 IEEE 21st International Conference on Parallel and Distributed Systems, ICPADS 2015 (頁 570-575). [7384340] (Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS; 卷 2016-January). IEEE Computer Society. https://doi.org/10.1109/ICPADS.2015.77