High-performance Physics Simulations Using Multi-core CPUs and GPGPUs in a Volunteer Computing Context

Abstract

This paper presents two conceptually simple methods for parallelizing a Parallel Tempering Monte Carlo simulation in a distributed volunteer computing context, where computers belonging to the general public are used. The first method uses conventional multi-threading. The second method uses CUDA, a graphics card computing system. Parallel Tempering is described, and challenges such as parallel random number generation and mapping of Monte Carlo chains to different threads are explained. While conventional multi-threading on central processing units is well-established, GPGPU programming techniques and technologies are still developing and present several challenges, such as the effective use of a relatively large number of threads. Having multiple chains in Parallel Tempering allows parallelization in a manner that is similar to the serial algorithm. Volunteer computing introduces important constraints to high performance computing, and we show that both versions of the application are able to adapt themselves to the varying and unpredictable computing resources of volunteers’ computers, while leaving the machines responsive enough to use. We present experiments to show the scalable performance of these two approaches, and indicate that the efficiency of the methods increases with bigger problem sizes.

Get full access to this article

View all access options for this article.

References

Anderson, A.G. , Goddard, W.A. and Schröder, P. ( 2007). Quantum Monte Carlo on Graphical Processing Units. Comput. Phys. Commun. 177(3).

Anderson, D.P. ( 2004). BOINC: A system for public-resource computing and storage . In Proceedings of the Fifth IEEE/ ACM International Workshop on Grid Computing, Pittsburgh, pp. 365-372.

Anderson, J.B. ( 2007). Quantum Monte Carlo: Origins, Development, Applications . New York: Oxford University Press .

Berg, B.A. ( 2004). Markov Chain Monte Carlo Simulations and Their Statistical Analysis. Danvers: World Scientific Publishing Co.

Chapman, B. , Jost, G. and van der Pas, R. ( 2008). Using OpenMP: Portable Shared Memory Parallel Programming . The MIT Press.

Fischer, K.H. and Hertz, J.A. , (1993). Spin Glasses. Cambridge: Cambridge University Press.

Hamze, F. , Dickson, N. and Karimi, K. ( 2010). Robust Parameter Selection for Parallel Tempering. Int. J. Mod. Phys. C. 21(5): 603-615.

Hukushima, K. and Nemoto, K. ( 1996). Exchange Monte Carlo method and application to spin glass simulations. J. Phys. Soc. Jpn 65: 1604-1608.

Kirk, D. and Hwu, W. ( 2010). Programming Massively Parallel Processors: A Hands-on Approach. Burlington: Morgan Kaufmann Publishers.

10.

Matsumoto, M. and Nishimura, T. ( 1998). Mersenne Twister: A 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model. Comput. Simul. 8(1): 3-30.

11.

Neven, H. , Denchev, V.S. , Rose, G. and Macready, W.G. ( 2008). Training a binary classifier with the quantum adiabatic algorithm. In Neural Information Processing Systems (NIPS) Workshop on Optimization for Machine Learning. Vancouver.

12.

Robert C.P. , and Casella, G. ( 2004). Monte Carlo Statistical Methods. New York: Springer-Verlag.

13.

Rubinstein, R.Y. and Kroese, D.P. ( 2008). Simulation and the Monte Carlo Method. Hoboken: John Wiley & Sons.

14.

Wu, J. ( 1999). Distributed System Design. Boca Raton, FL: CRC Press LLC.

15.

Young, A.P. , Knysh, S. and Smelyanskiy, V.N. ( 2008). Size dependence of the minimum excitation gap in the quantum adiabatic algorithm. Phys. Rev. Lett. 101, 170503.