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
GPU Implementation of the Particle Filter
Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.ORCID iD: 0000-0002-4865-6397
2013 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
GPU implementation av partikelfiltret (Swedish)
Abstract [en]

This thesis work analyses the obstacles faced when adapting the particle filtering algorithm to run on massively parallel compute architectures. Graphics processing units are one example of massively parallel compute architectures which allow for the developer to distribute computational load over hundreds or thousands of processor cores. This thesis studies an implementation written for NVIDIA GeForce GPUs, yielding varying speed ups, up to 3000% in some cases, when compared to the equivalent algorithm performed on CPU.

The particle filter, also known in the literature as sequential Monte-Carlo methods, is an algorithm used for signal processing when the system generating the signals has a highly nonlinear behaviour or non-Gaussian noise distributions where a Kalman filter and its extended variants are not effective. The particle filter was chosen as a good candidate for parallelisation because of its inherently parallel nature. There are, however, several steps of the classic formulation where computations are dependent on other computations in the same step which requires them to be run in sequence instead of in parallel. To avoid these difficulties alternative ways of computing the results must be used, such as parallel scan operations and scatter/gather methods.

Another area where parallel programming still is not widespread is the area of pseudo-random number generation. Pseudo-random numbers are required by the algorithm to simulate the process noise as well as for avoiding the particle depletion problem using a resampling step. In this thesis a recently published counter-based pseudo-random number generator is used.

Place, publisher, year, edition, pages
2013. , 72 p.
Keyword [en]
GPGPU, Particle filtering, CUDA, Sequential Monte Carlo, C++
National Category
Signal Processing
Identifiers
URN: urn:nbn:se:liu:diva-94190ISRN: LiTH-ISY-EX--13/4698--SEOAI: oai:DiVA.org:liu-94190DiVA: diva2:630500
Subject / course
Electrical Engineering
Presentation
2013-06-14, Algoritmen, Linköpings Universitet, Campus Valla, Linköping, 10:15 (Swedish)
Supervisors
Examiners
Available from: 2013-06-19 Created: 2013-06-18 Last updated: 2013-06-20Bibliographically approved

Open Access in DiVA

Thesis report(6218 kB)2073 downloads
File information
File name FULLTEXT01.pdfFile size 6218 kBChecksum SHA-512
8f7e6db78ab28315deb11a3eb1877ed70b71bf420b519e288512cbb5b891f62fc35e9c035ccaa8a73bbbfa685c1e07de8f30068dec9b7cdbc237a82330358c72
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Gebart, Joakim
By organisation
Automatic ControlThe Institute of Technology
Signal Processing

Search outside of DiVA

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