SEARCH SESSIONS

Search All
 
Refine Results:
 
Year(s)

SOCIAL MEDIA

EMAIL SUBSCRIPTION

 
 

GTC On-Demand

Algorithms and Numerical Techniques
Presentation
Media
Graph Partitioning Using Bayesian Inference on GPU
Carl Yang (UC Davis)
We implement an efficient CUDA algorithm that solves the graph clustering problem using the stochastic block model for the first time on GPUs. The algorithm views the graph as a generative model called degree-corrected stochastic block model, and per ...Read More
We implement an efficient CUDA algorithm that solves the graph clustering problem using the stochastic block model for the first time on GPUs. The algorithm views the graph as a generative model called degree-corrected stochastic block model, and performs statistical inference to discover the graph partitions most likely to result in the graph. A greedy agglomerative heuristic is used with Markov Chain Monte Carlo (MCMC) to do Bayesian inference. A comparison is made with the baseline GraphChallenge implementation on synthetic datasets. Our implementation achieves speed-ups of 11.5x and 4.1x over single-threaded and multi-threaded OpenMP implementations on the CPU. We''ll provide empirical evidence that even though our method of parallelizing MCMC leads to worse convergence in terms of iteration number, we are able to harness the parallelism of the GPU to discover clusters at the same accuracy in less time.  Back
 
Keywords:
Algorithms and Numerical Techniques, GTC Silicon Valley 2018 - ID S8424
Streaming: