Parallelizing and optimizing a bioinformatics pairwise sequence alignment algorithm for many-core architecture

作     者：Diaz, David Jose Esteban, Francisco Hernandez, Pilar Antonio Caballero, Juan Dorado, Gabriel Galvez, Sergio 

作者机构：Univ Malaga ETSI Informat Dep Lenguajes & Ciencias Computac E-29071 Malaga Spain Univ Cordoba Serv Informat E-14071 Cordoba Spain Inst Agr Sostenible IAS CSIC Cordoba 14080 Spain Univ Cordoba Dep Estadist E-14071 Cordoba Spain Univ Cordoba Dep Bioquim & Biol Mol E-14071 Cordoba Spain 

出 版 物：《PARALLEL COMPUTING》 (并行计算)

年 卷 期：2011年第37卷第4-5期

页      面：244-259页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Ministerio de Ciencia e Innovacion [AGL2010-17316, BIO2009-07443-E] "Consejeria de Agricultura y Pesca" of "Junta de Andalucia" [041/C/2007, 75/C/2009, 56/C/2010] Grupo PAI [AGR-248] "Universidad de Cordoba" ("Ayuda a Grupos"), Spain 

主　　题：Tile64 processor Multi-core parallelization System-on-chip Chip multiprocessor architecture Needleman-Wunsch Smith-Waterman High performance optimization Multithreading 

摘      要：Current computer engineering evolves at an accelerated pace, with hardware advancing towards new chip multiprocessors (CMP) architectures and with supporting software gearing towards new programming and abstraction paradigms, to obtain the maximum efficiency of the hardware at a low cost. In this context, Tilera Corporation has developed a brand new CMP architecture with 64 cores (tiles) called Tile64, and has launched several Peripheral Component Interconnect Express (PCIe) cards to be used and monitored from a host Personal Computer (PC). These cards may execute parallel applications built in C/C++ and compiled with the Tile-GCC compiler. We have previously demonstrated the usefulness of the Tile64 architecture for bioinformatics [S. Galvez, D. Diaz, P. Hernandez, F.J. Esteban, J.A. Caballero, G. Dorado, Next-generation bioinformatics: using many-core processor architecture to develop a web service for sequence alignment, Bioinformatics, 26 (2010) 683-686]. We have chosen a bioinformatics algorithm to test this many-core Tile64 architecture because of actual bioinformatics challenging needs: data-intensive workloads, space and time-consuming requirements and massive calculation. This algorithm, known as Needleman-Wunsch/Smith-Waterman (NW/SW), obtains an optimal sequence alignment in quadratic time and space cost, yet requires to be optimized to take full advantage of computing parallelization. In this paper we redesign, implement and fine-tune this algorithm, introducing key optimizations and changes that take advantage of specific Tile64 characteristics: RISC architecture, local tile s cache, length of memory word, shared memory usage, RAM file system, tile s intercommunication and job selection from a pool. The resulting algorithm - named MC64-NW/SW for Multicore64 Needleman-Wunsch/Smith-Waterman - achieves a gain of similar to 1000% when compared with the same algorithm on a x86 multi-core architecture. As far as we know, our NW/SW implementation is the fastes