Parallelizable Multi-Worm Algorithm
Kawashima Group
Massively parallel computations open the door to many otherwise intractable problems in condensed matter physics, in particular, quantum many-body problems. Recent high-performance computers, symbolized by K-computer in Kobe, rely on a large number, as many as a million, of processors (or more precisely "cores"). Therefore, we must split the computational tasks into many bits and assigning each to one of the numerous processors. This is by no means a trivial thing to do. Often we must significantly alter algorithms to split the task in an efficient way. In other words, we must develop new parallelizable algorithms. The quantum Monte Carlo method with the worm update algorithm [1, 2] has a broad range of applicability and is one of the standard tools to treat quantum many-body problems. However, in this algorithm, update of configurations is realized via the motion of a single-point object in the whole space-time (or the lattice), making it hard to split the task.
Fig. 1. Worms and worldlines in PMWA. The yellow dashed lines are the domain boundaries.
Fig. 2. (a) The order parameter of the Bose-Einstein condensate as a function of η;. (b) The standard error as a function of the number of domains with the fixed number of Monte Carlo steps. (c) The standard error as a function of the number of domains with the computational time (wall-clock time) being fixed.
Based on the directed-loop algorithm [2], one of the variants of the worm algorithm, we proposed a parallelizable worm algorithm, which we named the parallelizable multi-worm algorithm (PMWA). In PMWA, multiple worms are introduced by an artificial source field η and the space-time is decomposed into many domains, as illustrated in Fig. 1. Each domain is assined to a processor and typically contains 10-100 worms. We estimate physical observables by extrapolation to the η = 0 imit. Introducing multiple worms requires a different procedure from the conventional worm algorithm so as to satisfy the detailed balance condition. The migration of the worms over the domain boundaries is effectively realized through communications between domains so that the ergodicity condition is satisfied. The PMWA is applicable to the soft-core Bosons and the quantum spins as the conventional worm algorithm.
We applied the PMWA to the extended Hard-core Bose-Hubbard model on square lattice defined by
where bi is the annihilation operator at site i, t is the hopping energy, V is the nearest neighbor repulsion, and μ is the chemical potential. We established the extrapolation procedure to obtain physical quantities in the η = 0 limit. Then, we confirmed that the extrapolated PMWA result agreed with the result obtained by the conventional DLA algorithm. Figure 2(a) shows the order parameter of the Bose-Einstein condensate Q ≡ 〈b〉 as a function of η. Here we carried out simulations of the size of L × L × β = 10,240×10,240×16 using 3,200 processing cores, where L is the system's linear dimension and β is the inverse temperature. This size exceeds the maximum reachable size of the conventional worm algorithm. To evaluate the parallelization efficiency of the algorithm, we measured the standard error as a function of the number of domains N. We found a very weak N-dependence for the relaxation time in the simulation with fixed number of the Monte Carlo steps (Fig. 2(b)). In addition, in comparison with the conventional DLA results, PMWA results show better accuracy in fixed wall-clock time with N>8 (Fig. 2(c)), and the difference increases as the system becomes larger.
References
- [1] N. Prokof'ev, B. Svistunov, and I. Tupitsyn, Sov. Phys. JETP 87, 310 (1998) etc.
- [2] O. F. Syljuasen and A. W. Sandvik, Phys. Rev. E 66, 046701 (2012).
- [3] A. Masaki-Kato, T. Suzuki, K. Harada, S. Todo, and N. Kawashima, arXiv:1307.0328 (2013), to be published in Phys. Rev. Lett. (2014).