GPU Acceleration of Many Independent Mid-Sized Simulations on Graphs

Dustin Arendt
Department of Computer Science, Virginia Tech, Blacksburg, VA, USA
The 2012 International Conference on Computer Graphics and Virtual Reality (CGVR’12), 2012


   title={GPU Acceleration of Many Independent Mid-Sized Simulations on Graphs},

   author={Arendt, D. and Cao, Y.},

   booktitle={4th Cellular Automata, Theory and Applications Workshop (A-CSC’12)},



Download Download (PDF)   View View   Source Source   



Many GPU parallelizations exist to speedup simulation of complex systems, but these approaches see less benefit when the simulation is not large. Simulation of many independent complex systems is useful for Monte Carlo sampling or for exploring the behavior of many different models at once. We present and evaluate an algorithm for simulating many mid-sized dimer automata (e.g., having tens of thousands of vertices) on the GPU. Our algorithm has, in the best case, a throughput of over 300 million edge updates per second, and a speedup of over 37 on modest GPU hardware. Dimer automata can also be used to design and implement useful computations on graphs. As a test case, we implement a solution to the all pairs shortest path problem using dimer automata and our GPU algorithm, but find that the structure of the graph has a significant effect on the efficiency of the algorithm.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: