Use este identificador para citar ou linkar para este item:
https://repositorio.ufu.br/handle/123456789/12579| Tipo do documento: | Dissertação |
| Tipo de acesso: | Acesso Aberto |
| Título: | Escalonamento de tarefas baseado em autômatos celulares com uso dos parâmetros de previsão do comportamento dinâmico |
| Autor(es): | Carvalho, Tiago Ismailer de |
| Primeiro orientador: | Oliveira, Gina Maira Barbosa de |
| Primeiro membro da banca: | Oliveira, Pedro Paulo Balbi de |
| Segundo membro da banca: | Backes, André Ricardo |
| Resumo: | O problema de escalonamento investigado nessa dissertação consiste em distribuir as tarefas de um programa nos processadores de um sistema de maneira que o tempo total de execução do programa seja minimizado. Mesmo a versão mais simples desse problema é do tipo NP-completo. Portanto, não é possível determinar com exatidão a solução ótima de escalonamento em um tempo computacional viável. Por outro lado, a performance dos computadores atuais se relaciona diretamente com a solução desse problema, uma vez que os novos dispositivos utilizam um número crescente de processadores, o que levou à busca de abordagens aproximadas. Para oferecer uma solução aproximada de escalonamento, as heurísticas e meta-heurísticas têm sido aplicadas ao problema. Nesse tipo de estratégia, para cada instância do problema, o algoritmo de escalonamento constrói uma solução ótima ou sub-ótima. No entanto, esses métodos não são capazes de extrair conhecimento a partir do processo de escalonamento de uma instância para aplicar em novos programas. Com a motivação de propor algoritmo onde o conhecimento sobre o processo de escalonamento seja aprendido e reutilizado, foi investigada recentemente uma nova abordagem que utiliza o modelo matemático chamado autômato celular. O escalonador de tarefas baseado em autômato celular funciona em dois modos. No modo de aprendizagem, as regras de transição que ditam o comportamento do modelo são treinadas por um algoritmo genético com o intuito de encontrar boas soluções de escalona- mento. No modo de operação, as regras que foram treinadas anteriormente são aplicadas para determinar o escalonamento para novas instâncias do problema. Foi identificado no modelo precursor de escalonador baseado em autômatos celulares chamado SCAS-HP, que a maioria das regras encontradas no modo de treinamento não exibem comportamento dinâmico adequado, uma vez que são caóticas. Em outras aplicações de autômatos celulares encontradas na literatura, parâmetros de previsão de comportamento dinâmico foram utilizadas para auxiliar a busca evolutiva. Nesse trabalho realizamos a seleção e investigação de alguns desses parâmetros com o objetivo de identificar as regras do modo de treinamento com comportamento adequado para serem usadas no modo de operação. O parâmetro conhecido como sensitividade µ foi selecionado para se construir uma heurística para guiar a busca evolutiva na direção de regras não-caóticas. Um novo modelo de escalonador foi elaborado incorporando-se a heurística baseada no parâmetro de previsão e foi dominado EACS-CD: Escalonador Baseado em Autômatos Celulares Síncronos com Previsão de Comportamento Dinâmico. Experimentos foram realizados com o novo modelo, onde o mesmo foi comparado ao modelo antecessor SCAS-HP. Foi possível observar que as novas regras evoluídas exibem comportamento menos frequentemente caótico e desempenho melhor ao serem aplicadas em novas instâncias não vistas durante o treinamento. |
| Abstract: | Multiprocessor scheduling has been one of the most classic NP-hard optimization problem. Given a program divided by N jobs and a set of P processors, the problem is to assign each job j є N to a processor p є P in a way that minimizes the execution time for 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-heuristics has been studied. In that kind of approach a solution is searched for a specific instance of the problem. Nevertheless, the heuristics and metaheuristic are incapable of acquiring a knowledge about scheduling process which could be extracted and potentially used for solving new instances of scheduling problem. For this purpose was proposed the use of a cellular automata. In cellular automata based multiprocessor scheduling two modes are used. In learning mode, a genetic algorithm is applied to discover rules of cellular automata suitable for solving a instance of a scheduling problem. In operation mode, discovered rules of cellular automata are able to find an optimal or suboptimal solution of the scheduling problem for many 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 the scheduling problem in operation mode because of their caotic behaviour. On other hand, the classic approach for handling the behaviour of cellular automata rules is done by calculating a parameter considering that rule. The parameter sensitivity µ was selected for an heuristic approach for avoiding caotic rules. A new scheduler was proposed EACS-CD - Cellular Automata Based Scheduler with Dynamic Behaviour. This new scheduler was compared with SCAS-HP. Experimental results showed that in the new model fewer caotic rules was trained and thus the perfomance of the new scheduler was better in operation mode. |
| Palavras-chave: | Algoritmo genético Autômato celular Escalonamento estático de tarefas Parâmetros para previsão de comportamento dinâmico dos autômatos celulares Genetic algorithm Cellular automata Multiprocessor scheduling Cellular automata parameters |
| Área(s) do CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Idioma: | por |
| País: | BR |
| Editora: | Universidade Federal de Uberlândia |
| Sigla da instituição: | UFU |
| Departamento: | Ciências Exatas e da Terra |
| Programa: | Programa de Pós-graduação em Ciência da Computação |
| Referência: | CARVALHO, Tiago Ismailer de. Escalonamento de tarefas baseado em autômatos celulares com uso dos parâmetros de previsão do comportamento dinâmico. 2014. 133 f. Dissertação (Mestrado em Ciências Exatas e da Terra) - Universidade Federal de Uberlândia, Uberlândia, 2014. DOI https://doi.org/10.14393/ufu.di.2014.419 |
| Identificador do documento: | https://doi.org/10.14393/ufu.di.2014.419 |
| URI: | https://repositorio.ufu.br/handle/123456789/12579 |
| Data de defesa: | 25-Ago-2014 |
| Aparece nas coleções: | DISSERTAÇÃO - Ciência da Computação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| EscalonamentoTarefasBaseado.pdf | 4.81 MB | Adobe PDF |  Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.