bhasu_DATE12

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

Bharath Suri
 
Unmesh D. Bordoloi
Petru Eles Author homepage

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.


Related files:
bhasu_DATE12.pdfAdobe Acrobat portable document


[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.
( ! ) perl script by Giovanni Squillero with modifications from Gert Jervan   (v3.1, p5.2, September-2002-)
Last modified on Monday December 04, 2006 by Gert Jervan