English   español  
Por favor, use este identificador para citar o enlazar a este item: http://hdl.handle.net/10261/90195
Compartir / Impacto:
Estadísticas
Add this article to your Mendeley library MendeleyBASE
Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Título

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

AutorDíaz, David ; Esteban, Francisco J.; Hernández Molina, Pilar ; Caballero, Juan Antonio; Dorado, Gabriel; Gálvez, Sergio
Palabras claveSystem-on-chip
Multi-core parallelization
Tile64 processor
Chip multiprocessor architecture
Needleman–Wunsch
Smith–Waterman
Multithreading
High performance optimization
Fecha de publicaciónabr-2011
EditorElsevier
CitaciónParallel Computing 37(4-5): 244-259 (2011)
ResumenCurrent 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. Gálvez, D. Díaz, P. Hernández, 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 ∼1000% when compared with the same algorithm on a ×86 multi-core architecture. As far as we know, our NW/SW implementation is the fastest ever published for a standalone PC when aligning a pair of sequences larger than 20 kb. © 2011 Elsevier Inc. All rights reserved.
URIhttp://hdl.handle.net/10261/90195
DOI10.1016/j.parco.2011.03.003
Identificadoresdoi: 10.1016/j.parco.2011.03.003
issn: 0167-8191
Aparece en las colecciones: (IAS) Artículos
Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
accesoRestringido.pdf15,38 kBAdobe PDFVista previa
Visualizar/Abrir
Mostrar el registro completo
 

Artículos relacionados:


NOTA: Los ítems de Digital.CSIC están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.