Details

Novas abordagens na evolução de autômatos celulares aplicados ao escalonamento de tarefas em multiprocessadores

by Vidica, Paulo Moisés

Abstract (Summary)
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 baseadoem autômatos celulares (ACs) que tem o objetivo de alocar tarefas de um programa paralelo emum sistema com dois processadores. O algoritmo de escalonamento apresenta duas fases: a fase deaprendizagem e a fase de operação. O propósito da fase de aprendizagem é descobrir regras de ACsaptas ao escalonamento das tarefas. A busca por estas regras é conduzida com a utilização de umalgoritmo genético (AG). Na fase de operação, as regras descobertas na fase anterior são aplicadasem novas instâncias de programas paralelos. É esperado que, para qualquer alocação inicial dastarefas, 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 publicadosaté então para a arquitetura do escalonador de tarefas. Após o entendimento e reprodução de algunsresultados publicados, a meta do trabalho passou a ser investigar a capacidade de generalização dasregras de transição de ACs. Ou seja, investigar se as regras encontradas para um programa paraleloespecífico poderiam ser aplicadas, com sucesso, em outros programas. A principal conclusão dessainvestigaçã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 escalonamentobaseado em ACs: a evolução conjunta e um ambiente coevolutivo. Resultados obtidos através destasnovas abordagens mostram que, com o seu uso, as regras de ACs evoluídas apresentam uma melhorcapacidade de generalização.
This document abstract is also available in English.
Bibliographical Information:

Advisor:Keiji Yamanaka; Gina Maira Barbosa de Oliveira; Andre Carlos Ponce de Leon Ferreira de Carvalho

School:Universidade Federal de Uberlândia

School Location:Brazil

Source Type:Master's Thesis

Keywords:Autômatos celulares Escalonamento de tarefas em uma arquitetura multiprocessadora CIENCIA DA COMPUTACAO Inteligência Artificial

ISBN:

Date of Publication:01/29/2007

© 2009 OpenThesis.org. All Rights Reserved.