Source-linked AI summary
Optimized simulated annealing for Ising spin glasses
S. V. Isakov, I. N. Zintchenko, T. F. Rønnow, M. Troyer
TL;DR
Finding ground states of Ising spin glasses is computationally difficult, motivating efficient classical solvers and comparisons with specialized devices. The paper presents general, bipartite, and multi-spin-coded simulated-annealing implementations, achieving up to 50 spin flips per nanosecond on modern Intel CPUs while documenting replica correlations in one approach.
Problem
Finding Ising spin-glass ground states is NP-hard, and efficient classical implementations are therefore relevant for optimization problems that map to spin glasses.
Method
The paper develops generic, bipartite, and multi-spin-coded simulated-annealing implementations, including finite-range coupling codes for graphs with small maximum degree.
Results
50 spin flips per nanosecond are achieved on a single Intel processor using fast multi-spin and multi-threaded code.
Takeaways & Limitations
The software package offers efficient simulated-annealing implementations for sparse-graph Ising spin glasses and benchmarks them against specialized D-Wave devices.
Takeaways & Limitations
Using one random number for all 64 replicas in a multi-spin-coded word creates correlations between replicas.
Abstract
from arXiv · showhide
We present several efficient implementations of the simulated annealing algorithm for Ising spin glasses on sparse graphs. In particular, we provide a generic code for any choice of couplings, an optimized code for bipartite graphs, and highly optimized implementations using multi-spin coding for graphs with small maximum degree and discrete couplings with a finite range. The latter codes achieve up to 50 spin flips per nanosecond on modern Intel CPUs. We also compare the performance of the codes to that of the special purpose D-Wave devices built for solving such Ising spin glass problems.
PROGRAM SUMMARY
SimAn v1.0 is a parallelized C++ software package for finding Ising spin-glass ground states on sparse graphs using simulated annealing.
- SimAn v1.0 addresses Ising spin-glass ground states on sparse graphs with simulated annealing.The package is written in C++ and parallelized with OpenMP.
- Running times range from milliseconds to seconds on any PC running Linux, OS X, or UNIX.RAM and processor requirements are variable.
- The software is distributed under GPLv3 licensing provisions.
1. Introduction
The paper develops optimized simulated-annealing implementations for computationally difficult Ising spin-glass ground-state problems. It situates these implementations alongside parallel tempering and specialized D-Wave devices.
- 1. Introduction: Simulated annealing searches for low-energy configurations by cooling a Monte Carlo system, with repeated or sufficiently slow annealing potentially reaching the global minimum.
- 1. Introduction: The paper presents highly optimized simulated-annealing implementations for the Ising spin-glass problem.
- 1. Introduction: Finding Ising spin-glass ground states is NP-hard, and related problems such as constraint satisfaction and travelling salesman can be mapped to them in polynomial time.
- 1. Introduction: A prior study reported that a tested D-Wave device was 3600 times faster than the fastest compared classical code, while qualifying that result.
- 1. Introduction: Parallel tempering can outperform simulated annealing in some cases, including spin glasses with Gaussian-distributed couplings, and several presented optimizations also apply to it.
2. Optimisations
The paper improves simulated-annealing performance through implementation and computational optimizations, including caching energy changes, compile-time loop specialization, and faster random-number generation.
- 2. Optimisations: The optimization package provides efficient simulated-annealing implementations for modern CPUs, with performance improvements of orders of magnitude.
- 2. Optimisations: Caching each spin’s energy change avoids recomputation on rejected flips and updates cached values only when affected spins or neighbors change.This targets the dominant neighbor-traversal cost when average acceptance is around 15%.
- 2. Optimisations: Specifying the maximum neighbor count at compile time enables fixed-length loops and more effective compiler unrolling when degree variation is narrow.
- 2. Optimisations: Fast random-number generators are suitable because optimization quality is less sensitive to generator quality than high-accuracy physical-property simulations.
2.4. Deterministic traversal over lattice sites
The implementation can traverse lattice sites sequentially rather than selecting them randomly, reducing random-number generation and typically improving success rates despite violating detailed balance.
- 2.4. Deterministic traversal over lattice sites: Sequentially updating lattice sites reduces the number of generated random numbers and produces faster codes.
- 2.4. Deterministic traversal over lattice sites: Although deterministic traversal violates detailed balance, it typically yields better success rates.
2.5. Precomputing random numbers
The implementation reuses random numbers to reduce simulation cost, with integer comparisons providing an additional optimization for integer couplings. Cyclically shifting the precomputed sequence by a random offset reduces correlations between repetitions with minimal effort.
- Random acceptance thresholds can be precomputed as r = −1/β log u, replacing the Metropolis comparison with the cheaper test ∆E < r.For integer couplings, the comparison can use integer arithmetic instead of floating-point operations.
- Cyclically shifting the precomputed random-number array by a random offset for each sweep significantly reduces correlations between repetitions.A sweep is one attempted update per spin.
2.6. Optimisations for bipartite graphs
For bipartite graphs, the ground-state search can be reduced to optimizing one sub-lattice because spins in the other sub-lattice can always be aligned accordingly. With zero fields, this reduces updates to at most half the spins; fields can be handled by ancillary spins.
- Bipartite graphs permit ground-state optimization over only the A sub-lattice, with the B spins aligned accordingly.The construction assumes zero on-site fields and chooses N_A ≤ N_B.
- At most N/2 spins need updating because the smaller sub-lattice satisfies N_A ≤ N/2.
- Nonzero on-site fields are accommodated by adding two ancillary spins coupled to the two sub-lattices and strongly ferromagnetically coupled to each other.
2.7. Multi-spin coding
Multi-spin coding packs 64 replicas into one 64-bit word and updates them simultaneously using bitwise operations. The approach accelerates finite-range, discrete-coupling annealing but introduces replica correlations because one random number is shared across the packed replicas.
- Multi-spin coding represents spins as single bits, allowing 64 replicas to be updated simultaneously in 64-bit words.The implementations target finite coupling ranges and graphs with up to six nearest neighbours.
- Table 1 organizes the indices, energies, energy gains, and probabilities for a spin coupled to three neighbours with |J| = 1.
- The method replaces individual energy-change calculations with bitwise determination of finite energy-level indices and acceptance tests.For three-neighbour ±1 couplings, Boolean operations compute the interaction signs and the index used to select acceptance probabilities.
- Correlations: Using one random number for all 64 replicas creates correlations, and replicas that meet can subsequently follow the same path.The correlation ratio is near zero for uncorrelated replicas and equals one for fully correlated replicas.
- Correlations: The decorrelation strategy substantially reduces, but does not eliminate, correlations as the number of sweeps grows relative to system size.Figure 1 compares correlation ratios across quantiles for 126- and 503-spin depleted chimera graphs, with and without decorrelation.
- The second implementation determines the individual energies of 64 spins simultaneously and generates accepted flips in parallel.Generating Q accepted bits has average complexity O(log2(Q) + 2), and 64 bits require eight iterations on average.
3. Optimising annealing strategies
The paper optimizes annealing schedules and total runtime by balancing schedule parameters, repetition counts, and problem quantiles. For chimera instances, optimal single-repetition times vary with the target quantile.
- Annealing performance depends on optimizing both the schedule slope and its total length.
- βs = 0.1 and βe = 3 were effective initial and final inverse temperatures for ±1 couplings in problems up to 512 spins.The starting temperature should match the maximal single-spin-flip energy scale, while the final temperature should keep the state in the final minimum.
- Quantile optimization varies the balance between sweeps and repetitions because the required computational effort depends on the problem class and target success quantile.The framework uses S sweeps and R repetitions, with single-repetition ground-state probability w(S).
- 400 · N/f to 1000 · N/f are the optimal single-repetition annealing times observed for different quantiles on 1000 random chimera problems.The single-repetition time is ta = S · N/f, where S is the sweep count, N the system size, and f the attempted-update rate.
- Replacing log(0.01)/log(1 − w) with 1/w estimates the mean time to find the ground state, corresponding to 63% success when w is small.
4. Simulated annealing codes
The paper provides standalone simulated-annealing codes covering general and specialized graph and coupling structures. The implementations support configurable execution, parallel repetitions, and text-based lattice input and output.
- Multi-spin codes target lattices with one to six neighbours and ±1 couplings, with neighbour counts selected at compile time.The required neighbour count is chosen in ms config.h.
- Range-3 multi-spin code is included for up to six neighbours, while a code generator supports other finite integer coupling ranges and larger fixed neighbourhoods.
- Single-spin codes either support variable neighbour counts or use compile-time fixed loop lengths with a default maximum of six neighbours.Fixed-loop implementations can be faster in some circumstances.
- Independent annealing repetitions can be parallelized with OpenMP, and both single-threaded and multi-threaded code versions are provided.Parallel speedups can approach the number of threads when enough repetitions are used.
- The command-line interface specifies the lattice, schedule, sweep count, repetition count, and thread count.Lattice files contain couplings and local fields; output reports energy, occurrence count, success rate, and instance filename.
5. Benchmarking
The benchmarks evaluate optimized annealing codes on 503-spin chimera instances under single- and multi-threaded settings. The fastest multi-spin implementations achieve high throughput and short solution times, with results reported for both quantile and mean measures.
- Scaling: The multi-threaded multi-spin code performs best when the number of repetitions required to find the ground state is large enough.The benchmark tables report solution times for one-thread and 16-thread configurations.
- Performance: 50 spin flips per nanosecond is achieved by the fast multi-spin, multi-threaded code on a single Intel processor.This performance is reported for the benchmark codes on the Intel platform.
- Performance: Less than 153 ms is required to find solutions with 99% probability for range-1 instances without random fields on a 503-spin chimera graph.The corresponding bound with random fields is less than 27 ms.
- Mean solution times: The fastest code has a mean solution time of 8.2 ms for instances with fields and less than 40 ms for instances without fields.These are mean times for the 99% quantile benchmark.
Appendix A. The chimera graph
Chimera graphs are lattices of bipartite, fully connected unit cells arranged on a grid. The benchmark graph is based on an 8 × 8 K4,4 structure used by D-Wave Two, with missing vertices included to enable direct device comparisons.
- Graph structure: Each chimera unit cell is a bipartite fully connected graph Kc,c containing 2c vertices.The cells are distributed on an L × L grid.
- Benchmark graph: D-Wave Two implements a transverse-field Ising model on an 8 × 8 K4,4 graph, where nodes represent spins and edges represent couplings.The paper uses this graph for benchmarking its codes.
- Benchmark graph: Missing vertices are included in the benchmark graphs to allow direct comparisons with an actual D-Wave device.The missing vertices reflect fabrication issues.