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 (23)
- Ising formulations of many NP problems
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
- Stochastic p-bits for Invertible Logic
- The promise of spintronics for unconventional computing
- Quantum Monte Carlo Calculations for a large number of bosons in a harmonic trap
- Demonstration of nanosecond operation in stochastic magnetic tunnel junctions
- Simple universal models capture all classical spin physics
- 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
- Prime factorization using quantum annealing and computational algebraic geometry
- Implementing Bayesian Networks with Embedded Stochastic MRAM
- Efficient CMOS Invertible Logic Using Stochastic Computing
- Autonomous Probabilistic Coprocessing with Petaflips per Second
- Janus II: a new generation application-driven computer for spin-system simulations
- Training and Classification using a Restricted Boltzmann Machine on the D-Wave 2000Q
- Spintronics-compatible approach to solving maximum satisfiability problems with probabilistic computing, invertible logic and parallel tempering
- Parallel Tempering Simulation of the three-dimensional Edwards-Anderson Model with Compact Asynchronous Multispin Coding on GPU
- Analog Coupled Oscillator Based Weighted Ising Machine
- 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
- Logically Synthesized, Hardware-Accelerated, Restricted Boltzmann Machines for Combinatorial Optimization and Integer Factorization
- Factoring semi-primes with (quantum) SAT-solvers
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