Change search
ReferencesLink to record
Permanent link

Direct link
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
URN: urn:nbn:se:liu:diva-94190ISRN: LiTH-ISY-EX--13/4698--SEOAI: diva2:630500
Subject / course
Electrical Engineering
2013-06-14, Algoritmen, Linköpings Universitet, Campus Valla, Linköping, 10:15 (Swedish)
Available from: 2013-06-19 Created: 2013-06-18 Last updated: 2013-06-20Bibliographically approved

Open Access in DiVA

Thesis report(6218 kB)1448 downloads
File information
File name FULLTEXT01.pdfFile size 6218 kBChecksum SHA-512
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: 1448 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: 468 hits
ReferencesLink to record
Permanent link

Direct link