Architectures for Particle Filtering - Signal Processing Systems - page 631

Fig. 2 The operations that are performed by the PEs and by the CU. The data exchanged between
the PEs and the CU is also shown

Tabl e 1 Illustration of particle sharing modes

Mode Configuration Resampling algorithm Mode

0 Single PE Resampling algorithm with tagged particles 000

1 2-Fixed Only 2 PEs are used 001

2 2-2-Fixed 2 Separate particle filters each using 2 PEs 010 (2)

3 2-2-Fixed RNA without regrouping 011

4 2-2-Mixed RNA with regrouping with defined rules 100

5 2-2-Adaptive RNA with adaptive regrouping 101

6 4-Mixed RPA 111

The state update requires extensive data communication among the PEs and the
CU. In the example shown in Fig. 4 , a particle filter with P 16

particles is used. The particles and their weights are computed during the particle
generate and particle update steps. In this example, it happened that most of the
probability mass is contained in PE2. The normalized sums sum i for the PEs 1 to 4
are: 0, 13

= 4PEsand M =

16. In this example, the algorithm with proportional allocation
is used (RPA), so that each PE generates the number of particles as a result of
resampling proportional to its local sum. So, PE1 generates 0 replicated particles,
PE2 13 replicated particles and so on. It was shown in [ 25 ] that RPA produces the
same resampling result as the sequential resampling algorithms. In order to start the
next particle filtering iteration, the number of particles in each PE has to be the same,
namely four. So, PE2 has to send its particle surplus to the PEs 1, 3, and 4. The way
that it is done in RPA is shown in Fig. 5 a . It can be noticed from this example that
the communication pattern during the particle exchange is random. Namely, after
each particle filtering operation, it is not known which PE will have surplus and
which will lack particles. So, the direction and the amount of particles exchanged

/ 16, 0, 3 /