Escalonamento de Tarefas Baseado em autômatos celulares ... ?· escalonamento de arefas baseado em…

Embed Size (px)

Text of Escalonamento de Tarefas Baseado em autômatos celulares ... ?· escalonamento de arefas baseado...

  • UNIVERSIDADE FEDERAL DE UBERLNDIA

    FACULDADE DE CINCIA DA COMPUTAO

    PROGRAMA DE PS-GRADUAO EM CINCIA DA COMPUTAO

    ESCALONAMENTO DE TAREFAS BASEADO EMAUTMATOS CELULARES COM USO DOS PARMETROS

    DE PREVISO DO COMPORTAMENTO DINMICO

    TIAGO ISMAILER DE CARVALHO

    Uberlndia - Minas Gerais

    2014

  • UNIVERSIDADE FEDERAL DE UBERLNDIA

    FACULDADE DE CINCIA DA COMPUTAO

    PROGRAMA DE PS-GRADUAO EM CINCIA DA COMPUTAO

    TIAGO ISMAILER DE CARVALHO

    ESCALONAMENTO DE TAREFAS BASEADO EMAUTMATOS CELULARES COM USO DOS PARMETROS

    DE PREVISO DO COMPORTAMENTO DINMICO

    Dissertao de Mestrado apresentada Faculdade de Cin-

    cia da Computao da Universidade Federal de Uberlndia,

    Minas Gerais, como parte dos requisitos exigidos para ob-

    teno do ttulo de Mestre em Cincia da Computao.

    rea de concentrao: Inteligncia Articial.

    Orientadora:

    Profa. Dra. Gina Maira Barbosa de Oliveira

    Uberlndia, Minas Gerais

    2014

  • Dados Internacionais de Catalogao na Publicao (CIP)

    Sistema de Bibliotecas da UFU, MG, Brasil.

    C331e

    2014

    Carvalho, Tiago Ismailer de, 1988-

    Escalonamento de tarefas baseado em autmatos celulares com uso

    dos parmetros de previso do comportamento dinmico / Tiago Ismailer

    de Carvalho. - 2014.

    130 f. : il.

    Orientadora: Gina Maira Barbosa de Oliveira.

    Dissertao (mestrado) - Universidade Federal de Uberlndia,

    Programa de Ps-Graduao em Cincia da Computao.

    Inclui bibliografia.

    1. Computao - Teses. 2. Algoritmos genticos - Teses. 3.

    Autmato celular - Teses. I. Oliveira, Gina Maira Barbosa de, . II.

    Universidade Federal de Uberlndia. Programa de Ps-Graduao em

    Cincia da Computao. III. Ttulo.

    CDU: 681.3

  • UNIVERSIDADE FEDERAL DE UBERLNDIA

    FACULDADE DE CINCIA DA COMPUTAO

    PROGRAMA DE PS-GRADUAO EM CINCIA DA COMPUTAO

    Os abaixo assinados, por meio deste, certicam que leram e recomendam para a Facul-

    dade de Cincia da Computao a aceitao da dissertao intitulada Escalonamento

    de Tarefas Baseado em autmatos celulares com Uso dos Parmetros de Pre-

    viso do Comportamento Dinmico por Tiago Ismailer de Carvalho como parte

    dos requisitos exigidos para a obteno do ttulo de Mestre em Cincia da Compu-

    tao.

    Uberlndia, 3 de Agosto de 2014

    Orientadora:

    Profa. Dra. Gina Maira Barbosa de Oliveira

    Universidade Federal de Uberlndia

    Banca Examinadora:

    Prof. Dr. Pedro Paulo Balbi de Oliveira

    Universidade Presbiteriana Mackenzie

    Prof. Dr. Andr Ricardo Backes

    Universidade Federal de Uberlndia

  • UNIVERSIDADE FEDERAL DE UBERLNDIA

    FACULDADE DE CINCIA DA COMPUTAO

    PROGRAMA DE PS-GRADUAO EM CINCIA DA COMPUTAO

    Data: Agosto de 2014

    Autor: Tiago Ismailer de Carvalho

    Ttulo: Escalonamento de Tarefas Baseado em autmatos celulares com

    Uso dos Parmetros de Previso do Comportamento Dinmico

    Faculdade: Faculdade de Cincia da Computao

    Grau: Mestrado

    Fica garantido Universidade Federal de Uberlndia o direito de circulao e impresso

    de cpias deste documento para propsitos exclusivamente acadmicos, desde que o autor

    seja devidamente informado.

    Autor

    O AUTOR RESERVA PARA SI QUALQUER OUTRO DIREITO DE PUBLICAO

    DESTE DOCUMENTO, NO PODENDO O MESMO SER IMPRESSO OU REPRO-

    DUZIDO, SEJA NA TOTALIDADE OU EM PARTES, SEM A PERMISSO ESCRITA

    DO AUTOR.

    cTodos os direitos reservados a Tiago Ismailer de Carvalho

  • Dedicatria

    A todos que amo, amei e amarei!

  • Agradecimentos

    minha me Renilda, a mulher mais determinada e disposta desse universo (sem

    exageros, ok?) por ter tido a coragem e f de mudar da nossa casa para que seus lhos

    pudessem estudar.

    Ao meu pai Antnio, o homem mais trabalhador e sensvel desse mundo (continuo sem

    exagerar), por ter tido a fora e perseverana para suportar a distncia de seus lhos e

    esposa.

    Aos meus irmos, tico e teco, tambm conhecidos como Douglas (dodi) e Cristian

    (kiki) pelos bons momentos e brigas (sim, me zeram mais forte), e tambm pela certeza

    de que enquanto vocs existem eu no me sinto s.

    toda minha famlia, cujos nomes no esto aqui porque a maioria comea com R e

    isso aqui no RAP (ok?), amo todos vocs.

    A todos meus amigos. Em especial: Fabito e Sarita, pela companhia no lab e nos

    barzinhos (secret)!

    A Felipe pela fora, companheirismo e pacincia no momento mais difcil desse pro-

    cesso: a escrita dessa dissertao.

    Aos mestres, em especial Mrcia, Rita, Gina, Jos Maria: os caras que eu quero ser

    quando crescer.

    Aos msicos e bandas: Arcade Fire, Fleet Foxes, Radiohead, Daft Punk, Frank Ocean,

    Utada Hikaru, The XX, Leo Fressato e etc.

    A deus ou aos deuses, mesmo que eu no saiba com exatido o que isso signica.

    FAPEMIG pelo apoio nanceiro. FACOM e UFU pelo apoio de infraestrutura e

    de conhecimento.

    E principalmente professora Gina pelo prossionalismo, apoio, pacincia, amizade,

    compreenso, e orientao em todos os momentos da realizao deste trabalho.

  • If you're not confused, you're not paying attention

    (Tom Peters)

  • Resumo

    O problema de escalonamento investigado nessa dissertao consiste em distribuir astarefas de um programa nos processadores de um sistema de maneira que o tempo total deexecuo do programa seja minimizado. Mesmo a verso mais simples desse problema do tipo NP-Completo. Portanto, no possvel determinar com exatido a soluo timade escalonamento em um tempo computacional vivel. Por outro lado, a performance doscomputadores atuais se relaciona diretamente com a soluo desse problema, uma vez queos novos dispositivos utilizam um nmero crescente de processadores, o que levou buscade abordagens aproximadas.

    Para oferecer uma soluo aproximada de escalonamento, as heursticas e meta-heursti-cas tm sido aplicadas ao problema. Nesse tipo de estratgia, para cada instncia doproblema, o algoritmo de escalonamento constri uma soluo tima ou sub-tima. Noentanto, esses mtodos no so capazes de extrair conhecimento a partir do processo deescalonamento de uma instncia para aplicar em novos programas. Com a motivao depropor algoritmo onde o conhecimento sobre o processo de escalonamento seja aprendidoe reutilizado, foi investigada recentemente uma nova abordagem que utiliza o modelomatemtico chamado autmato celular.

    O escalonador de tarefas baseado em autmato celular funciona em dois modos. Nomodo de aprendizagem, as regras de transio que ditam o comportamento do modelo sotreinadas por um algoritmo gentico com o intuito de encontrar boas solues de escalona-mento. No modo de operao, as regras que foram treinadas anteriormente so aplicadaspara determinar o escalonamento para novas instncias do problema. Foi identicado nomodelo precursor de escalonador baseado em autmatos celulares chamado SCAS-HP, quea maioria das regras encontradas no modo de treinamento no exibem comportamentodinmico adequado, uma vez que so caticas.

    Em outras aplicaes de autmatos celulares encontradas na literatura, parmetrosde previso de comportamento dinmico foram utilizadas para auxiliar a busca evolutiva.Nesse trabalho realizamos a seleo e investigao de alguns desses parmetros com oobjetivo de identicar as regras do modo de treinamento com comportamento adequadopara serem usadas no modo de operao. O parmetro conhecido como sensitividade foi selecionado para se construir uma heurstica para guiar a busca evolutiva na direode regras no-caticas. Um novo modelo de escalonador foi elaborado incorporando-sea heurstica baseada no parmetro de previso e foi dominado EACS-CD: EscalonadorBaseado em Autmatos Celulares Sncronos com Previso de Comportamento Dinmico.Experimentos foram realizados com o novo modelo, onde o mesmo foi comparado aomodelo antecessor SCAS-HP. Foi possvel observar que as novas regras evoludas exibemcomportamento menos frequentemente catico e desempenho melhor ao serem aplicadasem novas instncias no vistas durante o treinamento.

    Palavras chave: algoritmo gentico, autmato celular, escalonamento esttico de tare-

    fas, parmetros para previso de comportamento dinmico dos autmatos celulares.

  • Abstract

    Multiprocessor scheduling has been one of the most classic NP-hard optimizationproblem. Given a program divided by N jobs and a set of P processors, the problem isto assign each job j N to a processor p P in a way that minimizes the execution timefor that program. This problem is related with the perfomance of the modern computers,whose is designed with a increasingly number of processors.

    To solve this problem many heuristics and meta-heuristis has been studied. In thatkind of approach a solution is searched for a specic instance of the problem. Nevertheless,the heurstics and metaheuristic are incapable of acquiring a knowledge about schedulingprocess which could be extracted and potentially used for solving new instances of sche-duling problem. For this purpose was proposed the use of a cellular automata.

    In cellular automata based multiprocessor scheduling two modes are used. In learningmode, a genetic algorithm is applied to discover rules of cellular automata suitable forsolving a instance of a scheduling problem. In operation mode, discovered rules of cellularautomata are able to nd an optimal or suboptimal solution of the scheduling problem formany program graph. In a recent celullar automata based scheduling model (SCAS-HP)was stated that some rules evolved in this scheduler was not appropriated for solving thescheduling problem in operation mode because of their caotic behaviour.

    On other hand, the classic approach for handling the behaviour of cel