Name
Title | ||
|---|---|---|
GPU-based branch-and-bound method to solve large 0-1 knapsack problems with data-centric strategies. |
Abstract | ||
|---|---|---|
An out-of-core branch-and-bound (B&B) method to solve large 0-1 knapsack problems on a graphics processing unit (GPU) is proposed. Given a large problem that produces many subproblems, the proposed method dynamically swaps subproblems to CPU memory. Because such a CPU-centric subproblem management scheme increases CPU-GPU data transfer, we adopt three data-centric strategies to eliminate this side effect. The first is an out-of-order search (O3S) strategy that reduces the data transfer overhead by adaptively transferring subproblems between the CPU and GPU. The second is an explicitly-managed pipelining strategy that hides the data transfer overhead by overlapping data transfer with GPU-based B&B operations. The third is a GPU-based stream compaction strategy that reduces the sparseness of arrays to be transferred. Experimental results demonstrate that the proposed out-of-core method stored 41 times as many subproblems as a previous in-core method that manages subproblems in GPU memory, solving approximately twice as many problem instances on the GPU. In addition, compared to a previous breadth-first search (BFS) strategy, the proposed O3S strategy achieved an average speedup of 7.5 times. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1002/cpe.4954 | CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE |
Keywords | Field | DocType |
branch and bound,data-centric method,GPU,knapsack,out-of-core computation | Database-centric architecture,Branch and bound,Computer science,Parallel computing,Branch and bound method,Knapsack problem | Journal |
Volume | Issue | ISSN |
31 | 4 | 1532-0626 |
Citations | PageRank | References |
1 | 0.37 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jingcheng Shen | 1 | 2 | 1.74 |
| Kentaro Shigeoka | 2 | 3 | 1.07 |
| Fumihiko Ino | 3 | 317 | 38.63 |
| Kenichi Hagihara | 4 | 528 | 56.94 |