The annealing processor solves combinatorial optimizations

informatics

With information from the University of Science in Tokyo – 04.10.2022

annealing calculation

Have you ever encountered a problem where you had to find the optimal solution among many possible options, such as finding the fastest route to a certain location given the distance and traffic?

In this case, the problem you were dealing with is formally known as a “combinatorial optimization problem”.

These problems are common in the real world and appear in many fields outside of logistics, including computer network routing, machine learning, and materials science.

The difficulty is that large-scale combinatorial optimization problems are too computationally demanding to be solved by computers, which is why researchers turn to alternative 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 room temperature, these atomic spins are oriented in random directions. But as the temperature decreases, the spins begin to align in search of a minimum energy state, where the orientation of each spin depends on the orientation of its neighbors.

It is not a full-fledged quantum computer, but a quantum simulator. And this operating principle, known as “quantum annealing”, can be used to model combinatorial optimization problems so that the final state of the spins gives the optimal solution. The D-Wave quantum computer works on this principle, as do some alternative processor architectures that are still at lab scale.

But what the researchers really want is to create annealing processors that mimic the behavior of spins using common electronic semiconductor chips such as LSI (Large Scale Integration) technology. This means avoiding tinkering with the still complicated hardware of quantum simulators and computers, which is not a negligible advantage.

The team’s implementation of annealing calculations, using two types of chips.
[Imagem: Kaoru Yamamoto et al. – 10.1016/j.micpro.2022.104674]

electronic annealing processor

This is what Kaoru Yamamoto and Takayuki Kawahara of Tokyo University of Science have done, building one of the first fully coupled annealing LSI processors (that is, taking into account all possible spin-spin interactions, not just interactions with neighboring spins ), which consists of 512 fully interconnected spins.

But a problem arose: the system turned out to be notoriously difficult to implement and scale due to the large number of connections between spins that needed to be considered. While the use of multiple fully connected chips in parallel was a potential solution to the scalability problem, it made the number of interconnects (wires) required between the chips prohibitively large.

The duo then designed and built a clever solution to this problem: they developed a new method in which the calculation of the system’s energy state is first shared between several fully connected chips, forming a “matrix calculator”. Another type of chip, called a control chip, then collects the results from the matrix calculator and calculates the total energy, which is used to update the values ​​of the simulated revolutions.

“The advantage of our approach is that the amount of data transferred between chips is extremely small,” explains Professor Kawahara. “Although its principle is simple, this method allows us to realize a scalable and fully connected LSI system for solving combinatorial optimization problems through simulated annealing.”

An incandescent computer prototype built by the team.
[Imagem: Kaoru Yamamoto et al. – 10.1016/j.micpro.2022.104674]

Speed ​​and energy efficiency

The researchers implemented their approach using commercial FPGA chips, which are integrated circuits that can be programmed once they are ready. They built a fully coupled 384-spin annealing system and used it to solve several optimization problems, including a 92 ns graph coloring problem and a 384 ns maximum break problem.

More importantly, proof-of-concept tests showed that the method delivers real performance benefits: compared to a modern CPU running a program modeling the same annealing system, the FPGA implementation was 584 times faster and consumed 46 times less energy by solving the maximum rez an issue.

Now, with this successful demonstration of the working principle of the annealing FPGA processor, the researchers plan to take it to the next level.

“We wanted to produce a custom LSI chip to increase the capacity and greatly improve the performance and energy efficiency of our method,” Professor Kawahara announced. “This will allow us to achieve the required performance in the areas of materials development and drug discovery, which involve very complex optimization problems.”

Other news about: