Dissertação
Novas abordagens na evolução de autômatos celulares aplicados ao escalonamento de tarefas em multiprocessadores
Registro en:
VIDICA, Paulo Moisés. Novas abordagens na evolução de autômatos celulares aplicados ao escalonamento de tarefas em multiprocessadores. 2007. 237 f. Dissertação (Mestrado em Ciências Exatas e da Terra) - Universidade Federal de Uberlândia, Uberlândia, 2007.
Autor
Vidica, Paulo Moisés
Institución
Resumen
Scheduling tasks in multiprocessor architectures still is a challenge in parallel computing field.
In this work, we studied a scheduling algorithm based on cellular automata (CA) with the goal of
allocate parallel program tasks in a system with two processors. The scheduling algorithm has two
phases: a learning phase and an operating phase. The purpose of the learning phase is to discover
CA rules for scheduling. A genetic algorithm (GA) is used for search these rules. In the operating
phase, the rules discovered in the previous phase are applied in new instances of parallel programs.
It is expected that for any initial allocation of the tasks, CA will be able to find an allocation of
tasks where the total execution time T is minimized (or close to it). We first studied CA and GA
models proposed and published for the task scheduler architecture. After the understanding of these
models and the reproduction of some published results, our goal turned to study the generalization
ability of the CA transition rules. We investigated if the rules found for a specific parallel program
can be applied, successfully, in other programs. Our main conclusion about this investigation is that
there is a lot of space for improving this ability. Aiming to improve this generalization ability, we
present two new approaches for the learning phase of the scheduling algorithm based on CA: the joint
evolution and a coevolutionary environment. Results obtained through these new approaches show
that, applying them, the evolved CA rules present a better generalization ability. Mestre em Ciência da Computação 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.