Microcanonical simulated annealing: Massively parallel Monte Carlo simulations with sporadic random-number generation

This contribution presents a general microchannel simulated annealing procedure (MicSA) that drastically reduces the computational cost of random number generation in massively parallel Monte Carlo simulations, and demonstrates its effectiveness and dynamic equivalence to standard methods through rigorous benchmarks on three-dimensional Ising spin glasses using GPUs and the Janus-II supercomputer.

The Gist

Imagine you are trying to find the lowest point in a vast, foggy mountain range. This is a classic problem in physics and computer science: searching for the "best" solution (the state of lowest energy) among millions of possibilities. To do this, scientists use a method called Simulated Annealing, which is comparable to shaking a box of balls to help them settle into the deepest hole.

However, there is a catch. The standard method for shaking the box (a Monte Carlo simulation) requires a massive amount of random numbers. Think of random numbers as the "dice rolls" that decide whether a ball moves or stays in place.

The Problem: The Dice-Roll Bottleneck

In modern supercomputers, especially those with thousands of processors working simultaneously (massively parallel), the computer spends so much time rolling these digital dice that it forgets to actually move the balls. It is like in an assembly line factory where workers spend 90% of their time only rolling dice and only 10% of their time building the product. The faster computers become, the more this "dice rolling" becomes the slowest part of the entire process, wasting enormous amounts of computing power.

The Solution: The "Microcanonical" Trick

The authors of this paper propose a clever new way to perform these simulations, called Microcanonical Simulated Annealing (MicSA).

Here is the analogy they use to explain it:
Imagine the balls (the spins) are connected to small energy batteries called "demons" or "walkers".

• The old way: Every time you want to move a ball, you roll a new die to decide if this is allowed.
• The new way (MicSA): You do not roll a die at all. Instead, you check the battery. If the ball moves and loses energy, that energy is immediately transferred to the battery. If the battery has enough charge, the movement takes place. If not, it stays as is.

Since the total energy of the system (balls + batteries) remains constant, you do not need to roll a die to check if the movement is "randomly" allowed. You simply check the math. This means you can move millions of balls simultaneously without stopping to roll dice.

The "Refresh" Mechanism

There is one problem: If you never roll a die, the batteries could become too full or too empty, and the system could get stuck in a strange state. To fix this, the authors use a very specific schedule:

• They let the system run for a long time without rolling dice.
• Then, very rarely (like once every few thousand steps), they "refresh" the batteries. They discard the old battery states and generate a fresh set of random numbers just for the batteries.
• Since this happens so rarely, the computer spends almost 100% of its time moving balls and almost 0% of its time rolling dice.

The Results: Does it work?

The team tested this new method on a very difficult problem: a 3D spin glass (a complex magnetic material notorious for being hard to simulate). They compared their new "dice-free" method with the standard "dice-rolling" method using two different supercomputers:

1. Janus II: A supercomputer built specifically for this problem.
2. GPUs: Standard graphics cards (like those in gaming computers) running their new code.

The findings:

• Accuracy: When the system settles (reaches equilibrium), both methods yield exactly the same results.
• Speed: The new method is incredibly fast on standard GPUs because it does not stall due to the generation of random numbers.
• Time rescaling: The only difference is that the "dice-free" method moves slightly slower or faster in terms of "steps." However, if you simply adjust the clock (rescale the time), the two methods match perfectly. It is like watching two runners; one runs in 10-second intervals and the other in 11-second intervals, but if you adjust the stopwatch, they run at the same pace.

Why this matters

The paper claims that this method allows scientists to run massive simulations on standard off-the-shelf hardware (like the GPUs in your gaming PC), which was previously only possible on expensive, custom-built supercomputers. It solves the "dice-rolling" bottleneck and makes it possible to simulate complex systems much more efficiently without having to invent new hardware.

In short: They found a way to simulate complex physical problems by replacing constant random dice rolls with an intelligent energy transfer system, enabling standard computers to perform work that previously required specialized supercomputers.

Technical Summary

Technical Conclusion: Microcanonical Simulated Annealing (MicSA)

Problem Statement
Monte Carlo simulations are indispensable for investigating complex systems such as spin glasses and for solving combinatorial optimization problems. However, a critical bottleneck in massively parallel implementations (e.g., on GPUs or custom hardware platforms) is the generation of high-quality pseudo-random numbers. As hardware complexity increases, the proportion of computation time dedicated to random number generation grows, becoming prohibitive for specialized platforms. The authors identify a conflict: parallel updates require vast streams of independent random numbers, yet their generation is computationally intensive.

Methodology
The authors propose Microcanonical Simulated Annealing (MicSA), a formalism that is extremely frugal in its consumption of random numbers while remaining fully compatible with massively parallel computation. The method is tested on the three-dimensional Edwards-Anderson Ising spin glass model.

The core of the algorithm comprises the following components:

1. Extended Configuration Space: The system is extended by auxiliary degrees of freedom, referred to as "demons" or "walkers" ($n_{x,\alpha}$), associated with each spin. The total Hamiltonian is given by $H = H_{EA} + H_{aux}$, where $H_{aux}$ is the sum of these auxiliary variables.
2. Creutz-like Steps: Instead of integrating out the auxiliary variables (which would destroy the separability required for parallel updates), the authors adapt the Creutz algorithm. A spin flip is proposed, and the change in spin energy ($\Delta H_{EA}$) is compensated by updating an auxiliary variable ($n_{x,\alpha} \to n_{x,\alpha} - \Delta H_{EA}$). This step requires no random numbers and preserves the total energy of the extended system.
3. Separability and Parallelism: To enable parallel updates, the lattice is decomposed into even and odd sublattices (checkerboard decomposition). The algorithm updates all spins of a given parity simultaneously.
4. Demons vs. Walkers:
   • Demons: Auxiliary variables bound to a specific lattice site.
   • Walkers: Auxiliary variables allowed to move through the lattice. The authors implement a "walk" procedure where walkers exchange values between neighboring sites in a specific pattern (e.g., forward/backward along the X-, Y-, Z-axes) to avoid local conservation laws that lead to dynamic slowing down.
5. Microcanonical Simulated Annealing: To achieve the canonical equilibrium distribution, the system must be cooled. The algorithm "refreshes" the configuration of the demons/walkers at specific time intervals by drawing new values from their canonical distribution (Equation 11).
   • Crucially, the refresh schedule is logarithmic (at times $t_s = 2^s$). This minimizes the frequency of random number generation, as the energy relaxation of spin glasses is slow (power-law or logarithmic).
   • The refresh effectively lowers the total energy of the system, mimicking the cooling process of standard simulated annealing, but acts exclusively on the auxiliary variables.

Main Contributions

• Algorithmic Innovation: A general formalism that reduces random number generation to a sporadic event (logarithmic in time) while preserving the statistical properties of canonical simulations.
• Adaptation to Massively Parallel Architectures: The method is explicitly designed for parallel architectures (GPUs), utilizes multi-spin coding, and avoids the non-linear coupling problems encountered in earlier microcanonical ensembles (e.g., by Lustig).
• Dynamic Scalability: The authors demonstrate that the non-equilibrium dynamics of MicSA can be mapped onto standard canonical Metropolis dynamics via a simple time-scaling factor ($k^*$).

Results
The authors compared MicSA simulations (performed on Nvidia GPUs) with high-precision standard Metropolis simulations (performed on the custom supercomputer Janus II) for the 3D Ising spin glass.

• Equivalence of Dynamics: In the paramagnetic phase ($T > T_c$) and the spin glass phase ($T < T_c$), the energy relaxation $e(t)$ and the coherence length $\xi_{12}(t)$ obtained via MicSA are indistinguishable from canonical results after applying a time scaling $t_{plot} = k^* \times t_{MicSA}$.
• Scaling Factors: The optimal scaling factor $k^*$ depends on the number of walkers/demons per spin ($\gamma$). For the "walker" variant with $\gamma=6$, $k^* \approx 6.034$, which is nearly identical to the number of updates per spin per time step. This suggests that one MicSA step corresponds to $\gamma$ Metropolis sweeps without requiring random numbers.
• Performance: On an Nvidia H100 GPU, the MicSA algorithm (including the walk procedure) achieved a spin update time of approximately 0.4 picoseconds per spin. This is significantly faster than the random number generation step in the standard Metropolis method (which accounted for about 72% of the time in the standard algorithm).
• Equilibrium Validation: In Appendix C, the authors showed that MicSA combined with Parallel Tempering successfully reproduces equilibrium values for small systems with Gaussian couplings, confirming its validity for equilibrium studies as well.

Significance and Claims
The authors claim that MicSA offers a "widely applicable" solution to the random number generation bottleneck in large-scale Monte Carlo simulations.

• Efficiency: By reducing the demand for random numbers by orders of magnitude (via logarithmic refreshing), the method makes massively parallel simulations on high-end GPUs and potential ASICs (Application Specific Integrated Circuits) significantly more efficient.
• Universality: The method is not limited to spin glasses; the authors argue it is applicable to any problem where the cost function (energy) changes discretely or can be handled via auxiliary variables, including combinatorial optimization.
• Validation: The authors emphasize that the property of dynamic scaling holds across various temperatures and algorithmic variants (demons vs. walkers), confirming that MicSA belongs to the same dynamic universality class as standard Metropolis dynamics.

The authors remain modest regarding the scope of application, noting that for very small systems or problems with continuously distributed energy changes (e.g., Gaussian couplings), specific adaptations (continuous walkers) are required, and the optimal refresh rate may vary depending on the specific problem and hardware. They do not claim that MicSA solves the NP-completeness of spin glasses, but rather offer a more efficient computational tool for their investigation.