跳到主要內容

臺灣博碩士論文加值系統

(100.24.118.144) 您好!臺灣時間:2022/12/06 05:40
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:紀佳瑋
研究生(外文):Jia-Wei Chi
論文名稱:利用GPGPU 搭配CUDA 語言平行化加速生物 演算法Smith-Waterman 的序列比對
論文名稱(外文):GPGPU with CUDA for Accelerating the Smith-Waterman Sequence Alignment Process
指導教授:陳依蓉陳依蓉引用關係
指導教授(外文):Yi-Jung Chen
口試委員:吳瑞瑜黃育銘陳依蓉
口試委員(外文):Ruei-Yu WuYuh-Ming HuangYi-Jung Chen
口試日期:2014-07-17
學位類別:碩士
校院名稱:國立暨南國際大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2014
畢業學年度:102
語文別:中文
論文頁數:37
中文關鍵詞:生物資訊學搜尋比對史密斯演算法圖形處理單元統一計算架構
外文關鍵詞:BioinformationSearch alignmentSmith-Waterman algorithmGPUCUDA
相關次數:
  • 被引用被引用:0
  • 點閱點閱:297
  • 評分評分:
  • 下載下載:49
  • 收藏至我的研究室書目清單書目收藏:0
目前在生物資訊學中時常必須針對兩條序列進行搜尋比對,找出兩條序列相似的片段。隨著科技及資訊的進步,資料庫中累積的序列數量急速的增加,為了滿足及解決大量搜尋的需求,於是有人提出了各式各樣的搜尋比對工具,如Smith-Waterman、BLAST、…等搜尋比對演算法。由於資料庫越來越大,搜尋的時間已經無法在期望的時間內完成,所以往往期望能有一個更好的加速比對技術。然而GPGPU 本身擁有的多個計算單元適用於大量的資料運算,且再搭配上CUDA 語言即可充分的發揮
GPGPU 的計算效能。在本篇論文中我們使用了GPGPU 來當作平行化計算的設備,並提出了一個平行化的計算方式和優化記憶體的方法,改善Smith-Waterman 演算法的搜尋效率, 藉此可以減少執行的時間, 達到一個較好的效率提升。
In bioinformatics, we often have to search for the similarity of the two sequences to identify similar fragments of two sequences. For more advanced technology &information progress, the number of sequence accumulated in the databases increases rapidly in order to solve a large number of searching. So there are a lot of search algorithms & tools had been suggested, such as Smith-Waterman, BLAST …, etc. Due to the size of database growing, the search time increase and could not completed search job within a requested time. How to find a better algorithm to accelerate the search speed is what we’re looking for. The GPGPU( General Purpose GPU), own a lot of SP(Streaming Processor) , is very suitable for large computing requirements. Under the specific support of particular language CUDA, GUGPU can fully perform well. In this paper we use the GPGPU as the parallel computing platform. We present a parallel method of calculation and also provide
the way of optimization of memory to improve the efficiency of Smith-Waterman search algorithm. It makes us reduce the execution time to achieve a better efficiency.
中文摘要‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧I
Abstract‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧II
目次‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧III
圖次‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧IV
表次 ‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧VI
第一章 背景與介紹‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧01
1.1 生物演算法背景與其加速方法之介紹‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧01
1.2 主要貢獻‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧03
1.3 本論文的組織‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧04
第二章 Smith-Waterman 序列比對演算法‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧05
第三章 GPGPU 架構與CUDA 語言 ‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧10
第四章 相關文獻探討‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧19
第五章 利用GPGPU 加速Smith-Waterman 演算法比對‧‧‧‧‧‧‧‧‧‧‧21
5.1 已有之GPGPU 加速方法之問題‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧21
5.2 優化加速的方法‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧24
5.2.1 依照獨立性運算相似度矩陣‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧25
5.2.2 Share 記憶體與Constant 記憶體 ‧‧‧‧‧‧‧‧‧‧‧‧‧‧26
5.2.3 資料預取‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧28
第六章 效能評估‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧30
第七章 結論‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧34
參考文獻‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧35
[1]Altschul SF, Madden TL, Schäffer AA, Zhang J, Zhang Z, Miller W, Lipman DJ, Gapped BLAST and PSI-BLAST: a new generation of protein database search programs, Nucleic Acids Res, 1997.
[2]C.W. Yu, K.H. Kwong, K.H. Lee, P.H.W. Leong, A smith-waterman systolic cell, 2005.
[3]Edans Flavius O. Sandes, Alba Cristina M.A. de Melo, CUDAlign: Using GPU to Accelerate theComparison of Megabase Genomic Sequences, in Proc. IEEE Symp.Principles and Practice of Parallel Programming (PPoPP 10), IEEEPress, Jan. 2010.
[4]Graphics Processing Unit(GPUs):Architecture and Programming. http://cs.nyu.edu/courses/spring12/CSCI-GA.3033-012/.
[5]Gregory M. Striemer, Ali Akoglu, Sequence Alignment with GPU: Performance and Design Challenges, IPDPS IEEE, May 2009, 1-10.
[6]Implementation of the smith-waterman algorithm on a reconfigurable supercomputing platform, Altera White Paper, September 2007.
[7]ŁukaszLigowski, WitoldRudnicki,An efficient implementation of SmithWaterman algorithm on GPU using CUDA, for massively parallelscanning of sequence databases, in Proc. IEEE InternationalSymposium on Parallel and Distributed Processing (iPDPS 09), IEEEPress, May, 2009.
[8]Manavski, S.S.: Smith-Waterman User Guide.http://bioinformatics.cribi.unipd.it/cuda/docs/SWCudaUserGuide.pdf
[9]Matrix made by matblas from blosum62, May, 2008.http://www.ncbi.nlm.nih.gov/Class/FieldGuide/BLOSUM62.txt.
[10]Michael Farrar, Striped Smith-Waterman speeds database searches sixtimes over other SIMD implementations, Bioinformatics 23, 2007, pp 156,161.
[11]NCBI Toolkit Cross Reference. http://www.ncbi.nlm.nih.gov/IEB/ToolBox/C_DOC/lxr/source/data/BLOSUM50.
NCBI: National Center for Biotechnology Information.
[12]NVIDIA Corporation: NVIDIA CUDA compute unified devicearchitecture programming guide.http://www.nvidia.com/object/cuda_develop.html.
[13]Performance Evaluation and Modeling of Smith-Waterman algorithm on HPC Plateform.
[14]Popular GPU – Accelerated applications.http://www.nvidia.com/docs/IO/123576/nv-applications-catalog-lowres.pdf.
[15]Qian Zhang, Hong An, Gu Liu, Wenting Han, Ping Yao, Mu Xu, Xiaoqiang Li, The Optimization of Parallel Smith-Waterman Sequence Alignment Using On-Chip Memory of GPGPU, BIC-TA IEEE, 2010, 844-850.
[16]Sean R Eddy,Where did the BLOSUM62 alignment score matrix comefrom?, Nature Biotechnology, 22:1035-1036.
[17]ShuaiChe, Michael Boyer, JiayuanMeng, David Tarjan,Jeremy W. Sheaffer, Kevin Skadron,A performance study of general-purpose applications ongraphics processors using CUDA,elsevior, J. Parallel Distrib. Comput.68(2008), pp. 1370-1380.
[18]Smith-Waterman algorithm function. http://en.wikipedia.org/wiki/Smith_waterman.
[19]Spring 2010 Syllabus. (Tentative)http://courses.engr.illinois.edu/ece498al/Syllabus.html
[20]Stephen F. Altschul, Warren Gish, Webb Miller, Eugene W. Myers, David J. Lipman, Basic local alignment search tool, J MolBiol, 1990.
[21]Svelin A Manavski, Giorgio Balle, CUDA compatible GPU cards as efficienthardware accelerators for Smith-Waterman sequence alignment, BMC Bioinformatics 2008.
[22]T. F. Smith, M. S. Waterman, Identification of common molecular subsequences, Journal of Molecular Biology, 1981, V147, 195-197.
[23]UniProtKB/Swiss-Prot protein knowledgebase release 2014_05 statistics. http://web.expasy.org/docs/relnotes/relstat.html.
[24]Weiguo Liu, Bertil Schmidt, Gerrit Voss, and Wolfgang Mu¨ller-Wittig,Streaming Algorithms for Biological SequenceAlignment on GPUs, IEEE Trans, vol. 18, no.9, Sep, 2007.
[25]Y. Liu, W. Huang, J. Johnson, and S. Vaidya, GPU AcceleratedSmith-Waterman, in ICCS, vol. 399412006, pp. 188-195.
[26]Yongchao Liu, Douglas L. Maskell and Bertil Schmidt, CUDASW++: optimizingSmith-Waterman sequence database searches for CUDA-enabledgraphics processing units, BMC Research Notes, May. 2009.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊