《计算机应用研究》|Application Research of Computers

GPU加速的差分进化粒子滤波算法

Speeding up differential evolution particle filter algorithm by GPU

免费全文下载 (已被下载 次)  
获取PDF全文
作者 曹洁,黄开杰,王进花
机构 兰州理工大学 a.计算机与通信学院;b.电气工程与信息工程学院,兰州 730050
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2018)07-1965-05
DOI 10.3969/j.issn.1001-3695.2018.07.009
摘要 为了解决实时系统中粒子滤波的计算复杂性问题,提出了一种零bank冲突并行规约的差分进化粒子滤波方法。该方法首先分析了并行差分进化粒子滤波算法在GPU中的内存访问模式,根据粒子滤波器的均方根误差与内存访问bank(存储体)冲突度成正比的关系,提出了一种去除bank冲突的有填充寻址的差分进化粒子滤波算法,降低了计算复杂度。将该算法在NVIDIA GTX960 GPU中实现,与串行差分进化粒子滤波算法进行比较。实验表明,随着粒子数增加,计算量以指数增加,采用GPU加速的跟踪算法的执行时间明显减少,有效提高了跟踪精度,降低了计算时间。
关键词 GPU;粒子滤波;差分进化;并行规约;零内存访问冲突
基金项目 国家自然科学基金资助项目(61633031)
甘肃省自然科学基金资助项目(1506RJZA105)
本文URL http://www.arocmag.com/article/01-2018-07-009.html
英文标题 Speeding up differential evolution particle filter algorithm by GPU
作者英文名 Cao Jie, Huang Kaijie, Wang Jinhua
机构英文名 a.CollegeofComputer&Communication,b.CollegeofElectrical&InformationEngineering,LanzhouUniversityofTechnology,Lanzhou730050,China
英文摘要 This paper proposed a differential evolution particle filter method based on parallel protocol of zero bank conflict, in order to solve the computational complexity of particle filtering in real-time systems. Firstly it analysed the memory access mode of parallel differential evolution particle filter algorithm in GPU.Then according to the relationship that the root mean square error was proportional to the degree of bank conflicts in memory access, it proposed a differential evolution particle filter with filled addressing mode to remove bank conflict, which reduced the computational complexity. It implemented the algorithm in NVIDIA GTX960 GPU, and compared with the serial differential evolution particle filter algorithm. As the number of particles increases, the amount of calculation increases exponentially. Theoretical analysis and simulation results show that the tracking algorithm using GPU acceleration is significantly reduced the execution time. It improves the tracking accuracy and reduces the computation effectively.
英文关键词 GPU; particle filter; differential evolution(DE); parallel protocol; bank conflicts free
参考文献 查看稿件参考文献
  [1] Sileshi B G, Oliver J, Toledo R, et al. Particle filter SLAM on FPGA:a case study on Robot@Factory competition[C] //Proc of the 2nd Iberian Robotics Conference. Berlin:Springer International Publishing, 2016.
[2] Pardal P C P M, Kuga H K, De Moraes R V. The particle filter sample impoverishment problem in the orbit determination application[M] //Mathematical Problems in Engineering. 2015:1-9.
[3] Malarvezhi P, Kumar R. Particle filter with novel resampling algorithm:a diversity enhanced particle filter[J] . Wireless Personal Communications, 2015, 84(4):3171-3177.
[4] 余春超, 杨智雄, 夏宗泽, 等. 采用GPU并行架构的基于互信息和粒子群算法的异源图像配准[J] . 红外技术, 2016, 38(11):938-946.
[5] Li Hongwei, Wang Jun, Su Hongtao. Improved particle filter based on differential evolution[J] . Electronics Letters, 2011, 47(19):1078-1079.
[6] 孙伟平, 向杰, 陈加忠, 等. 基于GPU的粒子滤波并行算法[J] . 华中科技大学学报:自然科学版, 2011, 39(5):63-66.
[7] 刘光敏, 陈庆奎, 赵海燕, 等. 一种GPU加速的粒子滤波算法[J] . 计算机科学, 2014(Z11).
[8] Murray L M, Lee A, Jacob P E. Parallel resampling in the particle filter[J] . Journal of Computational & Graphical Statistics, 2013, 25(3):789-805.
[9] 赵嵩, 徐彦, 曹海旺, 等. GPU并行实现多特征融合粒子滤波目标跟踪算法[J] . 微电子学与计算机, 2015, 32(9):153-156, 160.
[10] 刘伟, 孟朝晖, 薛东伟. 基于CUDA与粒子滤波的多特征融合视频目标跟踪算法[J] . 计算机系统应用, 2013, 22(11):123-128.
[11] 武勇, 王俊, 曹运合, 等. 基于二次预测的粒子滤波算法[J] . 吉林大学学报:工学版, 2015, 45(5):1696-1701.
[12] 张硕, 何发智, 周毅, 等. 基于自适应线程束的GPU并行粒子群优化算法[J] . 计算机应用, 2016, 36(12):3274-3279.
[13] 余莹, 李肯立, 郑光勇. 一种基于GPU集群的深度优先并行算法设计与实现[J] . 计算机科学, 2015, 42(1):82-85.
[14] Padua D. All prefix sums[M] // Encyclopedia of Parallel Computing. 2011.
[15] Nakano K. An optimal parallel prefix-sums algorithm on the memory machine models for GPUs[C] //Proc of the 12th International Conference on Algorithms and Architectures for Parallel Processing. 2012:99-113
收稿日期 2017/3/3
修回日期 2017/4/10
页码 1965-1969
中图分类号 TP301.6
文献标志码 A