There are many problems in modern society that can be solved through key "optimal combinations." For example, in the transportation sector, if we knew the optimal combination of a given road's traffic volume, traffic light settings, and so on, we could mitigate congestion. However, the problem becomes increasingly complex and more difficult to solve as the number of phenomena and the combinations thereof which need to be accounted for, increases. How can we efficiently resolve such complicated problems? Hitachi is tackling this difficult challenge with a new-paradigm computing technology that uses its original semiconductors.
HAYASHI Masato
Researcher
OKUYAMA Takuya
Researcher
(Publication: April 26, 2018)
HAYASHIThis new-paradigm computer is a computer that will solve combinatorial optimization problems. Most problems in society can be thought of as "combinatorial optimization problems." For example, in the logistics sector, what is the best order in which to deliver goods to achieve the shortest possible delivery time. In the financial sector, the question might be, out of all the different kinds of stocks, which stock should be purchased for maximum return? The answers to such questions can be found in the "optimal combinations" of order and stocks. We invented a computer that can solve these types of combinatorial optimization problems efficiently to address this challenge.
HAYASHIEven standard computers based on central processing units (CPU) can solve combinatorial optimization problems. However, the number of possible combinations, such as the number of stocks that one might purchase, can increase exponentially as the scale of the problem increases. Thus, it takes a considerable amount of time for a standard computer to solve large-scale issues.
OKUYAMAWhile CPU-based computers can process various things, the speed at which processing is done is limited. We thought that if a computer only needed to do a certain type of calculation, we could significantly increase the processing speed by being creative with the circuit. This is where we set out to make a specialized machine.
HAYASHIThe limitations to functional improvements of CPUs themselves in recent years were also in the backdrop. By creating a specialized machine, we aimed to efficiently solve combinatorial optimization problems at high speeds and with low electrical power.
Figure 1: Ising model
HAYASHITo solve the problems, we use a mathematical model called the Ising model, which is used to research magnetic properties in the field of statistical mechanics. The Ising model consists of spins which can be oriented either up or down.
Solving combinatorial optimization problems usually consists of testing various combinations and searching for the best solutions. Instead of simply conducting this process, the problem we wish to solve is first mapped in the form of the Ising model.
OKUYAMABy conducting a process called annealing, we can converge the combination of the spinning directions and thereby optimize the energy expenditure of the Ising model. The computer that we invented reproduces this convergence behavior through a complementary metal oxide semiconductor (CMOS) circuit. That is, the Ising model, which has been mapped with a combinatorial optimization problem, is converged to a state that expends a minimal amount of energy. Thus, the solutions to combinatorial optimization problems are displayed in this state of the Ising model, which expends the least amount of energy.
HAYASHIHowever, convergence behavior along CMOS circuits has a pitfall. There is the possibility that the operations might stop at a local solution, where the energy is not at a minimum of the whole. We made adjustments to escape the local solution and pursue even better solutions. This technology which replicate the operations of the Ising model along CMOS circuits is called CMOS annealing, and the new-paradigm computers that incorporate this technology are called CMOS annealing machines.
HAYASHIYes, that is correct. In truth, there have been various endeavors to efficiently resolve combinatorial optimization problems utilizing the characteristics of the Ising model. For example, a Canadian company accomplished this using a superconductor circuit. However, one must maintain extremely low temperatures to utilize superconductor circuits which then requires a large facility.
This is where Hitachi shifted its focus to semiconductors. While direct comparisons cannot be made because the formulas differ, special cooling systems would be unnecessary if semiconductors were used, and their adoption would also be apt for mass production. Given these advantages, we thought that if we could combine semiconductors with the Ising model's new calculation system, we could make a computer that was extremely practical. Building from those ideas, we launched a development project for a new-paradigm computer. I have been involved in this project ever since it was launched.
OKUYAMAI joined the company just after this project was launched and have been involved in developing CMOS annealing machines ever since. While Mr. Hayashi mainly develops hardware, I develop software that manipulates and utilizes the hardware.
Figure 2: First-generation CMOS annealing machine
HAYASHIWe started with the hardware, in fact, the semiconductor chips. This is extremely rare. Making semiconductor chips has production costs in and of itself, and requires time as well. Usually, I believe that semiconductors are created only after multiple simulations have been conducted.
However, in order to demonstrate the possibility of calculations using the Ising model, Hitachi rather boldly started with producing semiconductors. As a result, we confirmed that we could solve problems at a high electric power efficiency. We call this hardware installed with the Ising chips the first-generation machine.
Figure 3: Second-generation CMOS annealing machine
We succeeded at solving a specific field's problems with the first-generation machine. However, to pursue practical application in the real world, we needed to devise a generic formula that could be applied across various fields. Therefore, we developed the second-generation CMOS annealing machine using a field-programmable gate array (FPGA). As an FPGA can be reconfigured after having been manufactured, all sorts of formulae can be tested. Furthermore, because it is mass produced, one can easily gain access to a machine, and development costs have been driven down.
At present, we utilize this second-generation model and are continuing to enhance its software. However, as the development process progresses, we hope to produce specialized semiconductor chips, develop CMOS annealing machines able to handle large-scale problems and further conserve energy.
HAYASHIAs a matter of fact, on our team, only the leader had expertise in semiconductors. Our expertise was in the information sector, and we had some difficulties handling hardware because we didn't know what to do. We had some difficulties simply trying to measure the semiconductor chips. We didn't even know how to place the chips onto the measuring device, and once we thought we had figured that out, the pin wouldn't fit...
OKUYAMAYou really did have a hard time, didn't you, Mr. Hayashi. But it looked like you had a lot of fun too!
HAYASHII was taking on a new field, and so I often slipped up when it came to the tiniest of details. But at the end of the day, I had a lot of fun because I was creating things. I feel extremely fortunate to have been able to experience creating semiconductors in an entirely new field.
HAYASHIYes, however, there is still much to be done. The CMOS annealing machine is a computer that utilizes a new formula, which necessitates creating basic software technology—the equivalent for general computers might be the operating system (OS).
OKUYAMAThere are two main software technologies for CMOS annealing machines.
First is the technology that will efficiently imbed the Ising model into the hardware. Ising models that have been mapped with combinatorial optimization problems take extremely complex shapes. We developed an algorithm that would convert this into a simple shape that the hardware can express. This technology serves as a point through which the CMOS annealing machine conducts calculations. No matter the scale of the problem, this is not something that time can be expended on. We developed creative methods to convert the complex Ising model into even simpler shapes so that it can be imbedded into the hardware, all the while maintaining high-speed processing.
The other is the technology to extract problems that need to be solved from society as combinatorial optimization problems, and map them in the form of the Ising model. If the previous technology can be compared to the OS, this technology is similar to an application, and where we are currently experiencing the most difficulty. Problems in society are extremely complex, and are not easily mapped…
HAYASHIJust taking the simple example of delivering goods, many detailed conditions emerge such as, "We must deliver to this client between 9:00 AM and 12:00 PM," or, "It is best not to pass through this intersection as it is often congested." There is a need to consider whether or not it is possible to map these complex problems in the form of Ising models in the first place. As a result of this thought process, we have unfortunately concluded that some problems are not fit to be addressed by CMOS annealing machines.
Figure 4: Technology layers in the CMOS annealing machine
HAYASHIThrough co-creation with customers and partners. The conversation may begin for example with a show of interest at an exhibition, etc., which leads to a discussion on what kind of problems a CMOS annealing machine might be able to solve. By exploring these ideas further, and then actually announcing, "We are able to solve these types of issues," allows us to take our machine to the next level.
OKUYAMAWe've also engaged in cooperation with Hokkaido University with the hope that these young, bright students will provide us new knowledge. Just as we engage in developing a wide range of things ranging from hardware to algorithms, Hokkaido University also explores the possibilities of CMOS annealing machines from various angles.
HAYASHIHokkaido University and Hitachi also jointly hosted a programming contest. Posting the question online, we encouraged a wide variety of people to participate. This contest was aimed at an algorithm for imbedding the Ising model efficiently into the hardware, one of the software technologies we just talked about. The purpose of the contest was to improve the algorithm used in this process.
HAYASHII really want to respond to real life issues that people face in the real world.
OKUYAMAThe hardware is basically complete, and the surrounding software technology is in the process of being completed. My hope for the future is that we would be able to solve real life issues in society, and not simply the problems that we prepared the machine to solve.
OKUYAMAIn an interview before I joined the company, I said, "I want to do something that involves both information and physics." I believe that I am now involved in a project that fuses both information and physics together. Straddling the two fields, I wish to continue to do something that interests me, and hope that the world might benefit from what I do.
HAYASHIWhen I hear "clients are struggling with this," even if our computers cannot solve the problem, I am starting to be able to see that "we might be able to solve the problem if we use something from this field." Utilizing my knowledge and my skills, I would be happy if I could help someone that is having a hard time.