Implementación del algoritmo de Smith - Waterman utilizando instrucciones SIMD mediante OPENMP

Abstract

El presente trabajo aborda el problema de acelerar la ejecución del algoritmo de Smith-Waterman haciendo uso de las instrucciones vectoriales disponibles en las CPU modernas. Como ejemplo de implementaciones de Smith-Waterman podemos citar a Swipe[8], que está implementada con funciones intrínsecas y secciones de ensamblador, optimizada para usar instrucciones SSE. El problema de muchas de estas implementaciones es que no son portables, además de no ser fácilmente mantenibles. Para poder ejecutarse en una arquitectura diferente, muchas veces es necesario reescribir la aplicación. La propuesta del presente trabajo es utilizar OpenMP para desarrollar una implementación portable del algoritmo de Smith-Waterman acelerada mediante instrucciones vectoriales. Utilizar OpenMP permitirá resolver el problema de la portabilidad de rendimiento para este algoritmo. Gracias al uso de OpenMP, fue posible acelerar la ejecución del algoritmo de Smith-Waterman dramáticamente con respecto a la versión que no utiliza instrucciones vectoriales, consiguiendo un rendimiento que rivaliza con una implementación vectorizada con funciones intrínsecas.