FenixEdu™

Dissertação

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

Detalhes: 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.
Keywords: Grafos, GPU, CUDA, PageRank, Betweenness Centrality

Discussão: novembro 12, 2015, 18:0