Abordagens baseadas em autômatos celulares síncronos para o escalonamento estático de tarefas em multiprocessadores

Autor: Carneiro, Murillo Guimarães
Přispěvatelé: Oliveira, Gina Maira Barbosa de, Julia, Rita Maria da Silva, Lopes, Heitor Silvério
Jazyk: portugalština
Rok vydání: 2012
Předmět:
Zdroj: Repositório Institucional da UFU
Universidade Federal de Uberlândia (UFU)
instacron:UFU
Popis: Universidade Federal de Uberlândia The Static Task Scheduling Problem (STSP) in multiprocessors aims to allocate a set of computational tasks that compose a parallel application in the nodes of a multiprocessor architecture. An optimal solution for an instance of STSP is such that the precedence constraints are satised and the runtime - or makespan - is minimized. The problem is NPComplete, even limited to the simplest case: a parallel system with only two processors. Approaches proposed to solve it typically use heuristics, such as HLFET ( Highest Level First with Estimated Time) and MCP (Modied Critical Path), or metaheurístics, such as genetic algorithms (GA) and simulated annealing (SA) in an attempt to nd good results for the problem. However, in these approaches, a computational eort is used to solve an instance of the problem and when a new instance is presented to the algorithm, the process needs to start again from scratch. In this context, the cellular automata-based scheduling is a promising approach because its main feature is the extraction of knowledge while scheduling an application and its subsequent reuse in other instances. However some desirable features in CA-based scheduling such as: (i) massive parallelism inherent to CA, (ii) usage of an arbitrary number of processors, (iii) eective reuse of the knowledge extracted from parallel applications and others, have not been successfully exploited by previous models in the literature. This dissertation investigates new CA-based approaches for STSP. They were evaluated systematically and compared to previous approaches of CA-based scheduling and heuristic and metaheuristic methods. Some contributions of this research are three new models of schedulers (SCAS, SCAS-H and SCAS-HV) related to extraction, evaluation and reuse of knowledge, a new strategy to initialize CA lattices determined by a deterministic heuristic, a new strategy to analyze the dynamic behavior of CA rules (rule penalization) at runtime, and two new neighborhood models (Vpl-c1 e Vpl-c2) with simple structure, but able to extract information from parallel applications and use an arbitrary number of processors. The results showed it is possible to ensure the successful employment of parallelism in CAs as well as a good performance in the learning phase, in which the values found by new models are close to those of genetic algorithms (taken by reference) and superior than those obtained by heuristics and some metaheuristics. Furthermore, statistical tests were performed and proved the superiority of the new approaches in relation to other CA-based scheduling models. The reuse of knowledge was also evaluated and its performance was proved competitive in the new approaches. Finally, the methods developed showed the scheduling based on CA has great potential to eciently schedule tasks in multiprocessor systems. This potential can be better exploited when the proposed models work directly on parallel hardware architectures. O problema de escalonamento estático de tarefas computacionais (PEET) em uma arquitetura multiprocessada consiste em alocar tarefas que compõem um programa paralelo entre os nós de uma arquitetura com múltiplos processadores. Uma solução ótima de uma instância do PEET é tal que as restrições de precedência entre as tarefas sejam atendidas e o tempo total de execução - ou makespan - é minimizado. O problema é NP-Completo, mesmo limitado ao caso mais simples: um sistema paralelo com apenas dois processadores. Diante disso, métodos heurísticos, tais como HLFET (Highest Level First with Estimated Time) e MCP (Modied Critical Path), e meta-heurísticas, tais como algoritmos genéticos (AG) e simulated annealing (SA) têm sido frequentemente empregados na tentativa de encontrar boas soluções para o problema. Contudo, eles não apresentam qualquer habilidade para extrair conhecimento do processo de escalonamento de uma aplicação paralela e precisam reiniciar o processo a cada nova instância. Neste contexto, o escalonamento baseado em autômatos celulares (ACs) tem se mostrado promissor, uma vez que tem por objetivo a extração do conhecimento sobre o processo de escalonamento de um programa paralelo e sua consequente reutilização em novas instâncias. Contudo, algumas características desejáveis ainda não foram exploradas com sucesso pelos modelos existentes na literatura: (i) paralelismo massivo intrínseco aos ACs, (ii) uso de um número arbitrário de processadores, (iii) reuso eciente do conhecimento extraído sobre outras aplicações paralelas, entre outras. Desse modo, novas abordagens baseadas em ACs para o PEET foram investigadas. Essas abordagens foram avaliadas sistematicamente em relação a outras abordagens anteriores de escalonamento baseadas em AC e também a métodos heurísticos e meta-heurísticos. Dentre as contribuições da pesquisa estão três novos modelos de escalonadores (EACS, EACS-H e EACS-HV) relacionados à extração, avaliação e reuso do conhecimento; uma nova estratégia para inicializar os reticulados dos ACs baseada em uma heurística determin ística; uma nova estratégia para análise do comportamento dinâmico das regras do AC (penalização da regra) em tempo de execução e dois novos modelos de vizinhança de estrutura simples, porém com capacidade de extração de informações da aplicação paralela (Vpl-c1 e Vpl-c2) e uso de um número arbitrário de processadores. Como resultado dos experimentos, foi possível garantir o emprego bem sucedido do paralelismo nos ACs, além de um bom desempenho na fase de aprendizagem, onde os valores encontrados pelas abordagens estiveram próximos daqueles tomados por referência e foram superiores a heurísticas e algumas meta-heurísticas. Ainda, testes estatísticos foram realizados e comprovaram a superioridade das novas abordagens em relação a outros trabalhos baseados em AC. O reuso do conhecimento também foi avaliado e se mostrou competitivo nas novas abordagens. Em suma, as abordagens desenvolvidas mostram que o escalonamento baseado em AC possui grande potencial para o escalonamento eciente de tarefas em sistemas multiprocessados. Logo, este potencial pode ser melhor explorado quando os modelos propostos trabalham diretamente sobre arquiteturas de hardware paralelo. Mestre em Ciência da Computação
Databáze: OpenAIRE
Externí odkaz: