针对EM(Expectation Maximization)波形分解算法具有多次迭代和大量乘、除、累加等高密集运算的特点,提出一套将EM算法在通用计算图形处理器GPGPU上并行化的方案。针对通用并行计算架构CUDA的存储层次特点,设计总体的并行方案,充分挖掘共享存储器、纹理存储器的高速访存的潜能;根据波形采样值采用字节存储的特征,利用波形采样值的直方图求取中位数,从而降低求噪音阈值的计算复杂度;最后,采用求和规约的并行策略提高EM算法迭代过程中大量累加的计算效率。实验结果表明,当设置合理的并行参数、EM迭代次数大于16次、数据量大于64 M时,与单核CPU处理相比,GPU的加速比达到了8,能够显著地提高全波形分解的效率。

An objective in the field of EM-based wave decomposition when dealing with full-wave LiDAR data is to improve the processing efficiency. We proposed a method that parallels the EM algorithm on GPGPU.(1)Considering CUDA memory hierarchy that can access shared memory and texture memory with high speed, we designed an overall parallel framework.(2)A median can be obtained from the histogram of the waveform sampling values that are stored in bytes to reduce the complexity of noise threshold calculation.(3)A parallel strategy for summation was applied to improve the accumulation efficiency during the EM iterative process. Results indicated that the GPU speed ratio using the proposed method can reach 8 when meet the following conditions:(1)Proper parallel parameter setting;(2)EM iteration number is larger than 16;(3)Data size is larger than 64 MB. Therefore, the processing efficiency of full-wave decomposition can be significantly improved under the GPU parallel computing framework.