Projeto e análise de desempenho de um algoritmo iterativo para grandes grafos em um ambiente distribuído

Abstract

Atualmente grandes volumes de dados são gerados e coletados por meio de sensores, dispositivos e redes sociais. A capacidade de lidar com grandes massas de dados tornou-se um importante fator para o sucesso de muitas organizações, exigindo, cada vez mais, a utilização de processamento paralelo e distribuído. Para auxiliar os desenvolvedores a projetar programas distribuídos, existem várias ferramentas (frameworks), como Apache Hadoop e Spark. Esses frameworks fornecem diversos parâmetros de configuração (por exemplo, o Hadoop tem mais de 200) e atribuir valores otimizados a todos eles não é uma tarefa simples. Este trabalho investiga a influência desses parâmetros no desempenho do Apache Hadoop, utilizando o algoritmo HEDA, um algoritmo iterativo que calcula métricas de centralidade em grandes grafos. A execução do HEDA em uma rede complexa é extremamente importante, pois existem várias medidas de centralidade que determinam a importância de um vértice dentro do grafo. Observou-se que, em alguns casos, a melhoria no tempo de execução atingiu aproximadamente 80% aplicando os valores propostos por este trabalho aos parâmetros de configuração do Hadoop. Além disso, foi possível aumentar em cinco vezes o uso dos processadores e melhorar consideravelmente a escalabilidade. O trabalho também apresenta os métodos aplicados para preparar, executar e analisar os experimentos, o que poderá auxiliar em novos estudos.

Keywords

• Hadoop
• Grafo
• Parâmetros
• Algoritmos Iterativos