Grafos em CUDA

[Thársis Tuani Pinto Souza]

Alguém aí já implementou algoritmos em grafos em CUDA?

Os algoritmos tradicionais em CUDA geralmente lidam com estruturas regulares de dados, como matrizes ou vetores nos quais os acessos seguem um padrão bem definido.
O problema de grafos é que são estruturas irregulares, construídas ad-hoc, possivelmente desbalanceadas e com acessos sem padrão bem definido. Isso tudo são complicantes em uma arquitetura many-core como CUDA. Por isso, o número de trabalhos no assunto é mínimo.

Alguém tem alguma experiência no assunto para compartilhar?

Att.

--
Thársis T. P. Souza
Engenheiro de Computação - Unicamp
Mestrando em Ciência da Computação - USP
Analista de Sistemas - Centro de Computação Eletrônica - USP

[Victor Oliveira]

já cheguei a implementar uma estrutura de dados baseada em grafos pra
processamento de imagens [segmentação]. basicamente, não vale a pena
nada na gpu que não tenha acessos regulares à memória, perde muita
escalabilidade por causa do gargalo na memória.

até

2011/4/13 Thársis Tuani Pinto Souza <souza....@gmail.com>:

> --
> Você está recebendo esta mensagem porque se inscreveu no grupo "GPU Brasil"
> dos Grupos do Google.
> Para postar neste grupo, envie um e-mail para gpub...@googlegroups.com.
> Para cancelar a inscrição nesse grupo, envie um e-mail para
> gpubrasil+...@googlegroups.com.
> Para obter mais opções, visite esse grupo em
> http://groups.google.com/group/gpubrasil?hl=pt-BR.
>

[Thársis Tuani Pinto Souza]

Oi Victor,

qual estrutura de dados você usou?
Lista de adjacência compacta?

Matriz de incidencia tradicional eh ruim para grafos muitos grandes por ser O(n^2) no espaço.

Outro problema de grafos é que a maioria das threads acaba ficando ociosa devido a falta de estrutura do grafo. Uma técnica para isso é fazer um scan periodicamente para ver quem estah ativo e daí lançar exatamente o numero necessario de threads para um próximo passo do algoritmo.

Att.

--
Thársis T. P. Souza
Engenheiro de Computação - Unicamp
Mestrando em Ciência da Computação - USP
Analista de Sistemas - Centro de Computação Eletrônica - USP

2011/4/14 Victor Oliveira <victor...@gmail.com>

[Tiago Carneiro]

Prezados,

eu estou implementando alguns algoritmos de busca em grafos, e posso
dizer que é algo um tanto complicado de se fazer pra GPGPU.

Já utilizei OpenMP e ficou nota dez, o desafio agora é implementar para GPGPU.

Os resultados estão cada vez melhores, só não sei se é algo que
realmente vale a pena.

Se vocês quiserem eu passo alguns artigos de grafos em GPGPU que achei.

Forte abraço,

Tiago Carneiro.

Em 14 de abril de 2011 21:28, Thársis Tuani Pinto Souza
<souza....@gmail.com> escreveu:

[André Körbes]

Oi Thársis,

Trabalhei na implementação do algoritmo watershed para segmentação de imagens que é *baseado* em grafos. Fizemos duas implementações, uma em que uma das etapas é basicamente uma busca em profundidade, e outra que é uma busca em largura - uma SPF - a partir de raízes.

A busca em profundidade foi baseada no algoritmo union-find, e a SPF é baseada no Ford-Bellmann.

Como o Victor já falou, os resultados são um tanto decepcionantes. No Union-Find, conseguimos melhorar o desempenho em todas as outras etapas, menos na que trata da conectividade entre os vértices, que é o mesmo que a rotulação. O Ford-Bellmann é baseado em iterações até a convergência de *todo* o grafo, então precisamos lançar o kernel diversas vezes até não haver mais alterações. Isto fez com que o algoritmo ficasse consideravelmente mais lento que o Union-Find.

Em termos de estrutura de dados, usamos apenas uma matriz, não de adjacência, mas do mesmo tamanho da imagem, pois cada vértice corresponde a um pixel, e está conectado apenas a um outro vértice, cujo índice é armazenado na matriz.

André

2011/4/14 Thársis Tuani Pinto Souza <souza....@gmail.com>

[Thársis Tuani Pinto Souza]

Acredito que as principais referências no assunto são:

1. Large Graph Algorithms for Massively Multithreaded Architectures
2. Accelerating large graph algorithms on the GPU using CUDA
3. Exploring the Limits of GPUs With Parallel Graph Algorithms

Eles conseguiram resultados até interessantes. Algo como rodar um BFS em um grafo com milhões de vértices com grau médio 12 em 1 segundo. A estrutura de dados clássica é realmente uma lista de adjacência compacta e eventualmente fazendo scan dos vértices ativos.

Porém, gostaria de saber o comportamento para grafos com número de vértices abaixo dos milhões.
Ou se alguém realizou implementação com outra estrutura de dados.

Tiago, você tem algum artigo além dos que eu citei para dar como referência?

Att.

--
Thársis T. P. Souza
Engenheiro de Computação - Unicamp
Mestrando em Ciência da Computação - USP
Analista de Sistemas - Centro de Computação Eletrônica - USP

2011/4/14 André Körbes <andre....@gmail.com>

[Tiago Carneiro]

Caro camarada,

os únicos que tenho a acrescentar, fora esses que você falou, são os que seguem:

1) Distributed Genetic Programmingon GPU using CUDA

2) Parallel Graph Component Labelling with GPUs and CUDA

Se alguém quiser, é só me pedir por e-mail.

Você poderia me passar o 3. Exploring the Limits of GPUs With
Parallel Graph Algorithms ??

Forte abraço,

Tiago Carneiro.

Em 14 de abril de 2011 21:50, Thársis Tuani Pinto Souza
<souza....@gmail.com> escreveu: