GPU-based Ising computing for solving max-cut combinatorial optimization problems
| Autor: | Takashi Sato, Masayuki Hiromoto, Hengyang Zhao, Sheldon X.-D. Tan, Chase Cook |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Speedup
Computer science Maximum cut 020208 electrical & electronic engineering 02 engineering and technology Parallel computing Solver 020202 computer hardware & architecture Hardware and Architecture Problem domain 0202 electrical engineering electronic engineering information engineering Graph (abstract data type) Ising model Electrical and Electronic Engineering General-purpose computing on graphics processing units Software Randomness |
| Zdroj: | Integration. 69:335-344 |
| ISSN: | 0167-9260 |
| DOI: | 10.1016/j.vlsi.2019.07.003 |
| Popis: | In VLSI physical design, many algorithms require the solution of difficult combinatorial optimization problems such as max/min-cut, max-flow problems etc. Due to the vast number of elements typically found in this problem domain, these problems are computationally intractable leading to the use of approximate solutions. In this work, we explore the Ising spin glass model as a solution methodology for hard combinatorial optimization problems using the general purpose GPU (GPGPU). The Ising model is a mathematical model of ferromagnetism in statistical mechanics. Ising computing finds a minimum energy state for the Ising model which essentially corresponds to the expected optimal solution of the original problem. Many combinatorial optimization problems can be mapped into the Ising model. In our work, we focus on the max-cut problem as it is relevant to many VLSI design automation problems. Our method is inspired by the observation that Ising annealing process is very amenable to fine-grain massive parallel GPU computing. We will illustrate how the natural randomness of GPU thread scheduling can be exploited during the annealing process to create random update patterns and allow better GPU resource utilization. Furthermore, the proposed GPU-based Ising computing can handle any general Ising graph with arbitrary connections, which was shown to be difficult for existing FPGA and other hardware based implementation methods. Numerical results show that the proposed GPU Ising max-cut solver can deliver more than 2000X speedup over the CPU version of the algorithm on some large examples, which shows huge performance improvement for addressing many hard optimization algorithms for solving practical VLSI design automation problems. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect