Skip to content
Email: poscomp@ufabc.edu.br
facebook
twitter
youtube
instagram
linkedin
PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO
  • Início
  • Sobre o programa
    • Apresentação
    • Objetivos e perfil
    • Estrutura do curso
    • Perguntas frequentes
    • Premiações e destaques
  • Processos seletivos
    • Mestrado e Doutorado
      • Resultados dos Processos Seletivos
    • Aluno especial
    • Mestrado Acadêmico para Inovação
    • Doutorado Acadêmico Industrial
    • Doutorado sanduiche
    • Pós-doutorado
    • Histórico de Processos Seletivos
  • Pesquisa
    • Linhas de pesquisa
    • Laboratórios
  • Docentes
  • Discentes
    • Disciplinas ofertadas
    • Dúvidas sobre matrículas em geral (alunos regulares)
    • Manual de sobrevivência
    • Bolsas de estudo
    • Proficiência em inglês e exame
    • Exame de qualificação
    • Defesa de dissertação ou tese
    • Bancas agendadas ↗
    • Código de ética da UFABC
    • Ex-alunos (Alumni)
  • Eventos
    • Seminários em computação
    • Workshops
    • Mini-Cursos
    • Histórico
  • Institucional
    • Coordenação
    • Documentos e normativas
    • Lista de orientandos por orientadores ↗
    • Dissertações e teses defendidas ↗
    • Calendário acadêmico ↗
    • Eleições para coordenação
    • (Re)Credenciamento de docentes
  • Pós-Graduação UFABC ↗
  • Social

Siang Wun Song

Home > Seminários em computação > Siang Wun Song

Siang Wun Song

Posted on 09/05/201824/08/2021 by Coordenador
0

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.

PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO

  • Início
  • Sobre o programa
  • Processos seletivos
  • Docentes
  • Discentes

Acesso rápido

  • Perguntas frequentes
  • Como chegar
  • Institucional

Translate

Contato e Endereço

Email: poscomp@ufabc.edu.br

Universidade Federal do ABC - UFABC

Endereço: Av dos Estados, 5001 - Bairro Bangu - Santo André - SP
CEP: 09210-580

© 2025 PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO | WordPress Theme: Enlighten
Translate »