Top

The Journal of Supercomputing

Published in:

28-09-2022

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

Authors: Kaiyi Zhao, Li Li, Zeqiu Chen, Jiayao Li, Ruizhi Sun, Gang Yuan

Published in: The Journal of Supercomputing | Issue 4/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

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 \(\left( r-1\right) \times 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 \(\frac{(r-1)2^{n}}{\lceil log_2 r \rceil }\), thereby reducing the time complexity of Dempster’s rule effectively.

previous article Representation of gene regulation networks by hypothesis logic-based Boolean systems

next article The analysis of agricultural Internet of things product marketing by deep learning

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Buwei W, Jianfeng C, Bo W, Shuanglei F (2018) A solar power prediction using support vector machines based on multi-source data fusion. In: 2018 International Conference on Power System Technology (POWERCON). 10.1109/POWERCON.2018.8601672

Redfern S, Olson JB, Lundquist JK, Clack CTM (2019) Incorporation of the rotor-equivalent wind speed into the weather research and forecasting model’s wind farm parameterization. Monthly Weather Rev 147(3):1029–1046. https://doi.org/10.1175/MWR-D-18-0194.1CrossRef

Duan Z, Wu T, Guo S, Shao T, Malekian R, Li Z (2018) Development and trend of condition monitoring and fault diagnosis of multi-sensors information fusion for rolling bearings: a review. Inter J Adv Manufact Technol. https://doi.org/10.1007/s00170-017-1474-8CrossRef

Khoshro KMS (2010) Fault detection and diagnosis of an industrial steam turbine using fusion of svm (support vector machine) and anfis (adaptive neuro-fuzzy inference system) classifiers. Energy. https://doi.org/10.1016/j.energy.2010.06.001CrossRef

Tianyu C, Tingli N, Xin N, Yingchu S, Xuezhi Y, Liangxiao M (2018) Application of traditional Chinese medicine four-diagnostic auxiliary apparatus in evaluation of health status and clinical treatment. J Traditional Chinese Med 38(3):447–451. https://doi.org/10.1016/S0254-6272(18)30637-XCrossRef

Zhou T, Thung KH, Zhu X, Shen D (2018) Effective feature learning and fusion of multimodality data using stage-wise deep neural network for dementia diagnosis. Hum Brain Mapp. https://doi.org/10.1002/hbm.24428CrossRef

Honarmandi P, Duong TC, Ghoreishi SF, Allaire D, Arroyave R (2019) Bayesian uncertainty quantification and information fusion in calphad-based thermodynamic modeling. Acta Materialia 164:636–647. https://doi.org/10.1016/j.actamat.2018.11.007CrossRef

Liu X, Ngai ECH, Liu J (2020) Secure information fusion using local posterior for distributed cyber-physical systems. IEEE Transact Mobile Comput. https://doi.org/10.1109/TMC.2020.2969352CrossRef

Liu L, Zuo ZT, Wang YZ, Xu FR (2020) A fast multi-source information fusion strategy based on ftir spectroscopy for geographical authentication of wild gentiana rigescens. Microchem J. https://doi.org/10.1016/j.microc.2020.105360CrossRef

10.

Dubois D, Prade H (2001) Possibility theory, probability theory and multiple-valued logics: A clarification. Annal Math Artif Intell 32(1–4):35–66. https://doi.org/10.1023/A:1016740830286CrossRefMATH

11.

Dempster AP (1967) Upper and lower probabilities included by a multivalued mapping. Annals Math Stats 38(2):325–339. https://doi.org/10.1016/S1474-6670(17)62022-6CrossRefMATH

12.

Inglis J (1976) A mathematical theory of evidence. Technometrics 20(1):106–106. https://doi.org/10.1080/00401706.1978.10489628CrossRef

13.

Broemeling Lyle D (2011) An account of early statistical inference in arab cryptology. American Statian 65(4):255–257. https://doi.org/10.1198/tas.2011.10191CrossRef

14.

Zadeh LA (1965) Fuzzy sets. Information and Control 8(3):338–353. https://doi.org/10.1016/S0019-9958(65)90241-XCrossRefMATH

15.

Pawlak Z (1997) Rough sets, 3–7. https://doi.org/10.1007/978-1-4613-1461-5_1

16.

Kaijuan Y, Fuyuan X, Liguo F, Bingyi K, Yong D (2016) Modeling sensor reliability in fault diagnosis based on evidence theory. Sensors 16(1):113. https://doi.org/10.3390/s16010113CrossRef

17.

Xiao F (2018) Multi-sensor data fusion based on the belief divergence measure of evidences and the belief entropy. Inform Fusion. https://doi.org/10.1016/j.inffus.2018.04.003CrossRef

18.

Pan Y, Zhang L, Wu X, Skibniewski MJ (2020) Multi-classifier information fusion in risk analysis. Inform Fusion. https://doi.org/10.1016/j.inffus.2020.02.003CrossRef

19.

Barnett JA (2008) Computational methods for a mathematical theory of evidence. In: Yager, R.R., Liu, L. (eds.) Classic Works of the Dempster-Shafer Theory of Belief Functions, pp. 197–216. Springer, Berlin, Heidelberg

20.

Shenoy PP (1997) Binary join trees for computing marginals in the shenoy-shafer architecture. International Journal of Approximate Reasoning 17(2):239–263. https://doi.org/10.1016/S0888-613X(97)89135-9. Uncertainty in AI (UAI’96) Conference

21.

Shafer G, Logan R (1987) Implementing dempster’s rule for hierarchical evidence. Artif Intell 33(3):271–298. https://doi.org/10.1016/0004-3702(87)90040-3CrossRefMATH

22.

Benalla M, Boujemâa A, Hrimech H (2020) Improving driver assistance in intelligent transportation systems: An agent-based evidential reasoning approach. J adv transport 2020. https://doi.org/10.1155/2020/4607858

23.

Tessem B (1993) Tessem, b.: Approximations for efficient computation in the theory of evidence. Artif. Intell 61(2), 315–329. Artif Intell. 61:315–329. https://doi.org/10.1016/0004-3702(93)90072-J

24.

Benalla M, Achchab B, Hrimech H (2021) On the computational complexity of dempster’s rule of combination, a parallel computing approach. J Comput Sci 50:101283. https://doi.org/10.1016/j.jocs.2020.101283CrossRef

25.

Wu Q, Chen Y, Wilson JP, Liu X, Li H (2019) An effective parallelization algorithm for dem generalization based on cuda. Environ Model &Soft. https://doi.org/10.1016/j.envsoft.2019.01.002CrossRef

26.

Daniluk P, Firlik G, Lesyng B (2019) Implementation of a maximum clique search procedure on cuda. J Heuristics 25(2):247–271. https://doi.org/10.1007/s10732-018-9393-xCrossRef

27.

Sandric I, Ionita C, Chitu Z, Dardala M, Irimia R, Furtuna FT (2019) Using cuda to accelerate uncertainty propagation modelling for landslide susceptibility assessment. Environ Modelling Soft 115(MAY):176–186. https://doi.org/10.1016/j.envsoft.2019.02.016CrossRef

28.

Khaleghzadeh H, Zhong Z, Reddy R, Lastovetsky A (2018) Out-of-core implementation for accelerator kernels on heterogeneous clouds. J Supercomput 74(2):551–568. https://doi.org/10.1007/s11227-017-2141-4CrossRef

29.

Xu J, Liu W, Wang J, Liu L, Zhang J (2017) An efficient implementation of 3d high-resolution imaging for large-scale seismic data with gpu/cpu heterogeneous parallel computing. Comput & Geosci. https://doi.org/10.1016/j.cageo.2017.11.020CrossRef

30.

de la Asunción M, Mantas JM, Castro MJ, Fernández-Nieto ED (2012) An mpi-cuda implementation of an improved roe method for two-layer shallow water systems. J Parallel Distributed Comput 72(9):1065–1072. https://doi.org/10.1016/j.jpdc.2011.07.012.

31.

Bak S, Kim P, Park S (2022) Development of a parallel cuda algorithm for solving 3d guiding center problems. Comput Phys Communicat 276:108331. https://doi.org/10.1016/j.cpc.2022.108331CrossRef

32.

Rico N, Troiano L, Díaz I (2021) An efficient computation of dempster-shafer theory of evidence based on native gpu implementation. In: Denœux T, Lefèvre E, Liu Z, Pichon F (eds) Belief Funct: Theory Appl. Springer, Cham, pp 291–299CrossRef

33.

Zhao K, Li L, Chen Z, Sun R, Yuan G, Li J (2022) A survey: Optimization and applications of evidence fusion algorithm based on dempster-shafer theory. Appl Soft Comput. https://doi.org/10.1016/j.asoc.2022.109075CrossRef

34.

KlCkner A, Pinto N, Lee Y, Catanzaro B, Ivanov P, Fasih A (2012) Pycuda and pyopencl: a scripting-based approach to gpu run-time code generation. Parallel Comput 38(3):157–174. https://doi.org/10.1016/j.parco.2011.09.001CrossRef

Title: An efficient parallelization method of Dempster–Shafer evidence theory based on CUDA
Authors: Kaiyi Zhao
Li Li
Zeqiu Chen
Jiayao Li
Ruizhi Sun
Gang Yuan
Publication date: 28-09-2022
Publisher: Springer US
Published in: The Journal of Supercomputing / Issue 4/2023
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-022-04810-y

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 4/2023

Computer vision-based deep learning for supervising excavator operations and measuring real-time earthwork productivity

A sliced architecture using novel configurable logic modules in quantum dot cellular automata for application of field-programmable gate arrays

Evaluation of e-learners’ concentration using recurrent neural networks

Task offloading for edge computing in industrial Internet with joint data compression and security protection

IoT-fog-based healthcare 4.0 system using blockchain technology

The analysis of agricultural Internet of things product marketing by deep learning

Premium Partner