Novas abordagens na evoluÃÃo de autÃmatos celulares aplicados ao escalonamento de tarefas em multiprocessadores

AUTOR(ES)

Paulo MoisÃs Vidica

DATA DE PUBLICAÇÃO

2007

RESUMO

O escalonamento de tarefas em uma arquitetura multiprocessadora à ainda um grande desafio na Ãrea de computaÃÃo paralela. Neste trabalho, estudamos um algoritmo de escalonamento baseado em autÃmatos celulares (ACs) que tem o objetivo de alocar tarefas de um programa paralelo em um sistema com dois processadores. O algoritmo de escalonamento apresenta duas fases: a fase de aprendizagem e a fase de operaÃÃo. O propÃsito da fase de aprendizagem à descobrir regras de ACs aptas ao escalonamento das tarefas. A busca por estas regras à conduzida com a utilizaÃÃo de um algoritmo genÃtico (AG). Na fase de operaÃÃo, as regras descobertas na fase anterior sÃo aplicadas em novas instÃncias de programas paralelos. à esperado que, para qualquer alocaÃÃo inicial das tarefas, o AC seja apto a encontrar uma alocaÃÃo onde o tempo total de execuÃÃo T seja minimizado, ou muito prÃximo disso. Estudamos inicialmente os modelos de ACs e AGs propostos e publicados atà entÃo para a arquitetura do escalonador de tarefas. ApÃs o entendimento e reproduÃÃo de alguns resultados publicados, a meta do trabalho passou a ser investigar a capacidade de generalizaÃÃo das regras de transiÃÃo de ACs. Ou seja, investigar se as regras encontradas para um programa paralelo especÃfico poderiam ser aplicadas, com sucesso, em outros programas. A principal conclusÃo dessa investigaÃÃo à que ainda existe muito espaÃo para a melhoria dessa capacidade. Visando melhorÃ-la, apresentamos duas novas abordagens para a fase de aprendizagem do algoritmo de escalonamento baseado em ACs: a evoluÃÃo conjunta e um ambiente coevolutivo. Resultados obtidos atravÃs destas novas abordagens mostram que, com o seu uso, as regras de ACs evoluÃdas apresentam uma melhor capacidade de generalizaÃÃo.

ASSUNTO(S)

escalonamento de tarefas em uma arquitetura multiprocessadora scheduling tasks in multiprocessor architectures autÃmatos celulares cellular automata ciencia da computacao algoritmos genÃticos genetic algorithms inteligÃncia artificial

Documentos Relacionados

• DinÃmica e evoluÃÃo de autÃmatos celulares unidimensionais.
• Novas abordagens na evolução de autômatos celulares aplicados ao escalonamento de tarefas em multiprocessadores
• SimulaÃÃo de fluidos imiscÃveis em meios porosos atravÃs de autÃmatos celulares de gÃs na rede
• Abordagens baseadas em autômatos celulares síncronos para o escalonamento estático de tarefas em multiprocessadores
• A revisÃo judicial dos contratos e a evoluÃÃo do direito contratual