Seminário integrante da IV Semana do CMCC

Título: Um algoritmo paralelo para árvore geradora mínima

Palestrante: Siang Wun Song (IME-USP)

Data e local: Quarta-feira, 20 de junho de 2018, às 16:30, Santo André, Bloco A, auditório A-109-0

Resumo:

 Dado um grafo conexo com pesos nas arestas, computar uma árvore geradora mínima (minimum spanning tree ou MST) é um problema fundamental em Teoria de Grafos. Esse problema surge como um subproblema em muitas aplicações. Nesta palestra, apresentamos um algoritmo paralelo para computar uma MST, com uma implementação em uma máquina com GPU (Graphics Processing Unit). Algoritmos paralelos anteriores para resolver o problema de MST usam um passo em que é resolvido o problema de list ranking, cuja implementação paralela não apresenta bom desempenho na prática, embora apresente boa complexidade em teoria. O algoritmo paralelo aqui proposto não é baseado no problema de list ranking. Ele é baseado numa estrutura de dados denominada strut e no algoritmo de Boruvka. Usando o modelo de computação paralela BSP/CGM (Bulk Synchronous Parallel/Coarse Grained Multicomputer), mostramos que o algoritmo paralelo usa O(log n) superpassos ou iterações, onde n é o número de vértices do grafo. Implementamos o algoritmo numa máquina com GPU. A eficiência do algoritmo é comprovada por resultados experimentais. Testes realizados mostram que, para grafos construídos aleatoriamente com número de vértices de 10.000 a 30.000 e densidade de 0,02 a 0,2, o algoritmo constrói uma MST em no máximo seis iterações. Quando o grafo não é esparso, a nossa implementação alcançou um ganho (speedup) de mais que 50 e, para algumas instâncias, chegando ao valor de 296 vezes mais rápido que um algoritmo sequencial conhecido.

Biografia:

É professor titular aposentado do Departamento de Ciência da Computação do IME-USP, onde foi diretor do IME e docente desde 1971. Foi membro, em 2005, da equipe de elaboração do projeto pedagógico da UFABC e professor visitante da UFABC de 2010 a 2014. Sua área de pesquisa é Projeto de Algoritmos Paralelos.