liu.seSearch for publications in DiVA
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Accelerating the knapsack problem on GPUs
Linköpings universitet, Institutionen för datavetenskap, ESLAB - Laboratoriet för inbyggda system.
2011 (engelsk)Independent thesis Advanced level (degree of Master (Two Years)), 30 poäng / 45 hpOppgave
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.

sted, utgiver, år, opplag, sider
2011. , s. 87
Emneord [en]
gpgpu, knapsack, parallel computing
HSV kategori
Identifikatorer
URN: urn:nbn:se:liu:diva-70406ISRN: LIU-IDA/LITH-EX-A--11/029--SEOAI: oai:DiVA.org:liu-70406DiVA, id: diva2:439054
Fag / kurs
Computer and information science at the Institute of Technology
Presentation
2011-08-24, 13:00 (engelsk)
Uppsök
Technology
Veileder
Examiner
Tilgjengelig fra: 2011-09-06 Laget: 2011-09-06 Sist oppdatert: 2018-01-12bibliografisk kontrollert

Open Access i DiVA

fulltext(1307 kB)1116 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 1307 kBChecksum SHA-512
a23700aa833df205c9367a1e5c43b5d1aef8d7620316ef17e414ceb4cf579921d3aecea69c5d3b75ab232ac000c415977259a6f3dbef5cef3c408b8331d496ec
Type fulltextMimetype application/pdf

Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 1117 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

urn-nbn

Altmetric

urn-nbn
Totalt: 371 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf