An efficient parallelization method of Dempster-Shafer evidence theory based on CUDA

The Dempster-Shafer (D-S) evidence theory is effective for uncertain reasoning; it does not require advanced information. The theory has been widely used in multi-sensor data fusion. However, the time complexity of fusing r pieces of evidence for n possible events using Dempster's combination rule is (r - 1) x 2(2n+1), which is considerable. In addition, none of the existing implementations of Dempster's rule directly utilize the parallel performance of GPUs. In this study, an efficient parallelization method for implementing the D-S evidence theory, based on event-based binary encoding and kernel functions on GPUs, was developed. Theoretical analysis and simulation experiments show that the proposed method achieves a speedup of (r-1)2(n)/inverted right perpendicularlog(2) rinverted left perpendicular, thereby reducing the time complexity of Dempster's rule effectively.