7138

A Scalable GPU-based Approach to Accelerate the Multiple-Choice Knapsack Problem

Bharath Suri, Unmesh D. Bordoloi, Petru Eles
Delopt, India
Design Automation and Test in Europe (DATE12), 2012

@article{suri2012scalable,

   title={A Scalable GPU-based Approach to Accelerate the Multiple-Choice Knapsack Problem},

   author={Suri, B. and Bordoloi, U.D. and Eles, P.},

   year={2012}

}

Download Download (PDF)   View View   Source Source   

645

views

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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: