EnglishUna característica fundamental de los sistemas de software es que se construyen desde el principio sabiendo que deberán incorporar cambios a lo largo de su ciclo de vida. Todos los libros que tratan sobre ingeniería de software coinciden en que los sistemas son evolutivos. Incluso al evaluar el esfuerzo que se debe invertir en un proyecto de software, se considera que un 20% está en el desarrollo y 80% se aplica al mantenimiento (Pfleeger & Atlee, 2009). Ian Sommerville estima que el 17% del esfuerzo de mantenimiento se invierte en localizar y eliminar los posibles defectos de los programas (Sommerville, 2006). Por ello, conseguir programas libres de errores es uno de los principales objetivos que se plantea (o se debería plantear) el desarrollador frente a cualquier proyecto de software.
Por otro lado, las limitaciones a la integración impuestas por factores físicos como son la temperatura y el consumo de energía, se han traducido en la integración de unidades de cómputo en un único chip, dando lugar a los procesadores de múltiples núcleos. Para obtener la máxima eficiencia de estas arquitecturas, es necesario el desarrollo de programas concurrentes (Grama, Gupta, Karypis, & Kumar, 2003). A diferencia de los programas secuenciales, en un programa concurrente existen múltiples hilos en ejecución accediendo a datos compartidos. El orden en que ocurren estos accesos a memoria puede variar entre ejecuciones, haciendo que los errores sean más difíciles de detectar y corregir.
En cómputo de altas prestaciones donde los tiempos de ejecución de las aplicaciones pueden variar de un par de horas hasta días, la presencia de un error no detectado en la etapa de desarrollo adquiere una importancia mayor. Por este motivo, resulta indispensable contar con herramientas que ayuden al programador en la tarea de verificar los algoritmos concurrentes y desarrollar tecnología robusta para tolerar los errores no detectados. En este contexto, la eficiencia de los programas monitorizados se ve comprometida por el overhead que introduce el proceso de monitorización.
Este trabajo forma parte de las investigaciones para la tesis doctoral del autor en el tema "Software para arquitecturas basadas en procesadores de múltiples núcleos. Detección automática de errores de concurrencia". Como tal, su aporte constituye un estudio de las técnicas y métodos vigentes en la comunidad científica aplicados a la detección y corrección de errores de programación en programas concurrentes.
Las siguientes secciones constituyen una introducción al proceso de detectar, localizar y corregir errores de software en programas secuenciales y se explican las complicaciones introducidas por los programas concurrentes. El Capítulo 2 trata los distintos errores que se pueden manifestar en programas concurrentes.
El Capítulo 3 resume los antecedentes en técnicas de detección y corrección de errores de concurrencia y se justifica la elección de las violaciones de atomicidad como caso de error más general. El Capítulo 4 explica las características de un algoritmo de detección de violaciones de atomicidad, y da detalles de su implementación. El Capítulo 5 contiene las características de la plataforma de experimentación y de la metodología empleada. El Capítulo 6 proporciona los resultados del trabajo experimental. Finalmente, se presentan las conclusiones del trabajo y se proponen las líneas de investigación futuras.
El aumento en la escala de integración, con el objetivo de mejorar las prestaciones en los procesadores actuales, sumado al crecimiento de los sistemas de cómputo, han producido que la fiabilidad se haya vuelto un aspecto relevante. En particular, la creciente vulnerabilidad a los fallos transitorios se ha vuelto crítica, a causa de la capacidad de estos fallos de corromper los resultados de las aplicaciones.
Históricamente, los fallos transitorios han sido una preocupación en el diseño de sistemas críticos, como sistemas de vuelo o servidores de alta disponibilidad, en los que las consecuencias del fallo pueden resultar desastrosas. Pese a ser fallos temporarios, tienen la capacidad de alterar el comportamiento del sistema de cómputo. A partir del año 2000 se han vuelto más frecuentes los reportes de desperfectos significativos en distintas supercomputadoras, debidos a los fallos transitorios.
El impacto de los fallos transitorios se vuelve más relevante en el contexto del Cómputo de Altas Prestaciones (HPC). Aun cuando el tiempo medio entre fallos (MTBF) es del orden de 2 años para un procesador comercial, en el caso de una supercomputadora con cientos o miles de procesadores que cooperan para resolver una tarea, el MTBF disminuye cuanto mayor es la cantidad de procesadores. Esta situación se agrava con el advenimiento de los procesadores multicore y las arquitecturas de cluster de multicores, que incorporan un alto grado de paralelismo a nivel de hardware. La incidencia de los fallos transitorios es aún mayor en el caso de aplicaciones de gran duración, que manejan elevados volúmenes de datos, dado el alto costo (en términos de tiempo y utilización de recursos) que implica volver a lanzar la ejecución desde el comienzo, en caso de obtener resulta-dos incorrectos debido a la ocurrencia del fallo.
Estos factores justifican la necesidad de desarrollar estrategias específicas para mejorar la con-fiabilidad en sistemas de HPC; en este sentido, es crucial poder detectar los fallos llamados silenciosos, que alteran los resultados de las aplicaciones pero que no son interceptados por el sistema operativo ni ninguna otra capa de software del sistema, por lo que no causan la finalización abrupta de la ejecución.
En este contexto, el trabajo analizará una metodología distribuida basada en software, diseñada para aplicaciones paralelas científicas que utilizan paso de mensajes, capaz de detectar fallos transitorios mediante la validación de contenidos de los mensajes que se van a enviar a otro proceso de la aplicación. Esta metodología, previamente publicada, intenta abordar un problema no cubierto por las propuestas existentes, detectando los fallos transitorios que permiten la continuidad de la ejecución pero que son capaces de corromper los resultados finales, mejorando la confiabilidad del sistema y disminuyendo el tiempo luego del cual se puede relanzar la aplicación, lo cual es especialmente útil en ejecuciones prolongadas.
El objetivo de este Trabajo Final es comparar el efecto de la distribución de trabajo estática y dinámica sobre arquitecturas de cluster heterogéneo, analizando al mismo tiempo el speedup paralelo teórico y el obtenido experimentalmente para un determinado tipo de problema.
En particular, se ha elegido una aplicación clásica (Parallel N-Queens) con un algoritmo de solución paralela en la que predomina el procesamiento sobre el tamaño de los datos, de modo de profundizar en los aspectos del balance de carga (estático o dinámico) sin una distorsión de los resultados producida por aspectos relacionados al uso de la memoria y/o al tamaño de los mensajes a comunicar.
Para la experimentación se ha utilizado una combinación de 4 clusters interconectados, donde las máquinas dentro de cada grupo poseen procesadores homogéneos, pero diferentes entre clusters. De este modo el conjunto puede verse como un cluster heterogéneo de 43 procesadores.
El problema se ha resuelto utilizando el paradigma master/worker donde el procesamiento se descompone en tareas irregulares que atentan contra el balance de carga entre los procesadores. Por esta razón se han analizado tres estrategias de distribución de trabajo calculando en cada caso el desbalance de carga y el rendimiento obtenido, comparando los resultados para determinar la que tiene mejor comportamiento, y finalmente estudiar la escalabilidad para esa solución.
La solución paralela pura (sin tener en cuenta la distribución del trabajo) para el tipo de problemas donde Tp>>Tc, en particular el de N-Reinas requiere mínima comunicación entre máquinas, lo que hace esencial la elección de la distribución de datos entre los procesadores, para alcanzar un speedup cercano al óptimo (es decir un buen rendimiento).
Una de las áreas de mayor interés y crecimiento en los últimos años dentro del procesamiento paralelo es la del tratamiento de grandes volúmenes de datos, tales como las secuencias de ADN. El tipo de procesamiento extensivo de comparación para analizar patrones genéticos requiere un esfuerzo importante en el desarrollo de algoritmos paralelos eficientes.
El alineamiento de secuencias de ADN representa una de las operaciones más importantes dentro de la bioinformática. En 1981, Smith y Waterman desarrollaron un método para el alineamiento local de secuencias. Sin embargo, en la práctica se emplean diversas heurísticas en su lugar, debido a los requerimientos de procesamiento y de memoria del algoritmo Smith-Waterman. Si bien son más rápidas, las heurísticas no garantizan que el alineamiento óptimo sea encontrado. Es por ello que resulta interesante estudiar cómo aplicar la potencia de cómputo de plataformas paralelas actuales de manera de acelerar el proceso de alinear secuencias sin perder precisión en los resultados.
Los niveles insostenibles de generación de calor y consumo de energía que se presentan al escalar al máximo la velocidad de los procesadores mononúcleos motivaron el surgimiento de los procesadores de múltiples núcleos (multicore). Un procesador multicore integra dos o más núcleos computacionales dentro de un único chip y, si bien estos son más simples y menos veloces, al combinarlos permiten mejorar el rendimiento global del procesador y al mismo tiempo hacerlo más eficiente energéticamente. Al incorporar este tipo de procesadores a los clusters convencionales, se da origen a una arquitectura conocida como cluster de multicores, que combina memoria compartida y distribuida, y donde la comunicación entre las diferentes unidades de procesamiento resulta ser heterogénea.
En este trabajo se presenta un algoritmo paralelo distribuido para el alineamiento de secuencias de ADN basado en el método Smith-Waterman para ser ejecutado sobre las arquitecturas de cluster actuales. Además, se realiza un análisis de rendimiento del mismo. Por último, se presentan las conclusiones y las posibles líneas de trabajo futuro.
Este documento describe una investigación realizada como trabajo final para la Especialización en Computo de Altas Prestaciones dictada en la Facultad de Informática de la Universidad Nacional de La Plata. El tema de investigación consiste en métodos y herramientas para el análisis del comportamiento de aplicaciones de alto rendimiento. Este trabajo contribuye con un resumen de la teoría de análisis de rendimiento más una descripción de las herramientas de soporte disponibles en el momento. Se propone también un proceso para analizar el rendimiento, ejemplificando su aplicación a un conjunto de núcleos de cómputo no triviales. Luego de la introducción de terminología y bases teóricas del análisis cuantitativo de rendimiento, se detalla la experiencia de utilizar herramientas para conocer donde se deberían localizar los esfuerzos de optimización. Este trabajo resume la experiencia que debe atravesar cualquier investigador en busca de las diferentes alternativas para el análisis de rendimiento; incluyendo la selección de herramientas de soporte y la definición de un procedimiento sistemático de optimización.
En este trabajo se realiza un análisis comparativo de las técnicas de programación paralela, en el que puede observarse cómo la evolución en el diseño de la solución a un mismo problema permite maximizar la performance de algoritmos paralelos en arquitecturas clúster de multicore.
Este análisis se realiza utilizando un caso de estudio ampliamente estudiado en el área como lo es la multiplicación de matrices. Para ello, se implementaron diferentes soluciones para resolver el problema, partiendo de soluciones de alto nivel y bajo acoplamiento con la arquitectura, hasta llegar a soluciones de bajo nivel, dependientes de la arquitectura de prueba subyacente y que aprovechan las características de la misma, como por ejemplo la jerarquía de memoria.
Las soluciones implementadas son una solución utilizando pasaje de mensajes, y tres soluciones híbridas teniendo en cuenta diferentes librerías de programación paralela (OpenMPI, Pthreads y OpenMP), y diferentes esquemas de descomposición de los datos.
Asimismo, las pruebas de los algoritmos implementados se analizan desde distintos puntos de vista. Por un lado, escalando el tamaño del problema a resolver y por otro, escalando la cantidad de núcleos de procesamiento utilizados.
(English) Demo Content
El presente documento corresponde con el trabajo final de la Especialización en Cómputo de Altas Prestaciones y Tecnología Grid de la Facultad de Informática, de la Universidad Nacional de La Plata. El trabajo aborda la problemática de procesamiento paralelo de flujos de datos (data streams), con el ingrediente de basarse los mismos en marcos formales de medición y evaluación para luego regir la organización de sus datos en base a ellos. El trabajo aborda inicialmente el estado del arte en términos de sistemas de gestión de flujos de datos, para luego discutir el marco formal de medición y evaluación C-INCAMI, como referencia para la estructuración del contenido del flujo. Seguido, se discute globalmente el Enfoque Integrado de Procesamiento de Flujos de Datos Centrado (EIPFD) en Metadatos de Mediciones, el que se asocia a mi tesis para Doctor en Ciencias Informáticas de la misma facultad y que a la fecha, se encuentra en revisión y edición final de escritura. Dicho enfoque, permite estudiar el impacto de paralelizar el procesamiento de la recepción de los flujos y la organización en línea dentro de un buffer centralizado, controlando el acceso concurrente y simultáneo en entornos de arquitecturas con memoria compartida. Luego, se define un formato de intercambio de mediciones basado en C-INCAMI, junto con el procesador que permite efectuar la serialización/deserialización en línea a los efectos de favorecer el procesamiento paralelo. Hecho ello, se plantea la estructura de organización de las mediciones y cómo guían los metadatos, al proceso de clasificación de mediciones en un buffer central. Se plantea un caso de aplicación para EIPFD sobre el que se basará la simulación de laboratorio. Esta simulación, persigue validar inicialmente los tiempos de procesamiento y analizar estadísticamente los resultados de la misma, para poder identificar cuellos de botellas y situaciones de mejoras en términos de procesamiento.