Non-coalesced Access Patterns of Global Memory Load Transactions in Metropolis Resampling Implemented on Graphics Processing Unit

Dulger O. , Oguztuzun H.

26th IEEE Signal Processing and Communications Applications Conference (SIU), İzmir, Türkiye, 2 - 05 Mayıs 2018 identifier identifier


Due to having many particles, the particle filter has high computational cost. Owing to many cores in its architecture, graphics processing unit (GPU) offers promising solutions. The resampling stage of the particle filter has long execution time because of interactions among the particles. As Metropolis resampling does not need collective operations on particles, it avoids the numerical instability problem and performs fast. However, reading the weights from the global memory becomes serial as the number of particles increases. This is because of non-coalesced global memory access patterns of the Metropolis resampling. We devised two variations of Metropolis, namely, Metropolis-C1 and Metropolis-C2, in our previous work to ameliorate this problem. In these techniques, we ensure that the threads in a warp access the same segments of the global memory. We gain up to 9.7x speed up with Metropolis-C1 and up to 5.5x speed up with Metropolis-C2. Moreover, the quality (root mean square error) results of Metropolis-C1 and Metropolis-C2 on a highly non-linear equation are similar to those of Metropolis. In this study, we investigate the impact of non-coalesced global memory access patterns on the speed of the Metropolis resampling by using the CUDA profiler. We show that the number of global memory load transactions reduces with Metropolis-C1 and Metropolis-C2 leading to shorter execution time of the resampling stage.