Publicação: Abordagens baseadas em autômatos celulares síncronos para o
escalonamento estático de tarefas em multiprocessadores
Carregando...
Arquivos
Tipo do documento
Data
Direito de acesso
Área do conhecimento
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Título da Revista
ISSN da Revista
Título de Volume
Autores
Orientador
Coorientador
Resumo
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.
Abstract
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.
Palavras-chave
Autômato celular, Escalonamento estático de tarefas, Algoritmos evolutivos, Heurísticas, Meta-heurísticas, Cellular automata, Task static scheduling, Evolutionary algorithms, Heuristics, Metaheuristics, Inteligência artificial
Citação
CARNEIRO, Murillo Guimarães. Abordagens baseadas em autômatos celulares síncronos para o
escalonamento estático de tarefas em multiprocessadores. 2012. 155 f. Dissertação (Mestrado em Ciências Exatas e da Terra) - Universidade Federal de Uberlândia, Uberlândia, 2012. DOI https://doi.org/10.14393/ufu.di.2012.102