A Scalable GPU-Based Approach to Accelerate the Multiple-Choice Knapsack Problem
Design Automation and Test in Europe (DATE 2012) (short paper), Dresden, Germany, March 12-16, 2012.
ABSTRACT
Variants of the 0-1 knapsack problem manifest themselves at the core of several system-level optimization problems. The running times of such system-level optimization techniques are adversely affected because the knapsack problem is NP-hard. In this paper, we propose a new GPU-based approach to accelerate the multiple-choice knapsack problem, which is a general version of the 0-1 knapsack problem. Apart from exploiting the parallelism offered by the GPUs, we also employ a variety of GPU-specific optimizations to further accelerate the running times of the knapsack problem. Moreover, our technique is scalable in the sense that even when running large instances of the multiple-choice knapsack problems, we can efficiently utilize the GPU compute resources and memory bandwidth to achieve significant speedups.
[SDE12] Bharath Suri, Unmesh D. Bordoloi, Petru Eles, "A Scalable GPU-Based Approach to Accelerate the Multiple-Choice Knapsack Problem", Design Automation and Test in Europe (DATE 2012) (short paper), Dresden, Germany, March 12-16, 2012. |
|
