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

Direct link
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
URN: urn:nbn:se:liu:diva-70406ISRN: LIU-IDA/LITH-EX-A--11/029--SEOAI: diva2:439054
Subject / course
Computer and information science at the Institute of Technology
2011-08-24, 13:00 (English)
Available from: 2011-09-06 Created: 2011-09-06 Last updated: 2011-09-06Bibliographically approved

Open Access in DiVA

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

By organisation
ESLAB - Embedded Systems Laboratory
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 779 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

Total: 217 hits
ReferencesLink to record
Permanent link

Direct link