Parallelization of the Kalman filter for multi-output systems on multicore platforms

Abstract: 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.