Effective Resource Management for Master-Worker Applications in Opportunistic Environments

Author

Heymann Pignolo, Elisa

Director

Senar Rosell, Miquel Àngel

Date of defense

2002-11-05

ISBN

8469997874

Legal Deposit

B-42372-2002



Department/Institute

Universitat Autònoma de Barcelona. Departament d'Informàtica

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.

Keywords

Master-worker applications; Oportunistic environments; Scheduling

Subjects

68 - Industries, crafts and trades for finished or assembled articles

Knowledge Area

Tecnologies

Documents

ehp1de2.pdf

886.7Kb

ehp2de2.pdf

960.5Kb

 

Rights

ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs.

This item appears in the following Collection(s)