Optimización de la factorización de matrices no negativas en Bioinformática

  1. Mejía Roa, Edgardo
Zuzendaria:
  1. Francisco Tirado Fernández Zuzendaria
  2. Alberto Pascual Montano Zuzendaria

Defentsa unibertsitatea: Universidad Complutense de Madrid

Fecha de defensa: 2016(e)ko otsaila-(a)k 02

Epaimahaia:
  1. Katzalin Olcoz Presidentea
  2. Luis Piñuel Moreno Idazkaria
  3. José María Carazo García Kidea
  4. Víctor Viñals Yufera Kidea
  5. Ana María Ripoll Aracil Kidea
Saila:
  1. Arquitectura de Computadores y Automática

Mota: Tesia

Laburpena

En los últimos años se ha incrementado el interés de la comunidad científica en la Factorización de matrices no negativas (NMF). Este método permite transformar un conjunto de datos de grandes dimensiones en una pequeña colección de elementos que poseen semántica propia en el contexto del análisis. En el caso de Bioinformática, NMF suele emplearse como base de algunos métodos de agrupamiento de datos, que emplean un modelo estadístico para determinar el número de clases más favorable. Este modelo requiere de una gran cantidad de ejecuciones de NMF con distintos parámetros de entrada, lo que representa una enorme carga de trabajo a nivel computacional. Por ello, esta tesis doctoral se centra en la optimización y paralelización de la factorización NMF, pero no solo a nivel teórico, sino con el objetivo de proporcionarle a la comunidad científica una nueva herramienta para el análisis de datos de origen biológico. NMF expone un alto grado de paralelismo a nivel de datos, de granularidad variable. Los métodos de agrupamiento mencionados anteriormente presentan un paralelismo a nivel de cómputo, ya que las diversas instancias de NMF que se ejecutan son independientes. Por tanto, se plantea un modelo de optimización por capas donde se emplean diferentes tecnologías de alto rendimiento. El nivel inferior, de menor granularidad, corresponde a los productos de matrices que componen NMF. Un primer intento consistió en emplear la biblioteca de rutinas optimizadas de álgebra lineal, ATLAS (Automatically Tuned Linear Algebra Software). Posteriormente, se aprovecharon las capacidades de cómputo de las Unidades de procesamiento de gráficos (GPU). Para los primeros dispositivos programables se desarrolló una versión de NMF empleando el modelo de Procesamiento de flujos (Stream Processing) e implementada en OpenGL y Cg. Más adelante apareció otro paradigma, CUDA (Compute Unified Device Architecture), con el que se obtuvo una ganancia en tiempo muy importante respecto a la versión de base. No obstante, en el caso de dispositivos GPU discretos (normalmente dotados de una memoria específica de poca capacidad), las matrices de gran tamaño se deben procesar por bloques que deben previamente transferirse desde la memoria principal. En estos casos, la repercusión en el rendimiento suele ser importante. El nivel intermedio, de grano más grueso, puede establecerse en la distribución de los datos entre diversos elementos de cómputo. Así, todos los elementos trabajan simultáneamente, cada uno aplicando alguna de las tecnologías del nivel inferior al subconjunto de datos que le es asignado. La implementación de este nivel se ha llevado a cabo utilizando MPI. En un sistema multi-GPU se obtiene una ganancia superlineal respecto de un único dispositivo, ya que cada unidad debe ocuparse de un problema más pequeño, que no desborda la memoria y evita las continuas transferencias de datos. Finalmente, el nivel superior corresponde a todas las instancias de NMF que son ejecutadas por los métodos de agrupamiento. Estas pueden distribuirse entre varios sistemas de cómputo (por ejemplo, entre diversos clusters de GPU), donde cada uno aplique las técnicas de los niveles inferiores. En este caso se desarrolló una infraestructura capaz de aprovechar las ventajas de las redes Grid. La nueva aplicación incluye una fase de preprocesamiento de matrices, así como una etapa posterior que genera una versión gráfica de los resultados. También dispone de interfaces web y de servicios web. Para facilitar aún más su utilización se dispuso de una versión pública en línea, de uso gratuito y anónimo, a través de la dirección http://bionmf.dacya.ucm.es. Esta tuvo buena acogida por parte de la comunidad bioinformática, obteniendo una media de 75 trabajos mensuales procedentes de distintos países. Si bien esta aplicación aún puede ser mejorada, supone una excelente herramienta que ayude al trabajo que a diario realizan los investigadores.