A two stages cluster-based strategy for scheduling tasks on heterogeneous processors

O presente trabalho aborda o problema do escalonamento de tarefas de uma aplicação paralela em um conjunto de processadores heterogêneos de um sistema distribuído. Devido à sua grande importância, o escalonamento de tarefas é objeto de um grande número de estudos, e diversas técnicas já foram apresentadas para a solução deste problema que é NP-completo em sua forma geral. Algoritmos do tipo list scheduling que levam em consideração a heterogeneidade do ambiente de execução podem parecer, a princípio, mais propícios para o escalonamento de tarefas em ambientes heterogêneos com grades computacionais. Entretanto, sabe-se que heurísticas de aglomeração produzem escalonamentos eficientes para ambientes heterogêneos, em particular quando os custos de comunicação são mais elevados que a média dos custos de computação. O objetivo deste trabalho é estudar a aplicabilidade de algoritmos baseados em metodologia de aglomeração com replicação já proposta, para o escalonamento de tarefas em grades computacionais. Este trabalho apresenta uma estratégia de escalonamento de aplicações em um número limitado de processadores heterogêneos em dois estados, chamada de Clusterização para Processadores Heterogêneos (CPH). No primeiro estágio, as coleções de tarefas são construídas com o objetivo de amenizar o efeito dos custos de comunicação na execução da aplicação. O segundo estágio, o Algoritmo do Mapeamento de Coleções (AMC), proposto neste trabalho de Dissertação, implementa uma política de mapeamento de coleções nos processadores heterogêneos, de forma a minimizar o makespan da aplicação. O algoritmo de mapeamento proposto é do tipo list scheduling e explora tantas características das coleções quanto do sistema alvo. Para validação de sua aplicabilidade, os resultados produzidos por CPH foram comparados aos resultados produzidos por dois outros algoritmos amplamente estudados na literatura, específicos para ambientes heterogêneos e número limitado de processadores. A análise dos resultados mostra a vantagem em utilizar tal abordagem, principalmente quando os custos de comunicação são dominantes