uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Parallelization of the Kalman filter for multi-output systems on multicore platforms
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Systems and Control.
2012 (English)Independent thesis Advanced level (professional degree), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

The Kalman filter is a very commonly used signal processing tool for estimating state variables from noisy observations in linear systems. Because of its cubic complexity, it is motivated to search for more computationally efficient Kalman filter implementations.

In this thesis work, previous attempts of parallelizing the Kalman filter have been investigated to determine whether any of them could run efficiently on modern multi-core computers. Two of the most interesting methods from a multi-core perspective have undergone further analysis to study how they perform in a multi-core environment. In the analysis, both state estimation accuracy and algorithm speedup have been considered.

The experiment results indicate that one of the evaluated algorithms, denoted the Fusion Gain method in this report, is faster on a quad-core CPU than a straight-forward implementation of the original Kalman filter when the number of output signals is large. It should be noted, however, that this algorithm is not identical to the true Kalman filter due to an approximation used in the derivation of the method. Despite this detail, it might still be of use in some applications where speed is more important than accurate state estimates.

The other evaluated method is based upon a fast Givens rotation. It was originally implemented on a so-called systolic array, which makes use of parallelism differently than multi-core computers. Unfortunately, this algorithm turned out to run very slow in the benchmarks even though the number of floating-point operations per second (FLOPS) should be far less than many of the other methods according to the theoretical analysis. More attention could be devoted to this implementation to locate possible bottlenecks.

Place, publisher, year, edition, pages
2012. , 53 p.
UPTEC F, ISSN 1401-5757 ; 12025
National Category
Information Systems
URN: urn:nbn:se:uu:diva-205553OAI: oai:DiVA.org:uu-205553DiVA: diva2:641881
Educational program
Master Programme in Engineering Physics
Available from: 2013-09-03 Created: 2013-08-19 Last updated: 2013-09-03Bibliographically approved

Open Access in DiVA

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

By organisation
Division of Systems and Control
Information Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 481 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: 220 hits
ReferencesLink to record
Permanent link

Direct link