Massively parallel Monte Carlo for many-particle simulations on GPUs. (English) Zbl 1349.65005
Summary: Current trends in parallel processors call for the design of efficient massively parallel algorithms for scientific computing. Parallel algorithms for Monte Carlo simulations of thermodynamic ensembles of particles have received little attention because of the inherent serial nature of the statistical sampling. In this paper, we present a massively parallel method that obeys detailed balance and implement it for a system of hard disks on the GPU. We reproduce results of serial high-precision Monte Carlo runs to verify the method. This is a good test case because the hard disk equation of state over the range where the liquid transforms into the solid is particularly sensitive to small deviations away from the balance conditions. On a Tesla K20, our GPU implementation executes over one billion trial moves per second, which is 148 times faster than on a single Intel Xeon E5540 CPU core, enables 27 times better performance per dollar, and cuts energy usage by a factor of 13. With this improved performance we are able to calculate the equation of state for systems of up to one million hard disks. These large system sizes are required in order to probe the nature of the melting transition, which has been debated for the last forty years. In this paper we present the details of our computational method, and discuss the thermodynamics of hard disks separately in a companion paper.
MSC:
| 65C05 | Monte Carlo methods |
| 65Y05 | Parallel numerical computation |
| 65Y10 | Numerical algorithms for specific classes of architectures |
References:
| [1] | Asanovic, K.; Bodik, R.; Catanzaro, B. C.; Gebis, J. J.; Husbands, P.; Keutzer, K.; Patterson, D. A.; Plishker, W. L.; Shalf, J.; Williams, S. W.; Yelick, K. A., The landscape of parallel computing research: a view from Berkeley (2006), EECS Department, University of California: EECS Department, University of California Berkeley, Technical Report UCB/EECS-2006-183 |
| [2] | Stone, J. E.; Hardy, D. J.; Ufimtsev, I. S.; Schulten, K., GPU-accelerated molecular modeling coming of age, Journal of Molecular Graphics & Modelling, 29, 116-125 (2010) |
| [3] | Anderson, J. A.; Lorenz, C. D.; Travesset, A., General purpose molecular dynamics simulations fully implemented on graphics processing units, Journal of Computational Physics, 227, 5342-5359 (2008) · Zbl 1148.81301 |
| [4] | HOOMD-blue (2012) |
| [5] | Brown, W. M.; Wang, P.; Plimpton, S. J.; Tharrington, A. N., Implementing molecular dynamics on hybrid high performance computers - short range forces, Computer Physics Communications, 182, 898-911 (2011) · Zbl 1221.82008 |
| [6] | Götz, A. W.; Williamson, M. J.; Xu, D.; Poole, D.; Le Grand, S.; Walker, R. C., Routine microsecond molecular dynamics simulations with AMBER on GPUs. 1. Generalized born, Journal of Chemical Theory and Computation, 8, 1542-1555 (2012) |
| [7] | Le Grand, S.; Götz, A. W.; Walker, R. C., SPFP: Speed without compromise — A mixed precision model for GPU accelerated molecular dynamics simulations, Computer Physics Communications, 184, 2, 374-380 (2013) |
| [8] | Stone, J. E.; Phillips, J. C.; Freddolino, P. L.; Hardy, D. J.; Trabuco, L. G.; Schulten, K., Accelerating molecular modeling applications with graphics processors, Journal of Computational Chemistry, 28, 2618-2640 (2007) |
| [9] | Eastman, P.; Pande, V. S., Efficient nonbonded interactions for molecular dynamics on a graphics processing unit, Journal of Computational Chemistry, 31, 1268-1272 (2010) |
| [10] | Ganesan, N.; Bauer, B. A.; Lucas, T. R.; Patel, S.; Taufer, M., Structural, dynamic, and electrostatic properties of fully hydrated DMPC bilayers from molecular dynamics simulations accelerated with graphical processing units (GPUs), Journal of Computational Chemistry, 32, 2958-2973 (2011) |
| [11] | Colberg, P. H.; Höfling, F., Highly accelerated simulations of glassy dynamics using GPUs: Caveats on limited floating-point precision, Computer Physics Communications, 182, 1120-1129 (2011) |
| [12] | Rapaport, D. C., Enhanced molecular dynamics performance with a programmable graphics processor, Computer Physics Communications, 182, 926-934 (2011) · Zbl 1221.82013 |
| [13] | GROMACS (2013) |
| [14] | ACEMD (2013) |
| [15] | Swendsen, R.; Wang, J.-s., Nonuniversal critical dynamics in Monte Carlo simulations, Physical Review Letters, 58, 86-88 (1987) |
| [16] | Liu, J.; Luijten, E., Rejection-free geometric cluster algorithm for complex fluids, Physical Review Letters, 92, 1-4 (2004) |
| [17] | Whitelam, S.; Geissler, P. L., Avoiding unphysical kinetic traps in Monte Carlo simulations of strongly attractive particles, Journal of Chemical Physics, 127, 154101 (2007) |
| [18] | Bernard, E.; Krauth, W.; Wilson, D., Event-chain Monte Carlo algorithms for hard-sphere systems, Physical Review E, 80, 5-9 (2009) |
| [19] | Pawley, G.; Bowler, K.; Kenway, R.; Wallace, D., Concurrency and parallelism in MC and MD simulations in physics, Computer Physics Communications, 37, 251-260 (1985) |
| [20] | Ren, R.; Orkoulas, G., Acceleration of Markov chain Monte Carlo simulations through sequential updating, Journal of Chemical Physics, 124, 64109 (2006) |
| [21] | Preis, T.; Virnau, P.; Paul, W.; Schneider, J. J., GPU accelerated Monte Carlo simulation of the 2D and 3D Ising model, Journal of Computational Physics, 228, 4468-4477 (2009) · Zbl 1167.82347 |
| [22] | Levy, T.; Cohen, G.; Rabani, E., Simulating lattice spin models on graphics processing units, Journal of Chemical Theory and Computation, 6, 3293-3301 (2010) |
| [23] | Heffelfinger, G. S.; Lewitt, M. E., A comparison between two massively parallel algorithms for Monte Carlo computer simulation: An investigation in the grand canonical ensemble, Journal of Computational Chemistry, 17, 250-265 (1996) |
| [24] | Uhlherr, A.; Leak, S. J.; Adam, N. E.; Nyberg, P. E.; Doxastakis, M.; Mavrantzas, V. G.; Theodorou, D. N., Large scale atomistic polymer simulations using Monte Carlo methods for parallel vector processors, Computer Physics Communications, 144, 1-22 (2002) · Zbl 0987.82506 |
| [25] | Ren, R.; Orkoulas, G., Parallel Markov chain Monte Carlo simulations, Journal of Chemical Physics, 126, 211102 (2007) |
| [26] | OʼKeeffe, C. J.; Orkoulas, G., Parallel canonical Monte Carlo simulations through sequential updating of particles, Journal of Chemical Physics, 130, 134109 (2009) |
| [27] | Sadigh, B.; Erhart, P.; Stukowski, A.; Caro, A.; Martinez, E.; Zepeda-Ruiz, L., Scalable parallel Monte Carlo algorithm for atomistic simulations of precipitation in alloys, Physical Review B, 85, 1-11 (2012) |
| [28] | Lubachevsky, B. D., Efficient parallel simulations of asynchronous cellular arrays, Complex Systems, 1, 1099-1123 (1987) · Zbl 0654.68057 |
| [29] | Korniss, G.; Novotny, M.; Rikvold, P., Parallelization of a dynamic Monte Carlo algorithm: a partially rejection-free conservative approach, Journal of Computational Physics, 153, 488-508 (1999) · Zbl 0979.82043 |
| [30] | Martínez, E.; Marian, J.; Kalos, M.; Perlado, J., Synchronous parallel kinetic Monte Carlo for continuum diffusion-reaction systems, Journal of Computational Physics, 227, 3804-3823 (2008) · Zbl 1139.65003 |
| [31] | Arampatzis, G.; Katsoulakis, M. A.; Plecháč, P.; Taufer, M.; Xu, L., Hierarchical fractional-step approximations and parallel kinetic Monte Carlo algorithms, Journal of Computational Physics, 231, 7795-7814 (2012) · Zbl 1259.82110 |
| [32] | Esselink, K.; Loyens, L.; Smit, B., Parallel Monte Carlo simulations, Physical Review E, 51, 1560-1568 (1995) |
| [33] | Loyens, L.; Smit, B.; Esselink, K., Parallel Gibbs-ensemble simulations, Molecular Physics, 86, 171-183 (1995) |
| [34] | Bernard, E.; Krauth, W., Two-step melting in two dimensions: first-order liquid-hexatic transition, Physical Review Letters, 107, 1-4 (2011) |
| [35] | Durstenfeld, R., Algorithm 235: random permutation, Communications of the ACM, 7, 420 (1964) |
| [37] | Metropolis, N.; Rosenbluth, A. W.; Rosenbluth, M. N.; Teller, A. H.; Teller, E., Equation of state calculations by fast computing machines, Journal of Chemical Physics, 21, 1087 (1953) · Zbl 1431.65006 |
| [38] | Manousiouthakis, V. I.; Deem, M. W., Strict detailed balance is unnecessary in Monte Carlo simulation, Journal of Chemical Physics, 110, 2753 (1999) |
| [40] | Kirk, D. B.; Hwu, W.-m. W., Programming Massively Parallel Processors: A Hands-on Approach (2010), Morgan Kaufmann |
| [41] | Farber, R., CUDA Application Design and Development (2011), Morgan Kaufmann |
| [42] | Sanders, J., CUDA by Example (2010), Addison-Wesley Professional |
| [44] | Phillips, C. L.; Anderson, J. A.; Glotzer, S. C., Pseudo-random number generation for Brownian dynamics and dissipative particle dynamics simulations on GPU devices, Journal of Computational Physics, 230, 7191-7201 (2011) · Zbl 1231.82005 |
| [45] | Engel, M.; Anderson, J. A.; Glotzer, S. C.; Isobe, M.; Bernard, E. P.; Krauth, W., Hard-disk equation of state: First-order liquid-hexatic transition in two dimensions with three simulation methods, Physical Review E, 87, 042134 (2013) |
| [46] | Alder, B.; Wainwright, T., Phase transition in elastic disks, Physical Review, 127, 359-361 (1962) |
| [47] | Lee, J.; Strandburg, K., First-order melting transition of the hard-disk system, Physical Review B, 46, 11190-11193 (1992) |
| [48] | Zollweg, J.; Chester, G., Melting in two dimensions, Physical Review B, 46, 11186-11189 (1992) |
| [49] | Weber, H.; Marx, D.; Binder, K., Melting transition in two dimensions: A finite-size scaling analysis of bond-orientational order in hard disks, Physical Review B, 51, 14636-14651 (1995) |
| [50] | Jaster, A., Computer simulations of the two-dimensional melting transition using hard disks, Physical Review E, 59, 2594-2602 (1999) |
| [51] | Mak, C., Large-scale simulations of the two-dimensional melting of hard disks, Physical Review E, 73, 1-4 (2006) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
