GPU-based branch-and-bound method to solve large 0-1 knapsack problems with data-centric strategies

摘要

Anout-of-core branch-and-bound (B&B)methodto solve large 0-1 knapsackproblemsona graphicsprocessing unit (GPU)is proposed.Givena large problem thatproducesmany subproblems, the proposed method dynamically swaps subproblems to CPU memory. Because such a CPU-centric subproblemmanagement 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 theCPUand 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 asmany 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.