Effective Resource Management for Master-Worker Applications in Opportunistic Environments

Abstract

Este trabajo se basa en el uso de entornos oportunísticos, los cuales se caracterizan por aprovechar el tiempo en que las máquinas permanecen ociosas para ejecutar procesos de usuarios. Una parte fundamental de estos entornos consiste en gestionar procesos concurrentes que constituyen una aplicación paralela. En sistemas oportunísticos el objetivo del gestor de recursos es doble: por una lado ha de proveer tiempos de ejecución razonables (los usuarios desean obtener sus procesos acabados cuanto antes), y por el otro ha de proveer buena eficiencia, esto es, buen uso de los recursos, lo cual constituye el objetivo fundamental de un sistema que desea soportar grandes cantidades de cómputo durante largos períodos de tiempo.<br/>El desarrollo de un gestor de recursos adecuado para aplicaciones paralelas que se ejecutan en entornos oportunísticos incluye varios aspectos. En particular, este trabajo aborda tres de ellos:<br/>- Determinar el número de máquinas, pertenecientes a un entorno oportunístico, necesarias para ejecutar una aplicación, de manera tal que se obtenga buena eficiencia y buen tiempo de ejecución.<br/>- Planificar las tareas a las máquinas asignadas.<br/>- Reducir los efectos negativos producidos sobre una aplicación, cuando una máquina es reclamada por su dueño, lo que implica que el proceso que ejecuta allí debe dejar dicha máquina.<br/>En este trabajo se han considerado aplicaciones de tipo master-worker. El master envía tareas a los workers y recoge los resultados. Este proceso se repite varios ciclos, hasta que se produce una condición de finalización.<br/>Para asignar las tareas de la aplicación master-worker a las máquinas disponibles se ha propuesto una política de planificación dinámica denominada Random & Average. Esta política se evaluó por simulación, y los resultados muestran que su comportamiento es parecido al de políticas que necesitan información a-priori sobre el tiempo de ejecución de las tareas. También se dedujo la existencia del Intervalo Ideal, que corresponde al intervalo entre los números de máquinas mínimo y máximo para ejecutar la aplicación de manera tal que se obtenga una buena relación entre el tiempo de ejecución y la eficiencia.<br/>Luego se propuso un algoritmo para ajustar dinámicamente el número de máquinas, de manera tal que cualquier aplicación master-worker se ejecute con un número de máquinas perteneciente al intervalo ideal. Esta estrategia se implemento tanto en entornos homogéneos como heterogéneos, utilizando una aplicación encargada de obtener el esqueleto de imágenes.<br/>En un entorno oportunístico las máquinas pueden participar o dejar de participar en la ejecución de una aplicación, si son cedidas o reclamadas por sus dueños. Cuando una máquina es reclamada, el proceso que se ejecuta en dicha máquina debe ser detenido y debe dejar esa máquina inmediatamente. Si dicho proceso pertenece a una aplicación paralela, el rendimiento de toda esa aplicación se verá afectado negativamente. Dicho impacto se evaluó, y para disminuirlo se propusieron diferentes estrategias basados en utilizar máquinas extra y en duplicación de tareas. Estas estrategias se estudiaron primero por simulación y luego fueron implementadas.

This work focuses on the use of opportunistic environments, which are characterized by harnessing idle times of machines for executing user jobs. Management of the concurrent jobs constituting a parallel application is an integral part of such non-dedicated systems. In non-dedicated opportunistic environments, the resource manager's goal is to provide both a reasonable execution time (as users are interested in having their job finished as soon as possible), and good efficiency, i.e., good resource usage, which is the main goal of the system in order to obtain high throughput.<br/>The development of effective resource management for parallel applications running on opportunistic systems involves a great number of issues. In particular, this work deals with three of them:<br/>- Determining and allocating the number of machines, from the pool of machines belonging to the opportunistic system, needed for executing an application obtaining both a good execution time and a good efficiency. <br/>- Scheduling application tasks to the assigned computational resources.<br/>- Reducing the negative effects produced on an application when a machine belonging to a non-dedicated environment is reclaimed by its owner, and should therefore be released by the task running on it. <br/>Throughout this work master-worker applications have been considered. In these applications, there is a master that sends tasks to workers and collects the results. This process is repeated over a number of cycles until an end condition is reached. <br/>In order to assign tasks belonging to a master-worker application to machines belonging to an opportunistic environment, we proposed a dynamic scheduling policy called Random & Average. This policy was first evaluated by simulation, and results showed that it exhibits a similar behavior with respect to other policies requiring information in advance about the execution time of the tasks. We also derived the existence of the ideal interval, which corresponds to the interval comprised between the minimum and maximum number of machines for executing the application that obtain a good trade-off between execution time and efficiency. Then we proposed an algorithm for dynamically adjusting the number of machines, for executing any master-worker application, to a number of machines belonging to the ideal interval. This strategy was implemented and evaluated on both homogeneous and heterogeneous environments, with a master-worker thinning application.<br/>In an opportunistic environment machines can join and leave the computation as they are released or reclaimed by their owners. When a machine is reclaimed, the job running on that machine must be stopped and vacated. If this job belongs to a parallel application, the whole performance will be negatively affected. We evaluate this impact, and then, in order to alleviate it, propose strategies based on using extra machines and task replication. These strategies were first evaluated by simulation and then implemented and tested in a real environment.