liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A Scalable GPU-Based Approach to Accelerate the Multiple-Choice Knapsack Problem
Linköping University, Department of Computer and Information Science, ESLAB - Embedded Systems Laboratory. Linköping University, The Institute of Technology.
Linköping University, Department of Computer and Information Science, ESLAB - Embedded Systems Laboratory. Linköping University, The Institute of Technology.
Linköping University, Department of Computer and Information Science, ESLAB - Embedded Systems Laboratory. Linköping University, The Institute of Technology.
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, Published paper (Refereed)
Abstract [en]

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.
Series
Design, Automation and Test in Europe, ISSN 1530-1591
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:liu:diva-72206DOI: 10.1109/DATE.2012.6176665ISBN: 978-1-4577-2145-8 (print)ISBN: 978-3-9810801-8-6 (print)OAI: oai:DiVA.org:liu-72206DiVA: diva2:458268
Conference
Design Automation and Test in Europe (DATE12) (short paper), Dresden, Germany, March 12-16, 2012.
Available from: 2011-11-22 Created: 2011-11-22 Last updated: 2014-11-14

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Suri, BharathBordoloi, Unmesh D.Eles, Petru

Search in DiVA

By author/editor
Suri, BharathBordoloi, Unmesh D.Eles, Petru
By organisation
ESLAB - Embedded Systems LaboratoryThe Institute of Technology
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 147 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf