Massively Parallel Probabilistic Computing with Sparse Ising Machines
arXiv:2110.02481 · doi:10.1038/s41928-022-00774-2
Abstract
Inspired by the developments in quantum computing, building domain-specific classical hardware to solve computationally hard problems has received increasing attention. Here, by introducing systematic sparsification techniques, we demonstrate a massively parallel architecture: the sparse Ising Machine (sIM). Exploiting sparsity, sIM achieves ideal parallelism: its key figure of merit - flips per second - scales linearly with the number of probabilistic bits (p-bit) in the system. This makes sIM up to 6 orders of magnitude faster than a CPU implementing standard Gibbs sampling. Compared to optimized implementations in TPUs and GPUs, sIM delivers 5-18x speedup in sampling. In benchmark problems such as integer factorization, sIM can reliably factor semiprimes up to 32-bits, far larger than previous attempts from D-Wave and other probabilistic solvers. Strikingly, sIM beats competition-winning SAT solvers (by 4-700x in runtime to reach 95% accuracy) in solving 3SAT problems. Even when sampling is made inexact using faster clocks, sIM can find the correct ground state with further speedup. The problem encoding and sparsification techniques we introduce can be applied to other Ising Machines (classical and quantum) and the architecture we present can be used for scaling the demonstrated 5,000-10,000 p-bits to 1,000,000 or more through analog CMOS or nanodevices.
References in corpus (8)
- Demonstration of nanosecond operation in stochastic magnetic tunnel junctions
- Non-perturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins
- Multi-GPU Accelerated Multi-Spin Monte Carlo Simulations of the 2D Ising Model
- Efficient CMOS Invertible Logic Using Stochastic Computing
- Spintronics-compatible approach to solving maximum satisfiability problems with probabilistic computing, invertible logic and parallel tempering
- Randomized Algorithms for Scientific Computing (RASC)
- Simple and Near-Optimal Distributed Coloring for Sparse Graphs
- Nonequilibrium Monte Carlo for unfreezing variables in hard combinatorial optimization
Cited by in corpus (53)
- Quantum Annealing: An Overview
- A full-stack view of probabilistic computing with p-bits: devices, architectures and algorithms
- Roadmap for Unconventional Computing with Nanotechnology
- CMOS + stochastic nanomagnets: heterogeneous computers for probabilistic inference and learning
- Parallel Quantum Annealing
- Training Deep Boltzmann Networks with Sparse Ising Machines
- Biasing the quantum vacuum to control macroscopic probability distributions
- Experimental demonstration of an integrated on-chip p-bit core utilizing stochastic Magnetic Tunnel Junctions and 2D-MoS2 FETs
- Spintronics-compatible approach to solving maximum satisfiability problems with probabilistic computing, invertible logic and parallel tempering
- Efficient Probabilistic Computing with Stochastic Perovskite Nickelates
- Evaluating spintronics-compatible implementations of Ising machines
- Accelerated Quantum Monte Carlo with Probabilistic Computers
- All-to-all reconfigurability with sparse and higher-order Ising machines
- CMOS-compatible Ising and Potts Annealing Using Single Photon Avalanche Diodes
- Integrated probabilistic computer using voltage-controlled magnetic tunnel junctions as its entropy source
- Probabilistic-Bits based on Ferroelectric Field-Effect Transistors for Stochastic Computing
- Real-time Trading System based on Selections of Potentially Profitable, Uncorrelated, and Balanced Stocks by NP-hard Combinatorial Optimization
- Enhanced Convergence in p-bit Based Simulated Annealing with Partial Deactivation for Large-Scale Combinatorial Optimization Problems
- Energy landscapes of combinatorial optimization in Ising machines
- Solving Boolean satisfiability problems with resistive content addressable memories
- Correlation-diversified portfolio construction by finding maximum independent set in large-scale market graph
- Efficient and Scalable Architecture for Multiple-chip Implementation of Simulated Bifurcation Machines
- Pairs-trading System using Quantum-inspired Combinatorial Optimization Accelerator for Optimal Path Search in Market Graphs
- Double-Free-Layer Stochastic Magnetic Tunnel Junctions with Synthetic Antiferromagnets
- Physics-inspired Ising Computing with Ring Oscillator Activated p-bits
- Noise-augmented Chaotic Ising Machines for Combinatorial Optimization and Sampling
- Scalable Connectivity for Ising Machines: Dense to Sparse
- Pushing the Boundary of Quantum Advantage in Hard Combinatorial Optimization with Probabilistic Computers
- GPU-accelerated simulated annealing based on p-bits with real-world device-variability modeling
- Markov Chain Monte Carlo for Koopman-based Optimal Control: Technical Report
- Two-dimensional Parallel Tempering for Constrained Optimization
- Memristive Ising Circuits
- pc-COP: An Efficient and Configurable 2048-p-Bit Fully-Connected Probabilistic Computing Accelerator for Combinatorial Optimization
- Electrically Tunable Picosecond-scale Octupole Fluctuations in Chiral Antiferromagnets
- The First Hardware Demonstration of a Universal Programmable RRAM-based Probabilistic Computer for Molecular Docking
- Machine Learning Quantum Systems with Magnetic p-bits
- Lagrange Oscillatory Neural Networks for Constraint Satisfaction and Optimization
- Edge-of-chaos enhanced quantum-inspired algorithm for combinatorial optimization
- Superparamagnetic and Stochastic-Write Magnetic Tunnel Junctions for High-Speed True Random Number Generation in Advanced Computing
- Many-body computing on Field Programmable Gate Arrays
- Application of Probabilistic-bit in Precision Measurements
- Parallel Ising Annealer via Gradient-based Hamiltonian Monte Carlo
- Enhancing In-vehicle Multiple Object Tracking Systems with Embeddable Ising Machines
- Generalized Probabilistic Approximate Optimization Algorithm
- Ground-State Probabilistic Logic with the Simplest Binary Energy Landscape for Probabilistic Computing
- In-plane dominant anisotropy stochastic magnetic tunnel junction for probabilistic computing: A Fokker-Planck study
- Self-Adaptive Ising Machines for Constrained Optimization
- Metrics for spin-based computing
- Predicting sampling advantage of stochastic Ising Machines for Quantum Simulations
- Thermodynamic significance of QUBO encoding on quantum annealers
- Energy-Efficient p-Bit-Based Fully-Connected Quantum-Inspired Simulated Annealer with Dual BRAM Architecture
- An improved update rule for probabilistic computers
- Machine Learning-assisted High-speed Combinatorial Optimization with Ising Machines for Dynamically Changing Problems