Strict detailed balance poses difficulties in parallel implementations of Monte Carlo simulations. However, Markov chain Monte Carlo simulations can converge to the correct equilibrium distribution without strict detailed balance. We recently proposed [1, 2] a general Monte Carlo algorithm, which employs sequential updating with partial randomness to ensure correct sampling. Convergence analysis of simulation results on lattice systems indicate that the proposed algorithm improves statistical efficiency by reducing the autocorrelation time of the generated samples. The new algorithm, however, is not limited to discrete systems. It can also be applied to continuum systems, such as Lennard-Jones, in the grand canonical ensemble. The main advantages of the new algorithm are its simplicity, efficiency, and feasibility of parallel implementation. In this work, we consider the parallel implementation of our sequential updating algorithm. Any massively parallel Monte Carlo simulation based on spatial decomposition involves simultaneous moves of atoms/molecules on multiple CPUs. Technically, updating any molecule with interaction range beyond its own domain needs the most up-to-date information of its neighbor molecules from other computers. In parallel simulations on distributed/grid computers, communication between processors is a slow process due to the limit of network speed and traffic, comparing with local cache or memory operation. As the number of processors grows, the speed of simulation may drop dramatically due to the extra communication overhead. Thus, it is important for processors to compute independently most of the time, while synchronizing information between processors at a relatively low frequency. Several attempts have been made to parallelize Monte Carlo algorithms through decomposition of the system into a number of non-interacting domains. However, parallel Monte Carlo simulations based on spatial decomposition suffer from loss of precision due to the periodic switching of active domains. On the other hand, our algorithms are intrinsically sequential, and can be parallelized easily without compromising precision. Parallel implementation of our algorithms on lattice systems and Lennard-Jones fluids indicates that the same precision can be achieved by parallel Monte Carlo techniques with considerably less computing time.

[1] Ruichao Ren and G. Orkoulas, J. Chem. Phys. 124, 064109 (2006) [2] Ruichao Ren, CJ O'Keeffe and G. Orkoulas, Molecular Physics (submitted)