Annealing processor solves combinatorial optimizations

informatics

With information from Tokyo University of Science – 10/04/2022

Annealing processor solves optimizes

How spins can solve a real-world problem by implementing an Ising machine.
[Imagem: Kaoru Yamamoto et al. – 10.1016/j.micpro.2022.104674]

annealing computation

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

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

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

The difficulty is that large-scale combinatorial optimization problems are too computationally intensive to be solved by computers, causing researchers to 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 point 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 that of its neighbors.

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

But what 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 messing with the still complicated hardware of quantum simulators and computers, which is not a negligible advantage.

Annealing processor solves optimizes

Implementation of the annealing computation done by the team, 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 the Tokyo University of Science did, who built one of the first fully coupled LSI annealing processors (that is, accounting for all possible spin-spin interactions, rather than interactions with neighboring spins only), comprising 512 fully interconnected spins.

But a problem arose: The system proved to be notoriously difficult to implement and scale up due to the large number of connections between the spins that need 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 chips prohibitively large.

The duo then devised 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 subdivided between several fully coupled chips, forming a “matrix calculator”. A second type of chip, called a control chip, then collects the results from the matrix calculators and calculates 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 Professor Kawahara. “Although its principle is simple, this method allows us to realize a scalable and fully connected LSI system to solve combinatorial optimization problems through simulated annealing.”

Annealing processor solves optimizes

Annealing 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 are programmable once they are ready. They built a fully connected annealing system with 384 spins and used it to solve several optimization problems, including a 92-ns graph coloring problem and a 384-ns maximum cutoff problem.

More importantly, proof-of-concept tests showed that the method brings real performance benefits: Compared to a modern CPU running a program that models the same annealing system, the FPGA implementation was 584 times faster and consumed 46 times less energy by solving the maximum cut problem.

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

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

Bibliography:

Article: Scalable Fully Coupled Annealing Processing System and Multi-chip FPGA Implementation
Authors: Kaoru Yamamoto, Takayuki Kawahara
Magazine: Microprocessors and Microsystems
DOI: 10.1016/j.micpro.2022.104674

Follow Technological Innovation Site on Google News

Other news about:

more topics

Source link

About Admin

Check Also

“iPhone 15” should have camera with powerful Sony sensor

THE apple could lead to a great increase for the cameras of the line “iPhone …

Leave a Reply

Your email address will not be published. Required fields are marked *