Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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
Accelerating the knapsack problem on GPUs
Linköping University, Department of Computer and Information Science, ESLAB - Embedded Systems Laboratory.
2011 (English)Independent thesis Advanced level (degree of Master (Two Years)), 30 credits / 45 HE creditsStudent thesis
Abstract [en]

The knapsack problem manifests itself in many domains like cryptography, financial domain and bio-informatics. Knapsack problems are often inside optimization loops in system-level design and analysis of embedded systems as well. Given a set of items, each associated with a profit and a weight, the knapsack problem deals with how to choose a subset of items such that the profit is maximized and the total weight of the chosen items is less than the capacity of the knapsack. There exists several variants and extensions of this knapsack problem. In this thesis, we focus on the multiple-choice knapsack problem, where the items are grouped into disjoint classes.

However, the multiple-choice knapsack problem is known to be NP-hard. While many different heuristics and approximation schemes have been proposed to solve the problem in polynomial-time, such techniques do not return the optimal solution. A dynamic programming algorithm to solve the problem optimally is known, but has a pseudo-polynomial running time. This leads to high running times of tools in various application domains where knapsack problems must be solved. Many system-level design tools in the embedded systems domain, in particular, would suffer from high running when such a knapsack problem must be solved inside a larger optimization loop.

To mitigate the high running times of such algorithms, in this thesis, we propose a GPU-based technique to solve the multiple-choice knapsack problem. We study different approaches to map the dynamic programming algorithm on the GPU and compare their performance in terms of the running times. We employ GPU specific methods to further improve the running times like exploiting the GPU on-chip shared memory. Apart from results on synthetic test-cases, we also demonstrate the applicability of our technique in practice by considering a case-study from system-level design. Towards this, we consider the problem of instruction-set selection for customizable processors.

Place, publisher, year, edition, pages
2011. , 87 p.
Keyword [en]
gpgpu, knapsack, parallel computing
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-70406ISRN: LIU-IDA/LITH-EX-A--11/029--SEOAI: oai:DiVA.org:liu-70406DiVA: diva2:439054
Subject / course
Computer and information science at the Institute of Technology
Presentation
2011-08-24, 13:00 (English)
Uppsok
Technology
Supervisors
Examiners
Available from: 2011-09-06 Created: 2011-09-06 Last updated: 2011-09-06Bibliographically approved

Open Access in DiVA

fulltext(1307 kB)874 downloads
File information
File name FULLTEXT01.pdfFile size 1307 kBChecksum SHA-512
a23700aa833df205c9367a1e5c43b5d1aef8d7620316ef17e414ceb4cf579921d3aecea69c5d3b75ab232ac000c415977259a6f3dbef5cef3c408b8331d496ec
Type fulltextMimetype application/pdf

By organisation
ESLAB - Embedded Systems Laboratory
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 874 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 242 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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