Resumo: A multijunção espacial é uma consulta importante em bancos de dados espaciais, que tem sido amplamente utilizada em muitas aplicações científicas. Por ser intensiva em dados e em computação, ela geralmente é processada em sistemas distribuídos, onde cada máquina é responsável pelo processamento de um fragmento de consulta. O fragmento de consulta é um par de partições de dados alinhadas por um predicado espacial, que chamaremos de tarefa. Para que essas tarefas sejam processadas, elas devem ser escalonadas e, nesse cenário, o objetivo principal é executar esse escalonamento de forma que a carga da consulta seja distribuída igualmente entre as máquinas, minimizando assim o makespan, ou seja, o tempo total de execução. Além disso, o processamento de uma tarefa exige que as partições de dados sejam transferidas para a máquina na qual a tarefa foi escalonada, ocasionando um custo de comunicação, que também deve ser minimizado. No entanto, se a partição de dados já estiver na máquina, nenhum custo de comunicação é incorrido. Para esse problema de escalonamento, dois modelos de programação linear foram propostos recentemente: o modelo FM, que considera o cenário descrito acima, e o modelo SM, que pressupõe que o custo da comunicação será incorrido toda vez que uma tarefa for processada em uma máquina. Para o modelo SM, foram desenvolvidos algoritmos que encontram soluções viáveis aproximadas. O objetivo deste trabalho foi propor um algoritmo guloso para o escalonamento de multijunções espaciais usando o modelo FM. O algoritmo guloso proposto, chamado EBCVDMC, usa o cálculo do coeficiente de variação da dispersão das tarefas para calcular o quanto a distribuição das tarefas está desbalanceada. As soluções encontradas pelo algoritmo foram melhores que as encontradas por um método de relaxação linear (LP) em 68 das 80 instâncias avaliadas. Comparado a um método de relaxação lagrangiana (LR) para o SM, o método se mostrou competitivo em relação ao valor ótimo e encontrou melhores soluções para 4 instâncias. Por ser um algoritmo de complexidade O(nm^2), sendo n a quantidade de tarefas e m o número de máquinas, o EBCVDMC poderá ser usado em instâncias de multijunção para as quais o tempo de execução restrinja o tempo de escalonamento da consulta.

Palavras-chave: Dados Espaciais; Processamento Distribuído; Escalonamento; Algoritmo guloso.

Monografia completa. Copyright © 2019. Todos os direitos reservados.

Citação: Ronaldo Nogueira de Sousa. Algoritmo Guloso para Escalonamento de Multijunções Espaciais em Sistemas Distribuídos usando o Modelo FM. Monografia. Bacharelado em Ciências da Computação. Universidade Federal de Goiás, Regional Jataí. Jataí, GO, Brasil. 2019. 53p.

Copiar citação no formato bibtex.