以圖形處理器加速近似字串比對之位元平行演算法

Abstract

近似字串比對被廣泛運用到很多領域，例如：網頁搜尋、網路入侵偵測系統、網路安全、去氧核糖核酸序列匹配等。近似字串比對可在輸入字串與樣式字串間容許因為插入、替代、刪除等操作所造成的誤差。因為近似字串比對是一種資料密集的運算，對於大數據的處理，加速近似字串比對成為非常重要的關鍵。本研究提出階層平行化的架構並實現於圖形處理器，以加速位元平行演算法。階層平行化的架構包括兩個階段。第一個階段使用多串流操作，用來隱藏記憶體IO的延遲，而第二個階段運用圖行處理器來加速位元平行演算法。位元平行演算法相較於CPU的平行化版本，GPU版本可獲得約3.5倍效能的改善。實驗結果顯示，相較於其他相關研究，本研究可以獲得5倍的改善。

Approximate string matching has been widely used in many areas, such as web searching, network intrusion detection system, network security, 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 thesis, we propose a hierarchical parallel architecture to accerelate approximate string matching on GPUs. The hierarchical parallel architecture composes of two levels. The top level is to use mulitiple streams to hide the laterency of data transfer between CPU and GPU while the second level is to accelerate the kernel function of the bit-parallel algorithm on GPUs. The experimental results show that the bit-parallel algorithm performed on GPUs achieves 3.5 times faster than the multithreaded CPU counterparts. Compared to the state-of-the-art approaches, this proposed approach achieves 5 times improvement.