Have you ever been faced with a problem where you had to find an optimal solution out of many possible options, such as finding the quickest route to a certain place, considering both distance and traffic?
If so, the problem you were dealing with is what is formally known as a “combinatorial optimization problem.” While mathematically formulated, these problems are common in the real world and spring up across several fields, including logistics, network routing, machine learning, and materials science.
However, large-scale combinatorial optimization problems are very computationally intensive to solve using standard computers, making researchers turn to other approaches. One such approach is based on the “Ising model,” which mathematically represents the magnetic orientation of atoms, or “spins,” in a ferromagnetic material.
At high temperatures, these atomic spins are oriented randomly. But as the temperature decreases, the spins line up to reach the minimum energy state where the orientation of each spin depends on its neighbors. It turns out that this process, known as “annealing,” can be used to model combinatorial optimization problems such that the final state of the spins yields the optimal solution.
In a new study, researchers from TUS, Japan, proposed a fully connected scalable annealing processor that, when implemented in FPGA, can easily outperform a modern CPU in solving various combinatorial optimization problems in terms of speed and energy consumption. The proposed method achieves this using an “array calculator,” consisting of multiple coupled chips, and a “control chip.” It could be applied to solve similar complex optimization problems in logistics, network routing, warehouse management, personnel assignment, drug delivery, and materials science. © Takayuki Kawahara from TUS, Japan
Researchers have tried creating annealing processors that mimic the behavior of spins using quantum devices, and have attempted to develop semiconductor devices using large-scale integration (LSI) technology aiming to do the same. In particular, Professor Takayuki Kawahara’s research group at Tokyo University of Science (TUS) in Japan has been making important breakthroughs in this particular field.
In 2020, Prof. Kawahara and his colleagues presented at the 2020 international conference, IEEE SAMI 2020, one of the first fully coupled (that is, accounting for all possible spin-spin interactions instead of interactions with only neighboring spins) LSI annealing processors, comprising 512 fully-connected spins.
Their work appeared in the journal IEEE Transactions on Circuits and Systems I: Regular Papers. These systems are notoriously hard to implement and upscale owing to the sheer number of connections between spins that needs to be considered. While using multiple fully connected chips in parallel was a potential solution to the scalability problem, this made the required number of interconnections (wires) between chips prohibitively large.
In a recent study published in Microprocessors and Microsystems, Prof. Kawahara and his colleague demonstrated a clever solution to this problem. They developed a new method in which the calculation of the system’s energy state is divided among multiple fully coupled chips first, forming an “array calculator.”
A second type of chip, called “control chip,” then collects the results from the rest of the chips and computes the total energy, which is used to update the values of the simulated spins. “The advantage of our approach is that the amount of data transmitted between the chips is extremely small,” explains Prof. Kawahara. “Although its principle is simple, this method allows us to realize a scalable, fully connected LSI system for solving combinatorial optimization problems through simulated annealing.”
The researchers successfully implemented their approach using commercial FPGA chips, which are widely used programmable semiconductor devices. They built a fully connected annealing system with 384 spins and used it to solve several optimization problems, including a 92-node graph coloring problem and a 384-node maximum cut problem.
Most importantly, these proof-of-concept experiments showed that the proposed method brings true performance benefits. Compared with a standard modern CPU modeling the same annealing system, the FPGA implementation was 584 times faster and 46 times more energy efficient when solving the maximum cut problem.
Now, with this successful demonstration of the operating principle of their method in FPGA, the researchers plan to take it to the next level. “We wish to produce a custom-designed LSI chip to increase the capacity and greatly improve the performance and power efficiency of our method,” Prof. Kawahara says. “This will enable us to realize the performance required in the fields of material development and drug discovery, which involve very complex optimization problems.”
Finally, Prof. Kawahara notes that he wishes to promote the implementation of their results to solve real problems in society. His group hopes to engage in joint research with companies and bring their approach to the core of semiconductor design technology, opening doors to the revival of semiconductors in Japan.
More information:
Kaoru Yamamoto et al, Scalable Fully Coupled Annealing Processing System and Multi-chip FPGA Implementation, Microprocessors and Microsystems (2022). DOI: 10.1016/j.micpro.2022.104674
Ryoma Iimura et al, Annealing Processing Architecture of 28-nm CMOS Chip for Ising Model With 512 Fully Connected Spins, IEEE Transactions on Circuits and Systems I: Regular Papers (2021). DOI: 10.1109/TCSI.2021.3114422
Provided by
Tokyo University of Science
Citation:
Scalable and fully coupled quantum-inspired processor solves optimization problems (2022, September 28)
