發展以圖形處理器為基礎之高效能近似字串比對平行演算法

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 project, 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. The research results have been presented at the 2014 IEEE Symposium on Computer Applications and Communications (SCAC) and the 25th VLSI Design/CAD Symposium, 2014. We also implement a web-based interface allowing users to conduct approximate string matching using NVIDIA GPUs. (http://140.122.105.151/approximate_string_matching/).