Automatic dynamic tuning of parallel/distributed applications on computational grids

Las aplicaciones paralelas presentan diversos problemas de prestaciones al ser cambiadas para ejecutar en entornos Grid. Las características del sistema pueden ser diferentes en cada ejecución y en algunos casos dentro de una misma ejecución. Los recursos remotos comparten enlaces de red y, los procesos de la aplicación comparten las maquinas con otros procesos. En esos escenarios se propone el uso de la técnica de sintonización dinámica de prestaciones para ayudar las aplicaciones a adaptarse a los cambios en las características del sistema con la intención de resolver los problemas de prestaciones. Esta tesis analiza el problema de la ejecución de aplicaciones paralelas en entornos Grid, herramientas para el análisis de prestaciones disponibles y modelos adecuados para la sintonización dinámica de aplicaciones paralelas en este tipo de entorno. De este análisis, se propone una arquitectura para sintonización dinámica de aplicaciones paralelas en entornos Grid llamada GMATE. Esta arquitectura incluye diversas contribuciones. En el caso donde un gestor de recursos de alto nivel decide el mapeo de procesos de la aplicación, se proponen dos aproximaciones para el seguimiento de procesos que habilita GMATE a localizar donde las capas de software del Grid ha mapeado los procesos de la aplicación. Una aproximación consiste en la integración de GMATE a las capas de software del Grid. La otra integra los componentes requeridos de GMATE dentro de los binarios de la aplicación. El primer enfoque requiere derechos de administración en cuanto que el segundo incrementa el binario del la aplicación, lo que torna más lento el arranque de la misma. Para respetar las políticas de las organizaciones propietarias de los recursos, todas las comunicaciones usan el mismo certificado de seguridad de la aplicación. Esas comunicaciones son hechas con base en las capas del Grid. Esta aproximación habilita la arquitectura a monitorizar y sintonizar los procesos de la aplicación de forma dinámica a las restricciones de cortafuegos de las organizaciones y políticas de uso de la red en las mismas. Para bajar la necesidad de comunicaciones en la arquitectura GMATE, se encapsula parte de la lógica requerida para colectar las medidas y para cambiar los parámetros de la aplicación en componentes encuestados que ejecutan dentro de espacio de memoria del proceso de la aplicación. Para colectar medidas, se ha creado componentes sensores que disminuyen la necesidad de comunicaciones llevando el procesamiento de eventos para dentro del proceso de la aplicación. Diferente de la instrumentación tradicional, los sensores pueden retrasar la transmisión de los eventos y ejecutar operaciones básicas como sumas, temporizadores, promedios o generación de eventos basados en umbrales. Esas capacidades reducen los requerimientos de comunicaciones que son útiles en situaciones de bajo ancho de banda. Se propone también el encapsulamiento de la lógica de cambio en las aplicaciones en componentes actuadores. Los actuadores son instalados en el flujo de ejecución de la aplicación y posibilita la sincronización y baja intrusión en cambio de variables y ejecución de funciones para modificar la aplicación. La arquitectura propuesta posibilita la comunicación entre sensores y actuadores lo cual habilita la sintonizaciones sencillas sin necesidad de comunicaciones. Para aplicar la sintonización dinámica en entornos Grid, necesitamos de un modelo de prestaciones que pueda ser usado en entornos con heterogeneidad de red y procesadores para guiar el proceso. Se propone un modelo de prestaciones basado en una heurística para lograr usar el máximo número de esclavos y el mejor tamaño de grano en una ejecución Maestro-Esclavo en sistemas Grid. Se considera que una clase de aplicaciones pueden ser desarrolladas con la capacidad de cambiar el tamaño de grano en tiempo de ejecución y que esa acción cambia la relación entre cómputo y comunicación. En el escenario donde usuarios reciben un conjunto de recursos para una ejecución paralela, esos recursos pueden configurar un sistema de múltiples clústeres. La heurística del modelo presentado permite guiar la selección de los recursos para disminuir el tiempo total de ejecución de la aplicación. Se intenta buscar el punto donde el maestro usa el máximo número de esclavos posible asignando prioridad a aquellos más rápidos. Se presentan los resultados de sintonización del tamaño de grano y número de esclavos en ejecuciones Maestro-Esclavo en entornos Grid donde se logra bajar el tiempo total de ejecución de la aplicación y aumentando la eficiencia de uso de los recursos. Se presentan las implementaciones de las aplicaciones multiplicación de matrices, N-Body y cargas sintéticas las cuales tienen diferentes grados en la relación entre cómputo y comunicación en escenarios de cambio del tamaño de grano.When moving to Grid Computing, parallel applications face several performance problems. The system characteristics are different in each execution and sometimes within the same execution. Remote resources share network links and in some cases, the processes share machines using per-core allocation. In such scenarios we propose to use automatic performance tuning techniques to help an application adapt itself thus a system changes in order to overcome performance bottlenecks. This thesis analyzes such problems of parallel application execution in Computational Grids, available tools for performance analysis and models to suit automatic dynamic tuning in such environments. From such an analysis, we propose system architecture for automatic dynamic tuning of parallel applications on computational Grids named GMATE. Its architecture includes several contributions. In cases where a Grid meta-scheduler decides application mapping, we propose two process tracking approaches that enable GMATE to locate where a Grid middleware maps application processes. One approach consists of the integration of GMATE components as Grid middleware. The other involves the need to embed a GMATE component inside application binaries. The first requires site administration privileges while the other increases the application binary which slows down application startup. To obey organizational policies, all communications use the same application security certificates for authentication. The same communications are performed using Grid middleware API. That approach enables the monitoring and tuning process to adapt dynamically to organizational firewall restrictions and network usage policies. To lower the communication needs of GMATE, we encapsulate part of the logic required to collect measurements and change application parameters in components that run inside the processing space. For measurements collection, we create sensor components that reduce the communication needs by event processing inside the process space. Different from traditional instrumentation, sensors can postpone the event transmission and perform basic operations such as summarizations, timers, averages or threshold based event generation. That reduces the communication requirements in cases where network bandwidth is expensive. We also encapsulate the modifications used to tune the application in components called actuators. Actuators may be installed at some point in the program flow execution and provide synchronization and low overhead control of application variables and function executions. As sensors and actuators can communicate with each other, we can perform simple tuning within process executions without the need for communication. As the dynamic tuning is performance model-centric, we need a performance model that can be used on heterogeneous processors and network such Grid Systems. We propose a heuristic performance model to find the maximum number of workers and best grain size of a Master-Worker execution in such systems. We assume that some classes of application may be built capable of changing grain size at runtime and that change action can modify an application's compute-communication ratio. When users request a set of resources for a parallel execution, they may receive a multi-cluster configuration. The heuristic model allows for shrinking the set of resources without decreasing the application execution time. The idea is to reach the maximum number of workers the master can use, giving high priority to the faster ones. We presented the results of the dynamic tuning of grain size and the number of workers in Master-Worker applications on Grid systems, lowering the total application execution time while raising system efficiency. We used the implementation of Matrix-Multiplication, N-Body and synthetic workloads to try out different compute-communication ratio changes in different grain size selections