Planificación de DAGS en entornos oportunísticos

Abstract

Las aplicaciones tipo workflow se caracterizan por tener un elevado tiempo de cómputo y una elevada transferencia de datos. Como consecuencia, el tiempo de ejecución o makespan de un workflow es elevado. Con el propósito de reducir el makespan del workflow, las tareas se ejecutan en diferentes máquinas interconectadas a través de una red. Asignar correctamente las tareas del DAG a las máquinas disponibles del entorno de ejecución mejora el makespan. El encargado de realizar la asignación de las tareas del workflow a las máquinas es el planificador. El problema de un planificador estático es que no tiene en cuenta los cambios ocurridos en el entorno de ejecución durante la ejecución del DAG. La solución a este problema ha sido el desarrollo de un nuevo planificador dinámico. El planificador dinámico mejora el makespan del DAG debido a que considera los cambios ocurridos en el entorno de ejecución durante la ejecución del workflow, pero como contrapartida, genera overhead producido a consecuencia de reaccionar ante los cambios detectados. El objetivo de este trabajo es proporcionar estrategias que reducen el overhead del planificador dinámico, sin afectar al makespan del DAG. Para reducir el overhead, el algoritmo reacciona ante los cambios detectados durante la ejecución del DAG únicamente si anticipa que su makespan mejora. La política dinámica desarrollada ha sido evaluada a través de ejecuciones simuladas y ejecuciones realizadas en un entorno oportunístico real. En la experimentación simulada se ha mejorado el makespan entre 5% y 30%, y en la experimentación real la mejora del makespan ha sido entre 5% y 15%. En lo que respecta al overhead, éste se ha reducido como mínimo un 20% respecto a otras políticas de planificación dinámicas.

Workflow applications exhibit both high computation times and data transfer rates. For this reason, the completion time or makespan of the workflow is high. To reduce completion time, tasks of a workflow ought to run on different machines interconnected by a network. Efficient assignment of tasks to machines within the runtime environment is an important aspect to achieve a good makespan. The manager making these assignment is the scheduler.

The main problem of a static scheduler is that it ignores changes that occur in the execution environment during workflow execution. To solve this problem, we developed a new dynamic scheduler.

Taking into account the changes that occur to the execution environment during the execution of the DAG improves the makespan, but generates overhead as a result of reacting to the detected changes. The objective of this thesis was to reduce the overhead incurred by excessive self-adaptations, without affecting the makespan. To reduce overhead, the proposed dynamic algorithm self-adapts only when an improvement in makespan is expected.

The proposed policies have been evaluated by simulation and executed in a real environment. In simulated experiments we achieved a makespan improvement between 5% and 30%, while in real experiments the makespan improvement was between 5% and 15%. Regarding the overhead, our strategy incurred in at least 20% less overhead than other dynamic scheduling policies.