Moore's Law Reaches Its Limit! Developing a New Architecture to Solve the Combinatorial optimization problem

Main visual : Moore's Law Reaches Its Limit! Developing a New Architecture to Solve the Combinatorial optimization problem

What Will It Take for Computers to Improve the Society in the Future?

The performance of computers has evolved every day, while changing the world dramatically. Yet, there are many dreams that Fujitsu would like to solve using computers, such as resolving social problems. There are situations where it is difficult to make decision based on constraints such as limited number of people and time, planning for the disaster recovery, optimizing investment portfolios, or selecting economic policies. Can we use the computers to take decision for such difficult situation?

For a computer to determine what should be the next action, it must consider and evaluate the combinations of a variety of factors in order to select an optimal combination. These are called "combinatorial optimization problem". As the number of the factors increase, the number of the combinations increases explosively in "combinatorial optimization problem", and in order to solve within a practical time it is necessary to greatly improve the performance of the computers. However, the performance improvement as in Moore's law* , which has led the improvements of computer performance over the past 50 years is coming to an end, and the improvement in performance due to the semiconductor scaling is no expected.

In order to improve the future lifestyle and society by using computers, the industries need to take a variety of new steps. One of them is introducing completely new devices such as Quantum computer**.

Limitations of conventional computing

Although the current quantum computers can solve the "combinatorial optimization problem", at a high speed, but there is a limitation of connectivity between the adjacent elements, and at present it cannot deal with a wide range of problems. On the other hand, conventional processors cannot solve it at a high speed. For these reasons, implementation of a new computer architecture that can solve the wide range of combinations required in the real world in a manner which is both optimal and fast has become a key issue.

*: Moore's law, which refers that the number of transistors in semiconductor integrated circuits doubles in every two years, has acted as a guideline for the production and manufacturing of large scale integrated circuits. This law was first put forth in a 1965 paper by Gordon Moore, one of the founders of Intel.

**: A general term for computing technology that uses quantum phenomena. A method called "quantum annealing" is being developed as a means of solving the combinatorial optimization problem.

Developing a New Computer Architecture to Find Optimal Combinations

Fujitsu Laboratories Ltd. and the University of Toronto in Canada have jointly developed a new computer architecture for searching through a huge numbers of combinations to find optimal solutions in a variety of different real world problems. This architecture uses CMOS digital technology in order to improve its applicability, thus it can be freely used to handle a wide range of different problems. This newly developed technology offers the following two characteristics.

First of all, it is a non-von Neumann*** architecture to minimize the data movement. By using non-von Neumann processing instead of von Neumann processing (program execution) and update the optimization variable (bit) in a direction whereby the optimization problem’s cost decrease. First it first loads the problem from memory, then perform optimization as much as necessary, and finally outputs the results. Since it does not read or write from or to the memory during operations, this greatly minimizes loss of time and energy. Also, by minimizing the data movement between the basic circuits, it requires almost negligible data movement to the upper layers.

This technology minimizes data movement by using non-von Neumann operations.

The second is "High speed technology in basic optimization circuit". In the basic optimization circuit, probability theory is applied repeatedly to search from one state to the more optimal one. The possibility of finding the next state is improved by calculating the value of each operation for multiple candidates in parallel. If the search stuck in the middle of exploration, this method repeatedly adds a constant value to the total energy to increase the escape probability to the next state. This helps to obtain an optimal solution faster.

Acceleration technology for basic optimization circuits

***: Almost all current computers use "von Neumann processing", which means that they store the program and data in the memory, then execute the operations sequentially by reading the instruction and data. As computer performance has improved dramatically in recent years, the slow reading of instruction from the memory become a bottleneck, leading to non-von Neumann processing (which uses a different basic design) is being considered. Non-von Neumann architectures include a neurocomputers modeled after neural circuits, a quantum computers that apply the behavior of the elementary particles of quantum mechanics, and a DNA computers that use DNA as computing elements.

Operations Approximately 10,000 Faster Than Conventional Software Processes

We have evaluated the architecture by implementing the basic optimization circuit on FPGA**** which can handle 1024 bits, and found that it is approximately 10,000 times faster than the software processes operating on conventional processors.

By using multiple basic circuits that are performing optimization in parallel makes it possible to handle a wider range of problems than current quantum computers, at the same time increasing the scale of problems and the processing speed that can be handled. This enables, for instance, a faster solution of combinatorial optimization problems that involve too many calculations for current general-purpose processors to handle, such as the optimization of several thousands of physical distribution bases, or the formulation of investment portfolios that optimizes the profits of multiple projects within a limited budget. This technology is expected to broaden the area within where it is possible to apply information and communication technology through the use of accelerated optimal decision making.

Fujitsu Laboratories Ltd. will continue improving this newly developed architecture, and is planning to create a prototype system with a scale between 100,000 and 1 million bits that can be applied to real world problems by 2018, while conducting demonstrations in order to commercialize this technology.

****: Field Programmable Gate Array. An integrated circuit which can be configured by the customer or designer after manufacturing.