  We develop a novel parallel resampling algorithm for fully parallelized
particle filters, which is designed with GPUs (graphics processing units) or
similar parallel computing devices in mind. With our new algorithm, a full
cycle of particle filtering (computing the value of the likelihood for each
particle, constructing the cumulative distribution function (CDF) for
resampling, resampling the particles with the CDF, and propagating new
particles for the next cycle) can be executed in a massively and completely
parallel manner. One of the advantages of our algorithm is that every single
numerical computation or memory access related to the particle filtering is
executed solely inside the GPU in parallel, and no data transfer between the
GPU's device memory and the CPU's host memory occurs unless for further
processing, so that it can circumvent the limited memory bandwidth between the
GPU and the CPU. To demonstrate the advantage of our parallel algorithm, we
conducted a Monte Carlo experiment in which we apply the parallel algorithm as
well as conventional sequential algorithms for estimation of a simple state
space model via particle learning, and compare them in terms of execution time.
The results show that the parallel algorithm is far superior to the sequential
algorithm.
