The Ising annealing processor has emerged as a promising approach to accelerate the discovery of the optimal solutions for a wide range of combinatorial optimization problems (COPs), by mapping various COPs into a unified Ising model. However, fixed computational strategies and inflexible architectures make previous designs suffer from a low hardware resource utilization rate when the numbers of the total required and real-time flipped spins vary across different COPs and iteration steps. In this paper, a novel spin scale-aware self-adaptive Ising annealing processing architecture (AIAPA) is proposed to address this problem, with an adaptive computational strategy, a custom instruction set, multi-traffic mode routers, and a fully-pipelined computing array. It can dynamically adapt to the varying scenarios during the Ising annealing process to maximize the performance of limited hardware resources. Its prototype, supporting 65k fully-connected spins, is implemented on an FPGA platform, operates at a clock frequency of 188 MHz. The AIAPA achieves up to a 24.22 times faster annealing speed compared to the state-of-the-art FPGA design on the max-cut optimization problem while maintaining a high convergence accuracy.
The Ising annealing processor has emerged as a promising approach to accelerate the discovery of the optimal solutions for a wide range of combinatorial optimization problems (COPs), by mapping various COPs into a unified Ising model. However, fixed computational strategies and inflexible architectures make previous designs suffer from a low hardware resource utilization rate when the numbers of the total required and real-time flipped spins vary across different COPs and iteration steps. In this paper, a novel spin scale-aware self-adaptive Ising annealing processing architecture (AIAPA) is proposed to address this problem, with an adaptive computational strategy, a custom instruction set, multi-traffic mode routers, and a fully-pipelined computing array. It can dynamically adapt to the varying scenarios during the Ising annealing process to maximize the performance of limited hardware resources. Its prototype, supporting 65k fully-connected spins, is implemented on an FPGA platform, operates at a clock frequency of 188 MHz. The AIAPA achieves up to a 24.22 times faster annealing speed compared to the state-of-the-art FPGA design on the max-cut optimization problem while maintaining a high convergence accuracy.
An annealing processor based on the Ising model is a remarkable candidate for combinatorial optimization problems and it is superior to general von Neumann computers. CMOS-based implementations of the annealing processor are efficient and feasible based on current semiconductor technology. However, critical problems with annealing processors remain. There are few simulated spins and inflexibility in terms of implementable graph topology due to hardware constraints. A prior approach to overcoming these problems is to emulate a complicated graph on a simple and high-density spin array with so-called minor embedding, a spin duplication method based on graph theory. When a complicated graph is embedded on such hardware, numerous spins are consumed to represent high-degree spins by combining multiple low-degree spins. In addition to the number of spins, the quality of solutions decreases as a result of dummy strong connections between the duplicated spins. Thus, the approach cannot handle large-scale practical problems. This paper proposes a flexible and scalable hardware architecture with time-division multiplexing for massive spins and high-degree topologies. A target graph is separated and mapped onto multiple virtual planes, and each plane is subject to interleaved simulation with time-division processing. Therefore, the behavior of high-degree spins is efficiently emulated over time, so that no dummy strong connections are required, and the solution quality is accordingly improved. We implemented a prototype hardware design for FPGAs, and we evaluated the proposed method in a software-based annealing processor simulator. The results indicate that the method increased the spins that can be deployed. In addition, our time-division multiplexing architecture improved the solution quality and convergence time with reasonable resource consumption.
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.
Annealing processors that can quickly solve combinatorial optimization problems (COPs) are attracting attention. They solve COPs by converting them into spin-spin interactions and external fields of the Ising model. Annealing processors that use fully-coupled spin coupling can solve a wide range of COPs. However, it is difficult to execute parallel annealing in fully-coupled spin coupling because one spin is updated by referring to all the other spins. In this paper, we proposed multi-state pseudo annealing (MSPA), which is an annealing method for changing the spin value from a conventional binary to a multi state that takes into account intermediate states. In a software validation, we solved the Maxcut problem and the traveling salesman problem and confirmed that the proposed method improves the solution quality in parallel annealing compared with simulated annealing and pseudo annealing. In addition, we implemented MSPA on a field-programmable gate array as a 1024 -spin 16 -parallel system using a scalable structure. With the proposed system, we solved the Max-cut problem and confirmed that it achieves a 9.40 times faster solving speed and yields a 1% larger Max-cut value compared with the conventional parallelized annealing processors.
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.
Annealing processors (APs), which can efficiently solve combinatorial optimization problems (COPs), have attracted attention. APs that have fully-coupled spin coupling are the focus of active research due to their ability to handle a wide range of COPs. However, since a single spin is updated by referring to the states of all other spins, sequential spin updates are necessary. This makes it difficult to achieve both faster computation time and stable solution quality. We propose transition-based multi-state pseudo annealing (TMSPA), which is an annealing method that enables discrete spin states between ±1 and maps the conventional two spin states to different transition directions. By using TMSPA, we solved the Max-cut problem and the traveling salesman problem (TSP). We found that TMSPA enables all-parallel annealing for both COPs. In terms of solution quality, TMSPA performed comparably to or better than simulated annealing and pseudo annealing. For the TSP, TMSPA reached better minimum values with less than one-third the number of Monte Carlo steps than previous all-parallel annealing methods. We also propose an all-parallelized annealing processing system using TMSPA. By using the proposed system with 1024- and 2048-spin configurations, we achieved better solution quality and 6.25 times faster computation time while operating at half the frequency and limiting the increase in circuit-resource utilization to 1.03–5.70 times compared with a previous parallelized AP. This result indicates that reducing circuit complexity using TMSPA is highly effective in the implementation of parallelized APs.
Autonomous navigation serves as a versatile technology prominently used in logistics and transportation. The application of automatic guided vehicles has become pervasive within the realm of factory automation, as shown in Fig. 30.4.1. For such applications, path planning and collision avoidance are two main tasks. Both tasks are classified as combinatorial optimization problems (COPs), and finding their optimal solutions is time-consuming [1]. A COP can be mapped to an Ising model with spin couplings based on the nature of the problem. Annealing is then applied to find the solution by iteratively updating spins until the states of the spins reach the lowest energy (known as a Hamiltonian). Digital annealers [2] –[4] have been demonstrated to accelerate solving COPs with exponential complexity. Some designs [2] [3] only support small-scale COPs because of the limited number of spins. The other [4] can solve larger problems, while the problem complexity is still limited by their sparse spin connections. Mapping a COP onto an Ising model and vice versa is necessary for solving a specific problem, which is also not addressed in the previous hardware digital annealers.