An official website of the United States government
Probabilistic spin logic (PSL) has recently been proposed as a novel computing paradigm that leverages random thermal fluctuations of interacting bodies in a system rather than deterministic switching of binary bits. A PSL circuit is an interconnected network of thermally unstable units called probabilistic bits (p-bits), whose output randomly fluctuates between bits 0 and 1. While the fluctuations generated by p-bits are thermally driven, and therefore, inherently stochastic, the output probability is tunable with an external source. Therefore, information is encoded through probabilities of various configuration of states in the network. Recent studies have shown that these systems can efficiently solve various types of combinatorial optimization problems and Bayesian inference problems that modern computers are unfit for. Previous experimental studies have demonstrated that a single magnetic tunnel junctions (MTJ) designed to be thermally unstable can operate tunable random number generator making it an ideal hardware solution for p-bits. Most proposals for designing an MTJ to operate as a p-bit involve patterning the MTJ as a circular nano-pillar to make the device thermally unstable and then use spin transfer torque (STT) as a tuning mechanism. However, the practical realization of such devices is very challenging since the fluctuation rate of these devices are very sensitive to any device variations or defects caused during fabrication. Despite this challenge, MTJs are still the most promising hardware solution for p-bits because MTJs are very unique in that they can be tuned by multiple other mechanisms such spin orbit torque, magneto-electric coupling, and voltage-controlled exchange coupling. Furthermore, multiple forces can be used simultaneously to drive stochastic switching signals in MTJs. This means there are a large number of methods to tune, or termed as bias, MTJs that can be implemented in p-bit circuits that can alleviate the current challenges of conventional STT driven p-bits. This article serves as a review of all of the different methods that have been proposed to drive random fluctuations in MTJs to operate as a probabilistic bit. Not only will we review the single-biasing mechanisms, but we will also review all the proposed dual-biasing methods, where two independent mechanisms are employed simultaneously. These dual-biasing methods have been shown to have certain advantages such as alleviating the negative effects of device variations and some biasing combinations have a unique capability called ‘two-degrees of tunability’, which increases the information capacity in the signals generated.
more »
« less
Ising-FPGA: A Spintronics-based Reconfigurable Ising Model Solver
The Ising model has been explored as a framework for modeling NP-hard problems, with several diverse systems proposed to solve it. The Magnetic Tunnel Junction– (MTJ) based Magnetic RAM is capable of replacing CMOS in memory chips. In this article, we propose the use of MTJs for representing the units of an Ising model and leveraging its intrinsic physics for finding the ground state of the system through annealing. We design the structure of a basic MTJ-based Ising cell capable of performing the functions essential to an Ising solver. The hardware overhead of the Ising model is analyzed, and a technique to use the basic Ising cell for scaling to large problems is described. We then go on to propose Ising-FPGA, a parallel and reconfigurable architecture that can be used to map a large class of NP-hard problems, and show how a standard Place and Route tool can be utilized to program the Ising-FPGA. The effects of this hardware platform on our proposed design are characterized and methods to overcome these effects are prescribed. We discuss how three representative NP-hard problems can be mapped to the Ising model. Further, we suggest ways to simplify these problems to reduce the use of hardware and analyze the impact of these simplifications on the quality of solutions. Simulation results show the effectiveness of MTJs as Ising units by producing solutions close/comparable to the optimum and demonstrate that our design methodology holds the capability to account for the effects of the hardware.
more »
« less
- Award ID(s):
- 1642424
- PAR ID:
- 10216396
- Date Published:
- Journal Name:
- ACM Transactions on Design Automation of Electronic Systems
- Volume:
- 26
- Issue:
- 1
- ISSN:
- 1084-4309
- Page Range / eLocation ID:
- 1 to 27
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract A prominent approach to solving combinatorial optimization problems on parallel hardware is Ising machines, i.e., hardware implementations of networks of interacting binary spin variables. Most Ising machines leverage second-order interactions although important classes of optimization problems, such as satisfiability problems, map more seamlessly to Ising networks with higher-order interactions. Here, we demonstrate that higher-order Ising machines can solve satisfiability problems more resource-efficiently in terms of the number of spin variables and their connections when compared to traditional second-order Ising machines. Further, our results show on a benchmark dataset of Booleank-satisfiability problems that higher-order Ising machines implemented with coupled oscillators rapidly find solutions that are better than second-order Ising machines, thus, improving the current state-of-the-art for Ising machines.more » « less
-
Solving computationally hard problems using conventional computing architectures is often slow and energetically inefficient. Quantum computing may help with these challenges, but it is still in the early stages of development. A quantum-inspired alternative is to build domain-specific architectures with classical hardware. Here we report a sparse Ising machine that achieves massive parallelism where the flips per second—the key figure of merit—scales linearly with the number of probabilistic bits. Our sparse Ising machine architecture, prototyped on a field-programmable gate array, is up to six orders of magnitude faster than standard Gibbs sampling on a central processing unit, and offers 5–18 times improvements in sampling speed compared with approaches based on tensor processing units and graphics processing units. Our sparse Ising machine can reliably factor semi-primes up to 32 bits and it outperforms competition-winning Boolean satisfiability solvers in approximate optimization. Moreover, our architecture can find the correct ground state, even when inexact sampling is made with faster clocks. Our problem encoding and sparsification techniques could be applied to other classical and quantum Ising machines, and our architecture could potentially be scaled to 1,000,000 or more p-bits using analogue silicon or nanodevice technologies.more » « less
-
Abstract This work solves 3SAT, a classical NP-complete problem, on a CMOS-based Ising hardware chip with all-to-all connectivity. The paper addresses practical issues in going from algorithms to hardware. It considers several degrees of freedom in mapping the 3SAT problem to the chip—using multiple Ising formulations for 3SAT; exploring multiple strategies for decomposing large problems into subproblems that can be accommodated on the Ising chip; and executing a sequence of these subproblems on CMOS hardware to obtain the solution to the larger problem. These are evaluated within a software framework, and the results are used to identify the most promising formulations and decomposition techniques. These best approaches are then mapped to the all-to-all hardware, and the performance of 3SAT is evaluated on the chip. Experimental data shows that the deployed decomposition and mapping strategies impact SAT solution quality: without our methods, the CMOS hardware cannot achieve 3SAT solutions on SATLIB benchmarks. Under the assumption of some hardware improvements, our chip-based 3SAT solver demonstrates a remarkable 250$$\times$$ acceleration compared to Tabu search in dwave-hybrid on a CPU.more » « less
-
Abstract With the slowdown of improvement in conventional von Neumann systems, increasing attention is paid to novel paradigms such as Ising machines. They have very different approach to solving combinatorial optimization problems. Ising machines have shown great potential in solving binary optimization problems like MaxCut. In this paper, we present an analysis of these systems in boolean satisfiability (SAT) problems. We demonstrate that, in the case of 3-SAT, a basic architecture fails to produce meaningful acceleration, largely due to the relentless progress made in conventional SAT solvers. Nevertheless, careful analysis attributes part of the failure to the lack of two important components: cubic interactions and efficient randomization heuristics. To overcome these limitations, we add proper architectural support for cubic interaction on a state-of-the-art Ising machine. More importantly, we propose a novel semantic-aware annealing schedule that makes the search-space navigation much more efficient than existing annealing heuristics. Using numerical simulations, we show that such an “Augmented” Ising Machine for SAT is projected to outperform state-of-the-art software-based, GPU-based and conventional hardware SAT solvers by orders of magnitude.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1145/3411511
