GPU Acceleration of Many Independent Mid-Sized Simulations on Graphs
Department of Computer Science, Virginia Tech, Blacksburg, VA, USA
The 2012 International Conference on Computer Graphics and Virtual Reality (CGVR’12), 2012
@inproceedings{arendt2012gpu,
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)},
year={2012}
}
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.
August 31, 2012 by hgpu
