Dissertação

Measures Computation and Pattern Detection in Social Networks with GPU Acceleration EVALUATED

Aplicar medidas conhecidas a grafos de redes socials tem temos de execução altos devido ao grande tamanho do grafo. Uma solução para reduzir os tempos de execução é usar sistemas paralelos na implementação destas medidas. Este trabalho discute a implementação de duas medidas de centralidade de nós, o PageRank e a betweenness centrality, numa plataforma CUDA. Também estuda a possibilidae de aplicar as estas métrcas a grafos grandes, dentro da GPU. Embora as GPUS tenha um hardware complexo, capaz de executar milhares de threads concurrentes, a memória disponível na GPU é limitativa no processamento de grafos grandes. A implementação destas medidas considera possiveis optimizações às kernels CUDA, que promovam distribuição de trabalho pelas threasd, um baixo número de threads paradas, bem como a total utilização dos recursos da GPU. Esquemas de partição de grafos e Streams CUDA são usados para permitir concorrentemente a execução de kernels e operações de transferencia de memória a partir do sistema anfitrião. Os resultados do PageRank provam que é possível processar grafos grandes numa GPU, usando particionamento e Streams CUDA. No PageRank foi atingindo um speedup de 9x para grafos de 7.1GB de tamanho. Para a betweenness centrality não foi encontrado um esquema de particionamento que permitisse grafos maiores que a memória da GPU, e também foi notado que para utilizar totalmente os recursos da GPU, as estruturas de dados auxiliares necessárias limitam severamente o tamanho dos grafos, para esta medida.
Grafos, GPU, CUDA, PageRank, Betweenness Centrality

Novembro 12, 2015, 18:0

Publicação

Obra sujeita a Direitos de Autor

Orientação

ORIENTADOR

Alexandre Paulo Lourenço Francisco

Departamento de Engenharia Informática (DEI)

Professor Auxiliar

ORIENTADOR

Luís Jorge Brás Monteiro Guerra e Silva

Departamento de Engenharia Informática (DEI)

Professor Auxiliar