In a paper published in the journal Nature Communications, researchers presented an Ising annealing computer using 80 superparamagnetic tunnel junctions (SMTJs) to solve a challenging 70-city traveling salesman problem (TSP), equivalent to a 4761-node Ising problem.
a Optimization algorithm for 70-city TSP. b Number of required SMTJs for various problems using different methods. Burma14, berlin52, eil76, and eil101 are TSP of 14, 52, 76, and 101 cities, respectively. c Comparison of total Ising energy (path) and total clock cycles for final solution with different SA-based algorithms, including symbiotic organisms search40, ant colony optimazation41, multi-offspring genetic algorithm42, and gene-expression programming7. Our method is tested on our Ising system and others are tested on Intel Core-i7 PC. In this comparison, our system runs at a main frequency of 10 kHz. Image Credit: https://www.nature.com/articles/s41467-024-47818-z
The system outperformed other Ising schemes by harnessing the inherent randomness and employing a global annealing scheme in power consumption and energy efficiency. This promising approach offers a solution for complex problems with limited hardware resources.
Additionally, a scalable cross-bar array architecture was proposed for integration using conventional magnetic random-access memories. These results highlight the potential of SMTJ-based Ising computers for future unconventional computing, emphasizing high energy efficiency, speed, and scalability.
Background
Past work has seen the pursuit of efficient algorithms and hardware systems to tackle non-deterministic polynomial-time (NP) hard problems like the Ising model. Adiabatic quantum computing (AQC) and quantum computing based on superconducting qubits have shown promise but face challenges such as high power consumption.
Simulated annealing on CMOS implementations has been explored but requires substantial hardware resources. Other approaches, like coherent Ising machines (CIM), suffer from complexity and scalability issues. Recent experiments have investigated various devices, like superparamagnetic tunnel junctions (SMTJs), for emulating Ising spins but encounter challenges with scalability.
Thin Film Deposition
Thin film samples were deposited on Si substrates via direct current (DC) and radio frequency (RF) magnetron sputtering, resulting in a layered structure. The substrate consisted of multiple metal layers with varying thicknesses, including cobalt iron boron (CoFeB), magnesium oxide (MgO), tantalum (Ta), Ruthenium (Ru), and platinum (Pt).
SMTJs were fabricated by patterning bottom electrode structures using photolithography and ion milling. MTJ pillar structures were then patterned using e-beam lithography, followed by the deposition of an encapsulation layer of silicon nitride (Si3N4). Finally, the analysts patterned and deposited top electrodes of tantalum/copper (Ta/Cu).
MTJ characterization involved applying DC bias currents using a source meter and reading the voltage signal across the SMTJ. The MTJ switching probability was observed to vary with the amplitude of applied currents. The team determined retention time by conducting random telegraph noise measurements, and they calculated the expectation values of event time by fitting an exponential function to the experimental results.
An Ising printed circuit board (PCB) integrated 80 SMTJ arrays and peripheral circuits controlled by an Arduino mega 2560 Rev3 Microcontroller Unit (MCU). Rail-to-rail digital-to-analog converters (DACs) generated analog DC inputs for peripheral circuits. Half of the DAC output channels stimulated N-channel metal-oxide-semiconductor (NMOS) gate terminals, while others provided reference voltages to comparators.
The MCU reads Outputs of comparator arrays through multiplexers and then calculates to obtain new inputs for DACs. The PCB board and SMTJs supply voltage was 5V and 0.8V, respectively. Designing the resistor values in each computing unit could adjust the center of sigmoidal curves, enabling optimization of the Ising computer's performance.
Experimental Ising Spin
The experimental results demonstrate using SMTJ-based Ising spin systems to solve NP-hard problems. During evolution processes, observers can construct an Ising model corresponding to various issues to observe the ground states. A stochastic nanomagnet, represented by SMTJ, is a natural implementation of the Ising spin. This system exhibits low energy barriers between its states, allowing for rapid transitions and retention times ranging from microseconds to milliseconds.
An 80-node Ising computer is built by integrating 80 SMTJs with peripheral circuits and an MCU. Each Ising spin is emulated by an SMTJ with intrinsic randomness, facilitating the solution of optimization problems. The MCU monitors the states of all SMTJs and generates input voltages for DACs based on updating rules. This system leverages the intrinsic stochastic behaviors of SMTJs to perform the metropolis process of simulated annealing in hardware, leading to efficient solution times.
Applying the Ising computer activates its capabilities to solve combinatorial optimization problems, including the TSP. Mapping the TSP to an Ising model activates the system, initiating the annealing process to discover near-optimal solutions. The system exhibits rapid convergence to low-energy states, aided by the intrinsic stochasticity of SMTJs, thus avoiding local minima. The probability of success in solving TSP increases with the problem size, demonstrating the scalability of the method.
To address the scalability challenge of large-scale TSP, a graph Ising compressing algorithm based on constrained TSP (CTSP) is proposed. This algorithm significantly reduces the spins and interactions required to solve TSP, optimizing limited hardware resources efficiently. Experimental results show the superiority of this method in achieving near-optimal solutions with reduced computational complexity.
The researchers proposed a cross-bar architecture for large-scale Ising computing, integrating SMTJ bit cells with row decoders and read-sense amplifiers. This architecture allows for the parallel operation of SMTJs, enabling scalable and efficient Ising computing. The electrical coupling through resistance change is evaluated to have negligible effects, ensuring reliable system operation.
Conclusion
In conclusion, the experimental results demonstrated the effectiveness of SMTJ-based Ising spin systems in solving NP-hard problems. Leveraging the intrinsic stochasticity of SMTJs and efficient hardware implementations enabled rapid convergence to near-optimal solutions. The proposed graph Ising compressing algorithm provided a scalable approach to address large-scale optimization tasks with reduced computational complexity.
The proposed cross-bar architecture also showcased the potential for scalable and efficient Ising computing. These findings highlighted the promise of SMTJ-based Ising systems for addressing complex optimization challenges in various domains.
PITOME Revolutionizes Transformers by Merging Tokens to Save Memory and Boost Speed