This paper presents a CMOS annealing processor (CMOS-AP) that accelerates ground state searches of the Ising model. The main feature of this processor is its inter-chip connection interface for making a larger chip. A credit card sized compute node integrating two CMOS-APs was also developed as an interface with existing computer systems. The compute node can handle up to 61,952 spins at a time. A performance evaluation using the node improved the CPU speed by 55 times in solving a minimum vertex cover problem, one of the NP-hard combinatorial optimization problems. Finally, we describe a cloud interface for the compute node to make the CMOS-APs more useful and to promote application development for it.
This paper presents a CMOS annealing processor (CMOS-AP) that accelerates ground state searches of the Ising model. The main feature of this processor is its inter-chip connection interface for making a larger chip. A credit card sized compute node integrating two CMOS-APs was also developed as an interface with existing computer systems. The compute node can handle up to 61,952 spins at a time. A performance evaluation using the node improved the CPU speed by 55 times in solving a minimum vertex cover problem, one of the NP-hard combinatorial optimization problems. Finally, we describe a cloud interface for the compute node to make the CMOS-APs more useful and to promote application development for it.
This paper presents a CMOS annealing processor (CMOS-AP) that accelerates ground state searches of the Ising model. The main feature of this processor is its inter-chip connection interface for making a larger chip. A credit card sized compute node integrating two CMOS-APs was also developed as an interface with existing computer systems. The compute node can handle up to 61,952 spins at a time. A performance evaluation using the node improved the CPU speed by 55 times in solving a minimum vertex cover problem, one of the NP-hard combinatorial optimization problems. Finally, we describe a cloud interface for the compute node to make the CMOS-APs more useful and to promote application development for it.
This research is concerned with an annealing processor for efficiently solving a combinatorial optimization problem.\nIn order to realize a smart society, optimization of people and thingssuch as transportation networks, power networks, human resource allocationand routes is indispensable. Many of these problems are called combinatorial optimization problems and are known as very important problems in modern society. However, it is known that the combinatorial optimization problem is NP-hard and it is difficult to efficiently solve it with a conventional Neumann computer.\nIn recent years, the miniaturization of the process of manufacturing computer chips is approaching the physical limit. Therefore, especially in the solution by the full search, the improvement in speed due to the calculation speed of the computer cannot be expected. From such a background, dedicated hardware capable of solving a combination optimization problem at high speed and with low power consumption has been attracting attention.\nThe annealing processor is a general-purpose combination optimization solver that utilizes the property that the ground state of the optimization problem expressed by using the Ising model and the optimal solution of the combination optimization problem match. The Ising model is a ferromagnetic model in statistical physics expressed by spins having an upward and downward state, spin-spin interactions occurring between the spins, and an external magnetic field acting on each spin. The Ising model can express a combinatorial optimization problem by expressing a control target and a cost using these parameters. The annealing processor updates the spin state while slowly lowering the temperature parameters based on simulated annealing,which is an optimization method learned from natural phenomena generally called annealing. Eventually, the spin will reach the ground state with a high probability and obtain the optimal solution.\nAnnealing processors are classified into two types, the nearest neighbor type and the fully connected type, depending on the shape of the Ising model simulated on the hardware. In the nearest neighbor type, the coupling between spins is limited to only between adjacent spins, and in the full coupling type, coupling exists between arbitrary spins. The nearest neighbor type realizes high parallel processing by reducing the data spin required by simulated annealing by reducing the proximity spin. In addition, since data transfer is limited to adjacent spins, the scalability is high. However, since the spin-to-spin interaction is sparse, there is a problem that the class of combinatorial optimization problems that can be dealt with is limited, or that the problem requires deformation processing to match the Ising model of hardware. The fully connected type can solve any class of problems as long as the number of spins permits, however it requires connections between arbitrary spins.Therefore, scalability is low. Because there there is a dependency on all spins,the number of spins that can be updated at one time is always limited to only one regardless of the total number of spins. Therefore, it takes time to converge to the ground state.\nIn this research, we propose a method of increasing the number of spins for this annealing processor by using (1) a spatially-expanded time-division processing mechanism architecture based on a loosely-coupled type, (2) An algorithm for applying a fully coupled Ising network to a more complex Ising network using the nearest neighbor Ising network and an annealing method that can be updated in parallel, (3)We conducted a study on the architecture of a fully coupled annealing processor for parallel updating annealing.\nAs described above, the research described in this paper contributes to the improvement of the efficiency of the annealing processor for solving the large-scale combinatorial optimization problem from both the fundamental algorithm and the hardware architecture. I hope that this research will solve the combinatorial optimization problem that is expected to increase in demand in the future and contribute to the development of human society.
Combinatorial optimization problems with a large solution space are difficult to solve just using von Neumann computers. Ising machines or annealing machines have been developed to tackle these problems as a promising Non-von Neumann computer. In order to use these annealing machines, every combinatorial optimization problem is mapped onto the physical Ising model, which consists of spins, interactions between them, and their external magnetic fields. Then the annealing machines operate so as to search the ground state of the physical Ising model, which corresponds to the optimal solution of the original combinatorial optimization problem. A combinatorial optimization problem can be firstly described by an ideal fully-connected Ising model but it is very hard to embed it onto the physical Ising model topology of a particular annealing machine, which causes one of the largest issues in annealing machines. In this paper, we propose a fully-connected Ising model embedding method targeting for CMOS annealing machine. The key idea is that the proposed method replicates every logical spin in a fully-connected Ising model and embeds each logical spin onto the physical spins with the same chain length. Experimental results through an actual combinatorial problem show that the proposed method obtains spin embeddings superior to the conventional de facto standard method, in terms of the embedding time and the probability of obtaining a feasible solution.
Large-scale CMOS annealing processors are being developed to solve combinatorial optimization problems in society. Although it has been difficult to implement fully coupled annealing processors on multiple chips due to the complexity of the coupling, it is possible to scale by dividing a part of the calculation. In this work, we aim to realize a 4096 spin scalable fully coupled annealing processing system with 38 chips. For this purpose, we fabricated and evaluated the A-chip LSI that serves as the core in this system. We also reduced the number of required A-chips by 43.75% by reducing the interactions that occupy most of the area. In addition, we introduced spin threads to improve solution accuracy.
Annealing processors (APs) specialized for solving combinatorial optimization problems (COPs) have been gaining attention. Among them, APs that use a fully-coupled Ising model are in demand because of their versatility. However, due to the complexity of the spin couplings, challenges remain in achieving systems that balance both capacity (number of spins) and precision (interaction bit width). Previous studies have implemented annealing systems that only increase the number of spins using a scalable structure by distributing the calculation across multiple chips. This study proposes a dual scalable annealing processing system (DSAPS) that can simultaneously scale both capacity and precision using the same scalable structure. This demonstrates a new direction that combines both the number of spins and interaction bit width. A board implementation utilized spin threads to create two types of DSAPS: DSAPS #1, with 2048 spins, 10-bit interactions and four threads, and DSAPS #2, with 1024 spins, 37-bit interactions and two threads. Scaled MAX-CUT problems were used for operational validation, achieving an accuracy of over 99% compared with theoretical values. In another validation using the 0-1 knapsack problem, DSAPS #1 achieved an average deviation of over 99% relative to the knapsack capacity, whereas DSAPS #2 reduced the average deviation to 0.73%. This result is close to the average deviation of 0.40% obtained with an annealing emulation on a CPU (64-bit), demonstrating the significance of implementing DSAPSs suited to the characteristics of COPs.
Although quantum computing is expected to supplant traditional computing in several application fields, its adoption is hampered by temperature and economic constraints. To overcome these hurdles, researchers have proposed complementary metal-oxide-semiconductor (CMOS) annealing circuits. These circuits draw inspiration from quantum computing algorithms such as quantum annealing and aim to achieve near-quantum benefits by leveraging traditional CMOS technologies. This paper introduces an Ising-model-based hardware architecture that can be applied to combinatorial optimization problems (COPs). With its ability to express quadratic unconstrained binary optimization (QUBO) formulations as polynomials, the Ising model facilitates the encapsulation of multiple solutions and mapping onto fully connected architecture. The proposed annealing accelerator utilizes traditional circuit technologies, including pseudo-random number generators (PRNGs), to realize the required algorithms. The chip proposed herein, implemented using Taiwan Semiconductor Manufacturing Company (TSMC) 90-nm CMOS technology, operates at 50 MHz and covers an area of $3.24{\mathrm{m}}{{\mathrm{m}}^2}$3.24mm2. Experimental results demonstrate the excellent performance of this annealing accelerator in terms of area and power consumption, indicating its promise for use in solving COPs rapidly.