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

AUTOR(ES)
DATA DE PUBLICAÇÃO

2007

RESUMO

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 re-escalonamento 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.

ASSUNTO(S)

clusters de workstations grafos de tarefas algoritmos de escalonamento sistemas de computacao ambientes distribuídos

ACESSO AO ARTIGO

Documentos Relacionados