A Scalable GPU-Based Approach to Accelerate the Multiple-Choice Knapsack Problem
2012 (English)In: Design Automation and Test in Europe (DATE12) (short paper), Dresden, Germany, March 12-16, 2012., IEEE , 2012, 1126-1129 p.Conference paper (Refereed)
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.
Place, publisher, year, edition, pages
IEEE , 2012. 1126-1129 p.
, Design, Automation and Test in Europe, ISSN 1530-1591
Engineering and Technology
IdentifiersURN: urn:nbn:se:liu:diva-72206DOI: 10.1109/DATE.2012.6176665ISBN: 978-1-4577-2145-8ISBN: 978-3-9810801-8-6OAI: oai:DiVA.org:liu-72206DiVA: diva2:458268
Design Automation and Test in Europe (DATE12) (short paper), Dresden, Germany, March 12-16, 2012.