Introducción

El BLAST (Basic Local Alignment Search Tool) es un algoritmo y un programa informático de alineamiento de secuencias de tipo local, ya sea de ADN o de proteínas, empleado en bioinformática. El programa es capaz de comparar una secuencia problema contra una gran cantidad de secuencias que se encuentren en una base de datos y encontrar las que tienen mayor parecido así como la significación de cada resultado [1].

Muchas variantes han sido creadas para resolver algunos problemas específicos de búsqueda, pero BLAST es la herramienta más usada para la anotación y predicción funcional de genes o secuencias proteicas. BLAST es desarrollado por los Institutos Nacionales de Salud del gobierno de EE.UU., por lo que es de dominio público y puede usarse gratuitamente desde el servidor del Centro Nacional para la Información Biotecnológica (NCBI). No obstante, en el NCBI no se pueden hacer busquedas masivas al ser un recurso público y compartido [2].

El Servicio General de Informática Aplicada a la Investigación (IZO/SGI) de la UPV/EHU ha instalado y comparado 3 versiones diferentes de BLAST con el objeto de poder realizar cálculos másivos con BLAST. Para realizar cálculos masivos es necesario poder paralelizar el programa para poder emplear muchos cores simultáneamente. Una forma trivial es dividir el fichero de secuencias a estudiar en múltiples ficheros y enviarlos paralelamente y de forma independiente. Este método es complementario a cualquiera de las versiones estudiadas y es técnicamente sencillo. No obstante, tiene el inconveniente de tener que partir los datos iniciales para tras el cálculo tener que reagruparlos, cada uno de los procesos puestos en marcha debe de leer una copia de la base de datos lo cual es muy pesado y puede suponer un una importante carga para el servidor de datos, teniendo N cores no permite un reparto óptimo de la carga al no ser trivial el reparto de los procesos de forma homogénea en los recursos. Estos inconvenientes tendrán mayor o menor importacia dependiendo de la arquitectura y configuración del ordenador o cluster empleado.

Por ello, hemos escogido tres programas que paralelizan BLAST de forma diferente pero directa y que en cualquiera de los casos producen resultados idénticos: el proporcionado por el NCBI, gpuBLAST [3] y mpiBLAST [4]. Los benchmark se han ejecutado en nodos Xeon de 8 cores a 2.24 GHz y con una tarjeta Tesla C2070 y este software está instalado en las máquinas del IZO-SGI [5].

NCBI BLAST

Programa proporcionado con el NCBI capaz de abrir hilos de ejecución lo que lo limita a tener que ejecutarse en un único nodo y paralelizarse en tantos hilos como cores tiene el nodo (no se ha medido con hyperthreading activado). Con este programa hemos chequeado primero la dependencia del cálculo con el formato de la base de datos, en concreto con el tamaño máximo de cada fichero de la misma.

En la tabla 1 podemos ver como al reducir el tamaño máximo permitido para los ficheros que contienen la base de datos NR se aumenta el rendimiento de blastx de forma considerable. Por ello, no es recomendable la instalación de las bases de datos blast preformateadas que ofrece NCBI, pues son ficheros muy grandes cuyo rendimiento en ordenadores de muchos cores se ve penalizado al no poder repartir la carga en los cores adecuadamente. Es por tanto conveniente formatear manualmente las bases de datos produciendo un número suficiente de ficheros o fragmentos de base de datos. Hemos detectado también que el trocear la base de datos aumenta el rendimiento si se usan varios cores pero se penaliza si se usa únicamente 1.

En cuanto a la escalabilidad de NCBI se ve en la tabla 2 que es muy buena. En un core empleó 17002 segundos en ejecutarse y en 8 cores 2658 segundos, lo cual representa una aceleración de 6.3 y una eficiencia de la paralización del 80%.

mpiBLAST

Programa desarrollado a partir del de NCBI y que le implementa la paralelización. Para ello divide la base de datos BLAST en fragmentos que reparte entre los cores, cada uno de los cuales hace la busqueda en sus fragmentos asignados. Es conveniente formatear la base de datos de tal modo que cada core trabaje sobre un único fragmento. El IZO-SGI realizó un informe en el 2008 sobre el rendimiento de mpiBLAST con intención de poder predecir los requerimientos de tiempo y memoria de mpiBLAST [6]. Se vió que mpiBLAST escala linealmente en ambos casos, a mayor número de nodos (y fragmentos de la base de datos) menor tiempo y menor memoria. Esto convierte a mpiBLAST en una aplicación ideal para su uso en clusters de muchos nodos pequeños (por ejemplo el grid Pendulo del IZO-SGI [7]) dado que permite reducir el tamaño de cada proceso de forma que entre en la memoria RAM del ordenador. Hay que mencionar que mpiBLAST está implementado sobre una versión más antigua del NCBI, por lo que esto puede suponer una penalización en su rendimiento.

Hemos comparado mpiBLAST con el NCBI blast. mpiBLAST se ha ejecutado en 24 cores, no obstante sólo usa para la búsqueda en la base de los 22 cores pues 2 son siempre usados para la gestión del resto de procesos. Hemos decidido por ello compararlo con los 22 cores que realizan el cálculo. Comparándolo con el cálculo en un solo core (37601 s.) mpiBLAST supone una aceleración de 17 y un redimiento de la paralelización del 78%, es decir, paraleliza muy bien al compararlo con el cálculo en un core.

gpuBLAST

Existen varias implementeaciones de BLAST para GPGPUs pero hemos seleccionado ésta dado que produce exactamente los mismos resultados que el NCBI BLAST, solo está implementado el uso de GPGPUs en blastp. Hemos ejecutado gpuBLAST en tarjetas C2070 de última generación para cálculo científico.

Como se observa en la tabla 4 gpuBLAST multiplica por 2.5 la velocidad de ejecución respecto a la versión que se ejecuta en un core. No obstante, los nodos tienen varios cores  que sería absurdo no usar y si ejecutamos NCBI-BLAST usando los 8 cores logramos una aceleración cercana a 8 que bate a la ejecución de gpuBLAST. Igualmente podemos ejecutar gpuBLAST usando todos los cores más la GPGPU. El multiplicar el número de cores por 8 (+GPGPU) en esta ocasión no múltiplica por 8 la velocidad de ejecución de sistema con 1 core con GPGPU dado que gran parte del trabajo ya lo está realizando la GPGPU y solo se acelera la parte que estaba realizando el core. De este modo conseguimos acelerar por 3 nuevamente la ejecución y conseguimos el mejor resultado pero sólo es un 20% más rápido que usar los 8 cores. Las GPGPUs pueden ser una alternativa para acelerar la ejecución de BLAST en ordenadores con poco potencia donde añadir una GPGPU de gama medía podría mejorar sensiblemente los resultados. No obstante, para servidores de gama alta con muchos cores el uso de la GPGPU no mejora el resultado de forma muy significativa.

Referencias

[1] NCBI-BLAST (wikipedia): http://es.wikipedia.org/wiki/BLAST
[2] NCBI-BLAST: http://blast.ncbi.nlm.nih.gov/Blast.cgi
[3] Artículo sobre gpuBLAST: http://bioinformatics.oxfordjournals.org/content/27/2/182
[4] Artículo sobre mpiBLAST: http://synergy.cs.vt.edu/pubs/papers/darling-cwce2002-mpiblast.pdf
[5] Software en el IZO-SGI: http://www.ehu.es/sgi/software-de-calculo/software-de-calculo-disponible
[6] Infome del IZO-SGI sobre mpiBLAST: http://www.ehu.es/sgi/software-de-calculo/mpiblast
[7] Grid Péndulo: http://www.ehu.es/sgi/recursos/cluster-pendulo