Título: Um Modelo Baseado Em Autômatos Celulares Síncronos Para O Escalonamento De Tarefas Em Multiprocessadores
Autores: Carneiro, Murillo G.; Oliveira, Gina M. B.
Resumo: O Problema de Escalonamento Estático de Tarefas em multiprocessadores (PEET) é NP-Completo e as abordagens propostas para resolvê-lo normalmente utilizam heurísticas ou meta-heurísticas. Entretanto, muitas delas não têm a habilidade de extrair conhecimento do processo de escalonamento de uma aplicação paralela e reusá-lo em outras instâncias. Trabalhos anteriores têm mostrado o uso promissor de Autômatos Celulares (AC) para extração e reuso de conhecimento no PEET, mas o forte paralelismo intrínseco nestas estruturas não tem sido explorado com sucesso. Ao contrário, resultados satisfatórios de escalonamento de tarefas (ótimos ou sub-ótimos) foram obtidos anteriormente com o uso de ACs com modo de atualização de células sequencial, que os tornam estruturas essencialmente sequenciais e não propícias à implementação em hardware paralelo. Este artigo apresenta um novo modelo de escalonador baseado em AC com modo de atualização síncrono. Grafos de programa encontrados nas pesquisas relacionadas foram utilizados para avaliar a abordagem. Os experimentos mostram que o modelo é capaz de resolver grafos de programas paralelos que os modelos síncronos da literatura não conseguiram e apresenta resultados superiores aos modelos sequenciais, em termos de convergência para o escalonamento ótimo.
Palavras-chave: Escalonador baseado em AC; atualização síncrona; escalonamento estático de tarefas; sistemas multiprocessadores
Páginas: 8
Código DOI: 10.21528/CBIC2011-40.4
Artigo em pdf: st_40.4.pdf
Arquivo BibTex: st_40.4.bib