A New Solution Method for Combinatorial Optimization Problems to Maximize the Computational Performance of GPU

Adaptive Bulk Search that exceeds 1 trillion searches per second

Collaborative Research

Tokyo, 17 Aug. 2020 - NTT DATA Corporation and the research team of Hiroshima University, Graduate School of Advanced Science and Engineering led by Professor Koji Nakano have developed a new computational method, Adaptive Bulk Search, for high-speed search to retrieve solutions to the combinatorial optimization problems. This method uses multiple GPUs (Graphics Processing Units2 to solve a quadratic unconstrained binary optimization (QUBO) problem1efficiently in parallel. We use this method effectively to solve various problems including hard problems for conventional technologies, and to expand the application fields of quantum computers and next-generation architectures.

Background

Quantum annealers, GPUs, and FPGAs3 have been used to develop an architecture that solves the combinatorial optimization problems at high speed in the recent research and development activities. The combination optimization problems are applicable to a wide range of practical problems, which means that the computation capability to find the solution to these problems will lead to solve many social problems. The research and development of the new architecture, where various combinatorial optimization problems are integrated to a unified problem called QUBO problem, aim to solve the QUBO problem at high speed.

The features of our new method are "its flexibility for various QUBO problems" and "the large-scale computing system that can achieve acceleration proportional to the number of computers." These features realize flexible and scalable computation, and is expected to greatly expand the potential of this technology area beyond solving specific problems at a certain speed.

In January 2019, NTT DATA launched Quantum Computer and Next-Generation Architecture Lab Service4 to promote quantum computers and other next-generation architectural applications in various fields through the validations of these. Based on these validations, NTT Data provided applicable cases, evaluation methods and current problems, with which the Hiroshima University research team found the new solution method. NTT DATA will accelerate research and development activities to efficiently solve the unsolvable problems that are difficult to solve, even social issues in the future, through innovations in computing.

Overview

The new solution method, Adaptive Bulk Search, uses multiple algorithms to search in parallel for the best solution with the lowest cost from a large number of solutions on the GPU.

The Adaptive Bulk Search:

  • can solve various QUBO problems by changing the search method flexibly;
  • can increase the computation speed by using a larger computer system and supercomputer in proportion to the number of computing nodes; and
  • was designed considering the features of the GPU architecture, and achieved a computation performance of over 1 trillion solutions per second using a server equipped with four latest NVIDIA GPUs5.

The experiment results show that the Adaptive Bulk Search can solve the problems including the maximum cut problem, the traveling salesman problem, and the random problem very efficiently. In addition, it can handle up to 32,768-bit QUBO problems at this time.

Details of the research will be presented by Associate Professor Ryota Yasudo of Hiroshima University at the International Conference on Parallel Processing (ICPP), which will be held from August 17 to 20. The ICPP is a traditional international conference on parallel processing, and this will be the 49th edition.

FIGURE: Yasudo, et.al., ICCP 2020

(FIGURE: Yasudo, et.al., ICCP 2020)

Future Goals

NTT DATA will use this solution method to address various problems in the logistics, finance, and manufacturing industries, as well as to improve the performance of AI and machine learning. NTT DATA will also work with Hiroshima University to further improve the method to efficiently find solutions to unsolved difficult problems by expanding its applicability, in attempting to solve the social problems such as the issues of efficient energy use and smart logistics networks.

Conference Information

Conference

International Conference on Parallel Processing(ICPP)2020

Research Paper

Adaptive Bulk Search:Solving Quadratic Unconstrained Binary Optimization Problems on Multiple GPUs

Authors

Ryota Yasudo, Koji Nakano, Yasuaki Ito, Masaru Tatekawa, Ryota Katsuki, Takashi Yazane, Yoko Inaba

DOI No.

10.1145/3404397.3404423

Notes

  1. A quadratic unconstrained binary optimization (QUBO) problem is an unconstrained optimization problem expressed in quadratic form, where each variable can take 0 or 1.
  2. Graphics Processing Unit, originally an integrated circuit specialized for graphics processing. It has been used in many supercomputers because its high computational processing power can accelerate a variety of computations other than graphics processing.
  3. Abbreviation for Field Programmable Gate Array, an integrated circuit that allows users to set and change the configuration of the logic circuit.
  4. NTT DATA Launches Quantum Computer/Next Generation Architecture Lab service
    https://www.nttdata.com/global/ja/news/release/2019/012501/
  5. NVIDIA GeForce RTX 2080 Ti GPU

August 17, 2020

Tokyo, Japan