基于CUDA展开循环的并行差分进化粒子滤波算法

摘要

针对并行差分进化粒子滤波算法期间前缀和执行期间低规格效率的问题，提出了一种基于CUDA展开循环前缀的滤波算法，以去除并行前缀中存在的线程分化和线程冗余通过展开循环方法并展开线程束方法，优化周期，提高前缀和执行效率。通过引入并行策略，使用在算法更新期间使用改进的前缀和计算在GPU侧并行地实现差分进化粒子滤波算法。通过大数据分析，结果表明，该并行差分粒子滤波算法具有改进的前缀和规范，可以有效地改善非线性系统状态的差分进化粒子滤波，以及异构并行处理系统中的实时性能。

1.介绍

颗粒滤波是一种序贯的蒙特卡罗方法，该方法采用粒子以接近后验概率密度分布。在 [1]，将多智能协同进化机制引入到粒子滤波中，通过粒子之间的竞争、交叉、变异和自学习来实现重采样过程，有效解决了粒子退化和粒子稀缺性问题。文献[2]比较了不同搜索策略下粒子滤波的滤波精度，差分进化粒子滤波算法的精度得到了提高，但计算复杂度增加。为了解决计算复杂性问题，文献[3.- - - - - -5]提出了一种基于GPU的粒子滤波并行算法，该算法将传统的粒子滤波算法与GPU有效结合，充分利用GPU并行计算的性能，提高了粒子滤波算法的计算速度。文献[6，7]提出了一种基于gpu的粒子滤波并行优化设计与实现，以提高跟踪算法的计算速度。文献[8- - - - - -10]设计并实现了一种基于CUDA的并行粒子群优化算法，该算法使用大量的GPU线程来加快整个粒子群的收敛速度。上述文献采用并行规约算法进行并行粒子滤波算法，以简化线程操作。前缀和算法是并行算法编程的重要基元，是许多不同算法的基本模块。与串行算法相比，基于cuda的并行算法执行单指令的多线程命令，可以执行更多的操作，提高算法执行效率。但是，由于前缀和算法的执行模式和内存访问模式[11- - - - - -13]，执行过程中容易出现线程划分和内存访问冲突现象，不能有效利用GPU的硬件资源。前缀求和包含大量的重复操作，操作简单，效率低。分段前缀求和避免了线程重复，但存在严重的内存访问问题，GPU硬件资源利用率低。文献[14介绍了附加指令，并演示了它们在构建高效并行算法原语(如前缀和和分段二进制前缀和)中的应用。在文献[15]，研究人员使用并行分段前缀构建数据处理并对其进行优化，以提高算法的整体性能。在文献[16]，研究人员利用gpu和实际的并行粒子群井解决了设施位置奇异问题，证明了粒子群优化是一种灵活的优化技术。在文献[17]，对前缀和问题的几种树数据结构进行了研究，提供了各种实用的解，都获得了良好的加速因子。

为解决差分进化粒子滤波并行算法执行过程中的线程区分问题，基于CUDA架构，本文提出了一种基于展开循环前缀和优化的差分进化粒子滤波算法，消除了线程差异，减少了判断和分支预测造成的延迟，使得粒子滤波算法的计算性能逐步提高。

2.差分进化粒子滤波算法

差分进化算法(Differential evolutionary algorithm, DE)是一种随机并行直接搜索算法，其基本思想是从某个随机生成的初始种群开始，按照一定的操作规则连续迭代，并根据每个个体的适应度值，保留好个体，剔除劣个体，并引导搜索过程逼近最优解。该算法具有结构简单、易于实现、不需要梯度信息、参数较少等优点，并具有多种不同的搜索策略。

本文的DE-PF算法的计算过程如下。

步骤1。对于初始化步骤，采样是在同一时间执行的 ．由此产生的粒子作为初始样本，初始样本的分布是 ．所有粒子的初始权重都相同 ．重复迭代 ．

步骤2。对于预测步骤，设置 ，样品粒子通过当前时刻的状态转移模型，并计算当前的测度 ．

步骤3。权重被计算和标准化，并在收到步骤中的测量值后2，每个粒子需要根据似然函数更新权值 ： 归一化过程使粒子权重之和等于1，归一化过程表示为

步骤4。对于差异进化重采样，我们有以下几点:（1） ．进化的初始粒子 （2）对粒子集进行变异操作 ，然后执行交叉操作以获得候选粒子集（3）候选粒子集的适应度值，并进行选择操作，得到的粒子集为(4）如果 和 ，然后设置 ；转到步骤2；否则，执行下一步

第5步。按降序排列粒子。

步骤6。计算每个粒子被复制的次数，除了它自己。

第7步。计算步骤中权重的加权和4，除了它自己的。

第8步。清除小颗粒。

第9步。对于状态输出步长，使用优化的粒子集作为等权重的样本 ：

3.改进的并行前缀和

并行算法在进行计算时需要计算粒子的累积分布函数(cumulative distribution function, CDF)，这是一个简单的连续前缀和操作，具体描述如下: 在哪里 ， ，和是数据的大小吗 ．顺序计算非常简单，由于输出数据之间的依赖关系，使得并行化变得困难。对于小的前缀和问题，只使用一个线程块，用递归乘法来解决。然而，并行粒子滤波在粒子数量较大时，需要较长时间计算前缀和问题 ，和图1表示对不同粒子的相同操作，即前缀和的平行方式。

并行前缀和可以理解为对数组中所有数字求和的并行化过程。通常，并行化的思想是基于“树”的二进制法规，如图所示2和3.．并行前缀求和的实现可以分为两种类型:

(1)直接前缀和．元素与相邻元素配对求和

(2)交叉前缀和．根据给定的空间对元素进行配对

摘要针对交错前缀和算法并行操作中存在的空闲线程问题，提出了一种扩展循环前缀和方法，以减少空闲线程，提高前缀和的执行效率。

通过对交错前缀和方法的评估，stride的初始值为blockDim.x的一半。当 然后执行后续指令，这就意味着第一次迭代中有一半的线程是空闲的，这就浪费了GPU的计算资源，又产生了一个新的问题:空闲线程。如果能充分利用它们，并行算法的性能仍然可以得到提高，这也有待于下一步的优化和改进。

扩展循环是一种技术，旨在通过减少分支出现和循环维护指令的频率来优化环路。在循环扩展中，循环的主体在代码中多次写入，而不是仅仅使用循环的主体一次，然后使用另一个循环重复执行它。任何闭环都可以使其迭代次数减少或完全删除。环形主体的副本数被称为环形膨胀因子，迭代的数量变为循环膨胀因子的奇异次数。在顺序阵列中，循环扩展是当在执行循环之前已知循环的迭代次数的数量时，循环扩展是提高性能的最有效方法。假设线程块长度为1024，所涉及的规则迭代在512,256,128和64处的线程被分布在不同的线束中（因为每个扭曲只能同时执行32个线程）;然后，在这些线程束的SM执行中存在优先顺序，因此需要在块内同步的规定迭代的每个步骤。只有当法规迭代到32,16,8,4和2时，它们所在的线程束执行才与其他线程捆绑在一起，并且不需要互连同步，而在过程中的每个指令之后存在隐式同步SM中的线程包，因此可以解决内部垃圾同步问题，使与线程对应的全局数组在时间上更新，而不会影响下一个指令的执行。

在前面的前缀和计算中，每个线程块负责一个相应的数据块。现在，每个线程块负责前缀和计算两个数据块，从而消除了指令消耗，增加了更多独立指令的调度，以提高性能。下面是扩展因子为2和4的前缀和的示意图。有三种扩展规模，2、4、8，其中一个块分别计算2块、4块、8块数据，将相邻的数据块添加到当前线程块对应的数据块中，然后相加，列为table1- - - - - -3.．

并行前缀和方法算法强度较低，调度指令可能是系统的瓶颈。解决方案是展开for循环。__syncthreads用于块内同步。在法令内核函数中，它用来确保每一轮的所有线程在进入下一轮之前都已将其本地结果写入全局内存。在法令期间，活动线程的数量减少，当有少于32个活动线程时，我们将只有一个扭曲。在一个单一的过程中，指令的执行遵循SIMD(单指令多数据)模式;也就是说，当活动线程少于32个时，不需要同步控制，每条指令后面都有一个隐式的intrabundle同步进程。因此，有必要解决只有一个线程束时的循环控制和线程同步问题。在此基础上，提出了带交错前缀和的线程束展开方法。

通过前面的实验分析，展开了32个线程以下的迭代循环。事实上,由于线程块的长度限制(通常1024),确定循环的数量,所以循环可以充分展开,例如,1024年,512年,256年,128年和64年,和计算,唯一需要注意的是,每个计算应该是同步的。表格4显示了完全展开循环的伪代码。

4.实验与性能分析

为了验证的基本性能与改进的前缀和并行算法,算法的性能模拟使用典型的一维非线性系统模型并与并行前缀和基于循环展开,基于线程并行前缀和演变周期,以及基于全展开滤波算法的并行前缀和。实验平台包括Win10 64位系统、Visual Studio 2013编程软件和基于cuda9.2的编程框架，其中GPU为GTX1080Ti, CPU为i5-4460。具体参数如表所示5．

一维非线性系统模型如下:

系统噪声模型为 ，总观测时间为 ，交叉概率 ，最大进化时间为迭代次数 ．在本文中，我们在扩展环路的基础上使用并行前缀和扩展因子2,4,8 (2U-PRPDE-PF, 4U-PRPDE-PF, 8U-PRPDE-PF)。本文对PF、8U-PRPDE-PF、翘曲展开PRPDE-PF、完全展开PRPDE-PF三种算法进行了对比实验。

4．1.均方根误差的实验分析

对算法进行了仿真。 时的均方根误差定义为:

和表示当前的实际状态和预测状态在分别th模拟。测量噪声 ．数字4比较了两种粒子数设置时五种算法的瞬时均方根误差 和 ．

该算法的状态估计性能基本相同。从图中可以看出4在粒子数相同的实验条件下，2U-PRPDE-PF、4U-PRPDE-PF、8U-PRPDE-PF、WU-PRPDE-PF、CU-PRPDE-PF五种改进算法的均方误差相对于IIPRPDE-PF算法有所降低，并且这些方法都能保证状态估计能力，同时算法的精度得到一定程度的提高，说明改进的方法在一定程度上提高了滤波算法的状态跟踪性能。

4．2．粒子分布与计算时间实验

数据5和6基于展开周期显示60模拟时刻的展开周期，显示粒子数变化和改进的前缀和算法的计算时间的曲线。图中模拟曲线的比较5结果表明，2U-PRPDE-PF、4U-PRPDE-PF、8U-PRPDE-PF、WU-PRPDE-PF和CU-PRPDE-PF的粒子数逐渐减少，并随时间自适应调整。在图6,当时的时间可以看出,CU-PRPDE-PF低于其他过滤器由于执行全面展开,充分提高递归循环,增加了前缀和执行效率,即提高执行的重采样率和计算时间消耗,而2 u-prpde-pf, 4 u-prpde-pf,8U-PRPDE-PF、WU-PRPDE-PF小于IIPRPDE-PF，且有减小的趋势。

改进了重采样的递归循环后，自适应地减少了粒子，5个未展开循环后并行滤波算法的计算时间相对减少，小于IIPRPDE-PF。在重采样后展开递归循环,整个算法的复杂性增加,和递归抽样所需的时间来更新实时计算的粒子数是不足以抵消粒子的减少所节省的时间当粒子的数量很小,当所有展开环的并行差分进化粒子滤波器的计算时间小于相应的并行差分进化粒子滤波器时，这种情况就消失了，这也表明PRPDE-PF对展开循环的采样能更显著地提高计算时间。过滤器的计算时间如表所示6通过60个独立的蒙特卡罗实验获得，并以每个实验的每个过滤器的运行时间的平均值，可以看出Cu-PRPDE-PF需要最少的计算时间。结合每个滤波器的计算精度和计算时间的性能指标，完全展开的环路滤波器算法Cu-PRPDE-PF具有最少的计算时间，并且是本文五种改进的过滤算法中的最佳性能。

并与Wang等人的文章中提出的三种智能优化并行粒子滤波算法进行了比较[18]，本文改进算法(2U-PRPDE-PF、4U-PRPDE-PF)与块并行粒子智能优化粒子滤波算法的计算时间如表所示7,分别。由表可知，在三种智能优化并行算法中，分块并行粒子滤波算法分块并行CRPF的性能最好，其次是优化的分块并行算法;优化部分增加了算法的复杂度;与块并行算法相比，计算性能有所下降。本文提出的2U-PRPDE-PF算法和4U-PRPDE-PF算法分别与块并行算法进行了比较。从表7,结果表明,改进的2 u-prpde-pf本文算法具有较强的计算性能比块平行CRPF,并获得3.82倍的加速比随着粒子数的增长,和4 u-prpde-pf算法获得4.689倍的加速比粒子数量的增加渐近,因此，本文提出的算法在性能上有所提高，与分块并行算法相比，可以获得较好的加速比。

比较了五种并行差分进化粒子滤波算法2U-PRPDE-PF、4U-PRPDE-PF、8U-PRPDE-PF、woo - prpde - pf和CU-PRPDE-PF的运行情况，在相同的GPU情况下，采用改进的前缀和后改进的CUDA循环展开算法。表8和9分别给出了五种改进算法的运行调度和加速比，图7和8对应表8和9，其中加速比定义为相同粒子数条件下原算法运行时间除以改进算法运行时间得到的值。数字8原始算法IIPRPDE-PF的运算时间分别除以2U-PRPDE-PF、4U-PRPDE-PF、8U-PRPDE-PF、woo - prpde - pf、CU-PRPDE-PF的运算时间得到的值。CU-PRPDE-PF的加速比最大，随着粒子数的增加，加速比保持在1.19左右，而其他4种CU-PRPDE-PF、4U-PRPDE-PF、8U-PRPDE-PF和WU-PRPDE-PF的加速比随着粒子数的增加最终保持在一定值。在GTX1080Ti下，粒子数为1024;在展开因子为2、4、8的直接展开后，从39.2 ms到35.64 ms，可以看出直接循环展开对效率的影响非常大;这不仅是因为节省了额外的线程块运行，还因为改进有更多独立的内存加载，存储操作可以产生更好的性能，具有更好的隐藏延迟。对本文算法进行了增量改进，总体性能提高了1.19倍。

4．3．算法在不同gpu上的实时性

基于不同GPU条件，使用上述五种改进的算法进行实验模拟。整个实验平台包括Win10系统，Visual Studio 2013编程软件和基于CUDA9.2的编程框架，与I5-4460 CPU列为表10，在四个不同的gpu上运行算法，粒子数量来自来 ．

本文提出的五种改进算法在相同CPU和不同GPU条件下进行了性能实验。根据图中的分析9- - - - - -13，与IIPRPDE-PF算法相比，本文基于IIPRPDE-PF算法的循环展开算法2U-PRPDE-PF、4U-PRPDE-PF、8U-PRPDE-PF、WU-PRPDE-PF和CU-PRPDE-PF在不同gpu上的增长速度基本相同。讨论了算法在不同GPU条件下的加速比基本与GPU本身的计算能力成正比，在GPU GTX1080Ti的实验环境下，算法的性能最优。在本文中，GPU计算性能的提高仅限于改进的前缀和问题。基于直接分割前缀和改进的差分进化粒子滤波算法，CU-PRPDE-PF相对于IIPRPDE-PF算法的整体性能提升速度可达19%，CU-PRPDE-PF相对于原PDE-PR算法的性能提升因子可达1.45。改进后的算法性能提升有限的主要原因不仅仅是GPU上的简单并行，需要复杂的操作，甚至包含相当多的逻辑判断。但是，通过前缀和增量改进可以获得一些性能提升。

5.结论

在这篇文章中,针对并行执行线程并行差分进化粒子滤波效率低的问题，提出了一种基于CUDA展开循环的差分进化粒子滤波状态估计方法，并通过展开循环的前缀和方法提高了前缀和的执行效率还有一束线。该方法使用分段展开后循环前缀和改进的重采样和最新的观测时刻更新的建议分布实时优化的粒子滤波,自适应地调整粒子数的采样粒子滤波使用微分数量较小进化的重采样。另外，对于粒子滤波算法的执行，前缀和执行存在线程执行效率低的问题，GPU没有分支预测能力，在执行每一个分支时，因此，该算法通过展开循环和展开线程束方法消除了并行前缀中存在的线程束分化和线程空闲，消除了判断和分支预测失败造成的延迟，进一步提高了整体计算性能。目前的CUDA编译器不能为我们做这个优化，需要在内核函数内部人工展开循环，这可以极大地提高内核性能。在CUDA中展开循环的目的有两个:减少指令消耗，通过添加更多独立的调度指令来减少碎片，从而提高性能。仿真结果表明，采用该展开环的并行差分进化粒子滤波算法可以有效地提高智能最优粒子滤波对非线性系统状态和实时性的影响。 Finally, experimental simulations show that the algorithm with the improved prefix sum can achieve the best speedup factor of 1.19 relative to the IIPRPPDE-PF algorithm and 1.48 relative to the PDE-PF algorithm under GTX1080Ti, and the experimental data show that the overall performance of the algorithm under different GPUs is proportional to the GPU. The experimental data show that the overall performance of the algorithm under different GPUs is proportional to the GPU computational power, which indicates that the improved algorithm in this paper has universal applicability.

数据可用性

用于支持这项研究结果的数据包括在文章中。

的利益冲突

作者声明他们没有利益冲突。

参考文献

1. 闫明超，杨振宇，袁鑫，“基于GPU并行架构的互信息和粒子群算法的异构源图像对齐”，红外技术，卷。38，不。11，PP。938-946,2016。视图:谷歌学术
2. “基于差分进化的改进粒子滤波，”电子信件，第47卷，第47期。19, pp. 1078-1079, 2011。视图:出版商的网站|谷歌学术
3. S. W. X. J. C. Jiazhong和Y. Shengsheng“基于GPU的粒子滤波并行算法”华中科技大学学报(自然科学版)， vol. 5, pp. 63-66, 2011。视图:谷歌学术
4. S. K. Das, C. Mazumdar和K. Banerjee，“GPU加速的新型粒子滤波方法”，计算，第96卷，第2期8, pp. 749-773, 2014。视图:谷歌学术
5. L. M. MURRAY，A. LEE和P. E. JACOB，“粒子过滤器并行重新采样”，中国计算与图形统计学报，第25卷，第2期3, pp. 789-805, 2016。视图:出版商的网站|谷歌学术
6. V.P.Jilkov和J.Wu，“高效的GPU加速实施粒子和颗粒流动过滤器的目标跟踪”信息融合进展杂志，第10卷，第5期。1, pp. 73-88, 2015。视图:谷歌学术
7. 刘伟，“一种基于CUDA和粒子滤波的多特征融合视频目标跟踪算法”，计算机系统应用第22卷第2期11, pp. 123-128, 2013。视图:谷歌学术
8. S. Lalwani, H. Sharma, S. C. Satapathy, K. Deep, J. C. Bansal，“并行粒子群优化算法综述”，阿拉伯科学与工程杂志，第44卷，第5期。4, pp. 2899-2923, 2019。视图:出版商的网站|谷歌学术
9. F. Bourennani，“大维度问题的协同异步并行粒子群算法”，国际应用元启发式计算杂志，第10卷，第5期。3，页19-38,2019。视图:出版商的网站|谷歌学术
10. Lin X.， Wu Y.，“基于粒子群算法的光伏模型参数辨识，”能源《中华人民共和国刑法》，第196卷，第117054页，2020年。视图:出版商的网站|谷歌学术
11. 弗雷泽百货，使用并行前缀计算包含和排除的总和，博士论文，麻省理工学院，2020。
12. H. Tokura, T. Fujita, K. Nakano, Y. Ito, J. L. Bordim，“GPU上的几乎最优列前缀和计算”，超级计算杂志第74卷第1期4, pp. 1510-1521, 2018。视图:谷歌学术
13. G. Thakur, H. Sohal，和S. Jain，“一种用于优化Radix-2 FFT处理器的新型并行前缀加法器”，多维系统和信号处理，卷。3,2021。视图:谷歌学术
14. M. Harris和M. Garland，“为费米体系结构优化并行前缀操作”GPU计算宝石翡翠版，pp。29-38，摩根Kaufmann，2012年。视图:谷歌学术
15. A. Pîrjan，“分段求和算法函数的优化解决方案”，圆柱我们,2013年。视图:谷歌学术
16. E. Wynters，“并行粒子群优化可以在gpu上快速解决许多优化问题”，高校计算机科学学报第33卷第3期6, pp. 114-123, 2018。视图:谷歌学术
17. “大数据降维技术分析，一种新的基于PCA-whale优化的深度神经网络模型，用于番茄病害的GPU分类”。视图:谷歌学术
18. Wang j, Cao j, Li w, Yu p, Huang K.，“一种新的并行加速CRPF算法”，应用智能，第50卷，第5期。3, pp. 849-859, 2020。视图:出版商的网站|谷歌学术

版权

版权所有©2021黄凯杰、曹杰。这是一篇发布在知识共享署名许可协议，允许在任何媒介上不受限制地使用、传播和复制，但必须正确引用原作。