Annealing processors (AP) specializing in solving combinatorial optimization problems have attracted attention. From the perspective of versatility, there has been a demand for fully-coupled Ising model-based AP, but challenges remain in achieving a system that combines both capacity (number of spins) and precision (interaction bit width) due to the complexity of the coupling. This study proposed a Dual Scalable Annealing Processing System (DSAPS) that can simultaneously scale the number of spins and interaction bit width using the same scalable structure. This introduces a new direction in scalability that combines both capacity and precision, compared to previous approaches that focused solely on capacity. A DSAPS with 2,048-spin and 10-bit interaction was implemented on an actual board. Four scaled MAX-CUT problems were used for operational validation, achieving accuracy of over 97 % compared with theoretical values. Compared to CPU simulation for a weighted MAX-CUT problem, the average cut value error was limited to 0.912 %. Furthermore, the average cut value of DSAPS was 2.93 % closer to that of CPU simulation than the 4 bit interaction board. These results confirm the utility of the proposed system and its new scaling direction.
Annealing processors (AP) specializing in solving combinatorial optimization problems have attracted attention. From the perspective of versatility, there has been a demand for fully-coupled Ising model-based AP, but challenges remain in achieving a system that combines both capacity (number of spins) and precision (interaction bit width) due to the complexity of the coupling. This study proposed a Dual Scalable Annealing Processing System (DSAPS) that can simultaneously scale the number of spins and interaction bit width using the same scalable structure. This introduces a new direction in scalability that combines both capacity and precision, compared to previous approaches that focused solely on capacity. A DSAPS with 2,048-spin and 10-bit interaction was implemented on an actual board. Four scaled MAX-CUT problems were used for operational validation, achieving accuracy of over 97 % compared with theoretical values. Compared to CPU simulation for a weighted MAX-CUT problem, the average cut value error was limited to 0.912 %. Furthermore, the average cut value of DSAPS was 2.93 % closer to that of CPU simulation than the 4 bit interaction board. These results confirm the utility of the proposed system and its new scaling direction.
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.
There has been progress in annealing processors for solving combinatorial optimization problems. There are two types of annealing processors: the "sparsely coupled" type, which implements only some spin-to-spin couplings, and the "fully coupled" type, which implements all spin-to-spin couplings. The latter has the advantage of having a large number of problems to be solved per spin, but had been said to have the disadvantage of poor scalability due to the complicated coupling. To overcome this, we first created a scalable Fully coupled annealing processing system (SFCAPS) by using multi-chip operation and implemented it on an FPGA board. This is to reduce the amount of coupling per chip by performing the multi-chip operation, and to improve the scalability by facilitating the connection between the chips. However, in the architecture, multi-chip operation could not be fully used and most of the chips on the board were idle for a large amount of time. Therefore, for this study, we implemented a parallel annealing method called multi-spin threading on this architecture to reduce the number of idle chips and demonstrated that the architecture can operate more efficiently. As a result, the architecture became more efficient, which raised the parallelism of the architecture. This has resulted in an average 5% improvement in the accuracy of the annealing processor's solution, demonstrating that it is easier to achieve a high accuracy solution.
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), 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.
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.
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.