Abordagem adaptativa de monitoramento para escalonamento de grafos dirigidos acíclicos em ambientes distribuídos

Abstract

O escalonamento estático de um programa, representado por um grafo dirigido acíclico de tarefas, em um ambiente multiprocessado, tem o objetivo de minimizar o tempo de conclusão do programa. Apesar das pesquisas nesta área terem obtido heurísticas eficientes, encontrar um escalonamento ótimo é um problema NP - Completo. Clusters de workstations podem ser utilizados no processamento paralelo de programas e devido à complexidade de integração entre os programas, o monitoramento e a simulação são efetuados através de ferramentas que gerenciam o cluster e a execução dos programas paralelos. Dentre as ferramentas analisadas, o PM2P, será utilizado como base de estudo devido ao conhecimento da ferramenta. O objetivo deste trabalho é o desenvolvimento e implementação na ferramenta citada um monitoramento periódico para verificar a disponibilidade das máquinas do cluster e re-escalonar os programas se houver necessidade ou ganho de desempenho. Para testar este monitoramento foram implementados, devido à carência de algoritmos na ferramenta, três algoritmos estáticos voltados para o escalonamento de tarefas que possam ser representados por um GDA (Grafo Dirigido Acíclico). Estes algoritmos funcionam de forma similar, gerando uma lista em ordem topológica das tarefas e àquelas pertencentes ao mesmo nível, portanto, concorrentes entre si, são ordenadas pelo maior ou menor tempo de execução. As tarefas são distribuídas de acordo com a disponibilidade das máquinas no cluster e o objetivo do algoritmo de escalonamento é manter o makespan gerado igual ao tempo do caminho crítico do grafo. Os resultados dos testes, as conclusões sobre o monitoramento e re-escalonamento serão demonstradas através de tabelas e mapas de Gantt para facilitar a visualização e o entendimento. Foram testados conjuntos de tarefas distintas que representam aplicações exemplo. Foi observado que aplicações rápidas, que finalizam sua execução concomitante ou logo após o tempo gasto para verificar a disponibilidade das máquinas no cluster, o monitoramento e o reescalonamento não são necessários e neste caso é recomendável o reinício da aplicação. Ao contrário, aplicações que demandam mais tempo para sua execução, o monitoramento e o re-início de algum programa no caso de indisponibilidade de uma máquina são importantes, uma vez que a aplicação continua sua execução com a nova arquitetura de máquinas, a partir do ponto de detecção da falha. Apesar do custo adicional para execução da atividade, conclui-se que há vantagens em se ter um cluster monitorado quando da execução dos programas paralelos utilizando a biblioteca MPI. ______________________________________________________________________________________________________ ABSTRACT

Static scheduling of a program represented by a directed acyclic graph task on a multiprocessor environment to minimize the program completion time is the goal. It is a wellknown problem of concurrent processing. Although the researches in this area already have reached heuristic efficient to find an optimal scheduling is a NP-Complete problem. The Cluster of Workstations can be used to the parallel processing of programs and due to the program interaction complexity, the monitoring and the simulation are made through frameworks that manage the cluster and the parallel program execution. Among the frameworks analyzed, the framework PM2P, will be used as the base study. The objective of this work is the development and implements a periodic monitoring to verify the machines availability at the cluster and rescheduling the programs whether is necessary or to improve the performance. It has been implemented, to test this periodic monitoring due to the framework algorithms lack new three static algorithms toward the scheduling of programs of tasks that could be represented by DAG (Directed Acyclic Graph). These three algorithms working in a similar way, each one create a topological order list of the tasks and they scheduling the tasks that belongs at the same level of the graph and ordering these tasks by the bigger or smaller execution time criteria. The tasks are sorted and distributed through the cluster machines in accordance with the availability of them. The scheduling goal is getting the graph makespan like the critical path time. The tests results, monitoring conclusions and the scheduling algorithms proposals will be demonstrated with tables and Gantt charts to a best exhibition and comprehension. The tests were over sets of different tasks that representing some real application. It was observed that applications with small execution time finish their at the same time or as soon as the framework check the cluster machines availability. In these cases are not necessary to rescheduling the applications and is recommended restart them. By the other hand, applications with big execution time, the programs monitoring and the restart of some program is important if any machine become unavailability. So, the application continues this execution at the restart point using the other workstations. Nevertheless the additional monitoring overhead, the conclusions show that exist advantages of monitoring the cluster when are executing a parallel programs using the MPI library with a big execution time.