蛋白质序列比对算法在众核结构上的并行优化
基金项目:

Supported by the National Natural Science Foundation of China under Grant No.60736012 (国家自然科学基金); the National Basic Research Program of China under Grant No.2005CB321600 (国家重点基础研究发展计划(973))


Efficient Parallelization and Optimization of Protein Sequence Comparison Algorithm on Many-Core Architecture
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [32]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    在生物信息学中,蛋白质序列比对是最为重要的算法之一,生物技术的发展使得已知的序列库变得越来越庞大,这类算法本身又具有计算密集型的特点,这导致进行序列比对所消耗的时间也越来越长,目前的单核或者数量较少的多核系统均已经难以满足对计算速度的要求.Godson-T是一个包含诸多创新结构的众核平台,在该系统上实现了对一种蛋白质序列比对算法的并行化,并且结合蛋白质比对算法以及Godson-T结构的特征,针对同步开销、存储访问竞争以及负载均衡3个方面对算法进行了细致的优化,最终并行部分整体也获得了更优的、接近线性的加速比,并且实际性能远远优于基于AMD Opteron处理器的工作站平台.

    Abstract:

    In bioinformatics, a protein sequence comparison between two banks is one of most important algorithms. The sequence bank size is becoming larger and larger with the development of biotechnology, while the algorithm is also computation intensive. This leads to more and more consumption time and the single processor or multicore system, with only a few cores, are not powerful enough to reach a satisfying speed nowadays. Godson-T is a new kind of many-core architecture with lots of novel features. The parallelization of a protein sequence comparison algorithm on Godson-T is implemented. At the same time, the algorithm structure and architecture features of Godson-T are combined, and some optimization in three aspects are made: synchronization overhead, memory access contention, and load balance. The result shows that a close to linear speedup is obtained, and the performance is much better than that of the workstation platform based on the AMD Opteron processor.

    参考文献
    [1] Smith TF, Waterman MS. Identification of common molecular subsequences. Jounal of Molecular Biology, 1981,147(1):195?197.
    [2] Needleman SB, Wunsch CD. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Jounal of Molecular Biology, 1970,48:443?453.
    [3] Gotoh O. An improved algorithm for matching biological sequences. Jounal of Molecular Biology, 1982,162:705?708.
    [4] Altschul SF, Madden TL, Schaffer AA, Zhang J, Zhang Z, Miller W, Lipman DJ. Gapped BLAST and PSI-BLAST: A new generation of protein database search programs. Nucleic Acids Research, 1997,25(17):3389?3402.
    [5] Pearson WR, Lipman DJ. Improved tools for biological sequence comparison. Proceedings of the National Academy of Sciences, 1988,85(8):2444?2448.
    [6] Guerdoux P, Lavenier D. Samba: Hardware accelerator for biological sequence comparison. Computer Application in BIOSciences, 1997,13(6):609?615.
    [7] Krishnamurthy P, Buhler J, Chamberlain R, Franklin M, Gyang K, Lancaster J. Biosequence similarity search on the mercury system. In: Proc. of the 15th IEEE Int’l Conf. on Application-Specific Systems, Architecture and Processors (ASAP 2004). 2004. 365?375. http://www.computer.org/portal/web/csdl/doi/10.1109/ASAP.2004.10011
    [8] Darling AE, Carey L, Feng W. The design, implementation, and evaluation of mpiBLAST. In: Proc. of the Int’l Conf. on Linux Clusters: The HPC Revolution. 2003. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.3974
    [9] Lavenier D, Giraud M. Bioinformatics applications. In: Proc. of the Reconfigurable Computing. Springer-Verlag, 2005. 157?182.
    [10] Vangal S, Howard J, Ruhl G, Dighe S, Wilson H, Tschanz J, Finan D, Lyer P, Singh A, Jacob T, Jain S, Venkataraman S, Hoskote Y, Borkar N. An 80-tile 1.28TFLOPS network-on-chip in 65nm CMOS. In: Proc. of the 2007 Int’l Solid-State Circuits Conf. 2007. 97?99. http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?&arnumber=4242283&abstractAccess=no&userType=inst
    [11] Gschwind M, Hofstee HP, Flachs B, Hopkins M, Watanabe Y, Yamazaki T. Synergistic processing in Cell’s multicore architecture. IEEE Micro, 2006,26(2):10?24.
    [12] Cuvillo D, Zhu W, Hu Z, Gao GR. TiNy threads: A thread virtual machine for the cyclops64 cellular architecture. In: Proc. of the 19th IEEE Int’l Parallel and Distributred Processing Symp. 2005. 265?272. http://www.computer.org/portal/web/csdl/doi/10.1109/ IPDPS.2005.434
    [13] Kucherov G, Noe L, Roytberg M. A unifying framework for seed sensitivity and its application to subset seeds. In: Proc. of the 5th Int’l Workshop on Algorithms in Bioinformatics. 2005. 251?263. http://www.springerlink.com/content/72384x40t0v2j254/
    [14] http://www.expasy.ch/sprot/, 2008.
    [15] Tan GM, Fan DR, Zhang JC, Russo A, Gao GR. Experience on optimizing irregular computation for memory hierarchy in manycore architecture. In: Proc. of the PpoPP 2008. 2008. 279?280. http://portal.acm.org/citation.cfm?id=1345255
    [16] Lin W, Ye XC, Song FL, Zhang H. Using write mask to support hybrid write-back and write-through cache policy on many-core architectures. Chinese Journal of Computers, 2008,31(11):1918?1928 (in Chinese with English abstract).
    [17] Iftode L, Singh J, Li K. Scope consistency: A bridge between release consistency and entry consistency. In: Proc. of the 8th Annual ACM Symp. on Parallel Algorithms and Architectures. 1996. 277?287. http://portal.acm.org/citation.cfm?id=237502.237567
    [18] Wang D, Tang ZM. The implementation and analysis of Smith-Waterman algorithm on systolic array. Chinese Journal of Computers, 2004,27(1):12?20 (in Chinese with English abstract).
    [19] Zhang F, Qiao XZ, Liu ZY. Parallel divide and conquer bio-sequence comparison based on Smith-Waterman Algorithm. Science in China Series E, 2004,34(2):190?199 (in Chinese).
    [20] Lavenier D, Guyetant S, Derrien S, Rubini S. A reconfigurable parallel disk system for filtering genomic banks. In: Proc. of the Engineering of Reconfigurable Systems and Algorithms (ERSA 2003). 2003. 154?166. http://www.irisa.fr/symbiose/lavenier/ Publications/Lav03cc.pdf
    [21] Chow E, Hunkapiller T, Peterson J, Waterman MS. Biological information signal processor. In: Proc. of the Int’l Conf. on Application Specific Array Processor. 1991. 144?160. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=238887
    [22] Roges T, Seeberg E. Six-Fold speed-up of Smith-Waterman sequence database searches using parallel processing on common microprocessors. 2000,16:699?706. http://bioinformatics.oxfordjournals.org/content/16/8/699.abstract
    [23] Farrar M. Striped Smith-Waterman speeds database searches six times over other SIMD implementations. Bioinformatics, 2007, 23(2):156?161.
    [24] Martin WS, Delcuvillo JB, Useche FJ, Theobald KB, Gao GR. A multithreaded parallel implementation of a dynamic programming algorithm for sequence comparison. In: Proc. of the Pacific Symp. on Biocomputing. 2001. 311?322. http://citeseerx.ist.psu.edu/ viewdoc/download?doi=10.1.1.88.6923&rep=rep1&type=pdf
    [25] Yap TK, Frieder O, Martino RL. Parallel computation in biological sequence analysis. IEEE Trans. on Parallel and Distributed Systems, 1998,9(3):283?294.
    [26] Muriki K, Underwood K, Sass R. RC-BLAST: Towards a portable, cost-effective open source hardware implementation. In: Proc. of the HiCOMB. 2005. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5222005
    [27] Lin H, Balaji P, Poole R, Sosa C, Ma X, Feng W. Massively parallel genomic sequence search on the blue Gene/P architecture. In: Proc. of the ACM/IEEE Conf. for High-Performance Computing, Networking, Storage and Analysis (SC). 2008. 1?11. http://en.cnki.com.cn/Article_en/CJFDTOTAL-JSJX200801014.htm
    [28] Wu N, Wen M, He Y, Xun CQ, Ren J, Chai J, Zhang CY. MASA stream architecture and evaluating foir a fluid computing application. Chinese Journal of Computers, 2008,31(1):133?141 (in Chinese with English abstract).
    附中文参考文献: [16] 林伟,叶笑春,宋风龙,张浩.众核处理器中使用写掩码实现混合写回/写穿透策略.计算机学报,2008,31(11):1918?1928.
    [18] 汪东,唐志敏.Smith-Waterman算法在脉动阵列上的实现及分析.计算机学报,2004,27(1):12?20.
    [19] 张法,乔香珍,刘志勇.基于Smith-Waterman算法的并行分而治之生物序列比对算法.中国科学(E辑),2004,34(2):190?199.
    [28] 伍楠,文梅,何义,荀长庆,任巨,柴俊,张春元.一种流处理器体系结构MASA及其在流体力学计算中的评测.计算机学报,2008, 31(1):133?141.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

叶笑春,林伟,范东睿,张浩.蛋白质序列比对算法在众核结构上的并行优化.软件学报,2010,21(12):3094-3105

复制
分享
文章指标
  • 点击次数:4827
  • 下载次数: 6776
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2008-09-23
  • 最后修改日期:2009-04-27
文章二维码
您是第19780903位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号