Browsing by Author "Huang, Chun-cheng"

Filter results by typing the first few letters
Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    實現於圖形處理器的高性能平行位置檢知近似字串比對演算法
    (2017) 黃俊程; Huang, Chun-cheng
    近似字串比對被廣泛的應用於各種不同的領域。例如：去氧核糖核酸序列搜尋比對、電腦文字輸入校正、文字資料探勘以及垃圾電子郵件過濾等。近似字串比對的設計是用來搜索文件中所有近似字串文字樣式字串及使用者定義的插入、刪除、取代的容許誤差值搜索後的匹配的位置。在眾多被提出的近似字串比對演算法中，位元平行演算法被認定是最適、最有效率的演算法。然而，傳統的位元平行演算法無法同時偵測樣式字串匹配字串的起始及結束位置。除此之外，因應現代多核心處理器的硬體發展，以及叢集運算、雲端運算以及大數據處理的需求。如何加速位元平行演算法成為當今重要的課題。本研究分別提出利用多串流平行和高維度平行這兩種位置偵測近似字串比對方法並利用圖形運算處理器(GPU)來加速演算法。實驗結果顯示，比較高維度平行演算法在圖形運算處理器(GPU)以及CPU的執行效能，圖形運算處理器(GPU)版本無論是在作業系統執行環境或者是在圖形顯示處理(GPU)核心執行的情況，效能皆得到顯著的提升。相較於其他相關研究，本研究所提出的高維度平行的方法達到了 11 至 105 倍的效能改善。最終，我們開發了一個讓使用者可以在線上執行位置偵測近似字串比對並找出所有樣式字串匹配結果起點及終點位置網路服務。