Parallelizing Kalman Filters

submited by

Style Pass

2024-10-12 04:30:34

Parallel scan or the Associative scan algorithm is a popular parallel computing technique that is used to parallelize sequential algorithms using the associative property of that algorithm. This technique is a generalization of the earlier and much more popular prefix sum algorithm (summing operation is associative).

Consider a sequential algorithm A\mathcal A A that runs in O(N)\mathcal O(N) O ( N ) . By definition, at each step tt t , the computation ata_t a t depends on the previous result at−1a_{t-1} a t − 1 through some associative operation ⊗\otimes ⊗ . The set of all the prefix-sums for NN N steps is therefore

Many common operations are associative like addition, subtraction, maximum, minimum, and so on. The parallel computation of the above generalized prefix-sum is called the scan operation [1]. A prefix-scan algorithm taken in an array a1,a2,…,aNa_1,a_2, \ldots, a_N a 1 , a 2 , … , a N and computes the array a1,(a1⊗a2),…,(a1⊗⋯⊗aN)a_1, (a_1 \otimes a_2), \ldots ,(a_1 \otimes \cdots \otimes a_N) a 1 , ( a 1 ⊗ a 2 ) , … , ( a 1 ⊗ ⋯ ⊗ a N )

For our purposes, by parallelization we really mean a SIMD implementation - where the same operation is carried over different data points in parallel. This is also called vectorization in practice. The parallel prefix-sum is, thus, a vectorized cumulative sum algorithm.