Abordagens baseadas em autômatos celulares síncronos para o escalonamento estático de tarefas em multiprocessadores

AUTOR(ES)
FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

28/02/2012

RESUMO

O problema de escalonamento estático de tarefas computacionais (PEET) em uma arquitetura multiprocessada consiste em alocar tarefas que compõem um programa paralelo entre os nós de uma arquitetura com múltiplos processadores. Uma solução ótima de uma instância do PEET é tal que as restrições de precedência entre as tarefas sejam atendidas e o tempo total de execução - ou makespan - é minimizado. O problema é NP-Completo, mesmo limitado ao caso mais simples: um sistema paralelo com apenas dois processadores. Diante disso, métodos heurísticos, tais como HLFET (Highest Level First with Estimated Time) e MCP (Modied Critical Path), e meta-heurísticas, tais como algoritmos genéticos (AG) e simulated annealing (SA) têm sido frequentemente empregados na tentativa de encontrar boas soluções para o problema. Contudo, eles não apresentam qualquer habilidade para extrair conhecimento do processo de escalonamento de uma aplicação paralela e precisam reiniciar o processo a cada nova instância. Neste contexto, o escalonamento baseado em autômatos celulares (ACs) tem se mostrado promissor, uma vez que tem por objetivo a extração do conhecimento sobre o processo de escalonamento de um programa paralelo e sua consequente reutilização em novas instâncias. Contudo, algumas características desejáveis ainda não foram exploradas com sucesso pelos modelos existentes na literatura: (i) paralelismo massivo intrínseco aos ACs, (ii) uso de um número arbitrário de processadores, (iii) reuso eciente do conhecimento extraído sobre outras aplicações paralelas, entre outras. Desse modo, novas abordagens baseadas em ACs para o PEET foram investigadas. Essas abordagens foram avaliadas sistematicamente em relação a outras abordagens anteriores de escalonamento baseadas em AC e também a métodos heurísticos e meta-heurísticos. Dentre as contribuições da pesquisa estão três novos modelos de escalonadores (EACS, EACS-H e EACS-HV) relacionados à extração, avaliação e reuso do conhecimento; uma nova estratégia para inicializar os reticulados dos ACs baseada em uma heurística determin ística; uma nova estratégia para análise do comportamento dinâmico das regras do AC (penalização da regra) em tempo de execução e dois novos modelos de vizinhança de estrutura simples, porém com capacidade de extração de informações da aplicação paralela (Vpl-c1 e Vpl-c2) e uso de um número arbitrário de processadores. Como resultado dos experimentos, foi possível garantir o emprego bem sucedido do paralelismo nos ACs, além de um bom desempenho na fase de aprendizagem, onde os valores encontrados pelas abordagens estiveram próximos daqueles tomados por referência e foram superiores a heurísticas e algumas meta-heurísticas. Ainda, testes estatísticos foram realizados e comprovaram a superioridade das novas abordagens em relação a outros trabalhos baseados em AC. O reuso do conhecimento também foi avaliado e se mostrou competitivo nas novas abordagens. Em suma, as abordagens desenvolvidas mostram que o escalonamento baseado em AC possui grande potencial para o escalonamento eciente de tarefas em sistemas multiprocessados. Logo, este potencial pode ser melhor explorado quando os modelos propostos trabalham diretamente sobre arquiteturas de hardware paralelo.

ASSUNTO(S)

autômato celular escalonamento estático de tarefas algoritmos evolutivos heurísticas meta-heurísticas ciencia da computacao inteligência artificial cellular automata task static scheduling evolutionary algorithms heuristics metaheuristics

Documentos Relacionados