Browsing by Author "Chang, Hao-Ping"

Filter results by typing the first few letters
Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    以多圖形處理器加速近似字串比對
    (2012) 張浩平; Chang, Hao-Ping
    字串比對在許多領域中被廣泛運用，例如網路入侵偵測系統、網際網路搜尋、去氧核糖核酸序列比對等等；其中，字串比對可區分為固定字串比對與近似字串比對兩類。固定字串比對是指找出所有字串樣式於輸入文字中出現的位置，所有字串樣式必須精確的比對，不容許任何錯誤；而所謂近似字串比對是指所搜尋的字串樣式則可經由插入、刪除及替代等有限次數的動作，轉換成輸入文字中的某部分。近似字串比對的演算法可區分為dynamic programming與bit-parallelism；Dynamic programming需經龐大運算及記憶體空間記錄誤差值，故在處理大量資料時，將為此演算法之瓶頸；反之，bit-parallelism運用邏輯運算子模擬非確定有限狀態自動機進行比對，速度快且節省記憶體。 近似字串比對的運算量大且非常耗費時間，尤其在針對大量的輸入文字比對大量的字串樣式時，其耗費的時間更為明顯。本研究將分析並實現bit-parallelism與dynamic programming於NVIDIA GPU上，實驗結果顯示在處理2Gbytes的輸入文字時，執行於單一個GPU的bit-parallelism較執行於單一執行緒CPU版本的bit-parallelism快上7倍的加速。本研究並進一步透過openMP連結多個GPU的加速，其結果顯示在處理2Gbytes的輸入文字時，以2個GPU加速之bit-parallelism較執行於單一執行緒CPU版本的bit-parallelism快上10倍的速度。