Estimated and Observed Performance of Heuristic Algorithrns for Task Scheduling on Heterogeneous Processors - Kitajima, J. P. W.; Porto, S. C. S. (Anais do International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD); 1997: Anais do IX Simpósio Brasileiro de Arquitetura de Computadores e Processamento de Alto Desempenho, 1997)
Aplicações paralelas com um comportamento regular e bem conhecido, onde as estimativas dos tempos de execução de tarefas são bastante razoáveis, adequam-se bem ao escalonamento estático (em oposição ao escalonamento dinâmico, realizado durante a execução da aplicação). Este é o caso de várias aplicações científicas paralelas. O escalonamento de tarefas em um ambiente heterogêneo, onde os processadores apresentam capacidades diferentes de processamento, é ainda mais complexo do que em um ambiente homogêneo. Escalonamento estático de tarefas baseia-se em dados estimados sobre a aplicação paralela e a arquitetura do sistema e tem recebido freqüentemente um enfoque heurístico. Por isso, uma avaliação de desempenho realística de um algoritmo de escalonamento de tarefas poderá apenas ser completamente realizado se resultados práticos também forem considerados. Neste sentido, o presente trabalho analisa a qualidade de dois algoritmos de escalonamento, um heurístico de construção e outro baseado na metaheurística de busca tabu. Esta análise compara resultados determinísticos com resultados observados do tempo de execução de diversas aplicações paralelas sintéticas em máquinas paralelas reais de acordo com o escalonamento previámente obtido.