A Shared Memory Based Parallel Hierarchical Interest Matching Algorithm

doi:10.16182/j.issn1004731x.joss.20-0019

Abstract

Abstract: Interest matching plays an important role in distributed simulation. However, because of huge number of simulation entities and frequent change of regions, interest matching consumes tremendous computation in large scale simulations. The ubiquity of multicore urges us to improve the performance of interest matching by parallelization. A shared memory based parallel hierarchical interest matching algorithm is propose to solve the problem. It maps subscribe regions into a full binary tree, and compares update regions with the tree in parallel. Due to the associative relationship between adjacent nodes, unnecessary comparisons can be eliminated. The experimental results demonstrate that the proposed algorithm has good scalability and can effectively improve the efficiency of interest matching.

Key words: interest matching, parallel algorithm, distributed simulation, sort-based matching

CLC Number:

TP391.9

Tang Wenjie, Cheng Junwei, Yao Yiping, Zhu Feng. A Shared Memory Based Parallel Hierarchical Interest Matching Algorithm[J]. Journal of System Simulation, 2021, 33(5): 1086-1094.

References

[1] IEEE Standard for Modeling and Simulation (M&S) High Level Architecture (HLA)[S]. IEEE Std1516-2010 (Revision of IEEE Std 1516-2000).
[2] Sarbazi-Azad H, Zomaya A Y.Data Distribution Management[M]. Large Scale Network- Centric Distributed Systems. Hoboken, NJ: IEEE, 2014: 103-122.
[3] Tan G, Zhang Y S, Ayani R.A hybrid Approach to Data Distribution Management[C]// Proceedings 4th IEEE International Workshop on Distributed Simulation and Real-Time Applications (DS-RT 2000). Piscataway, NJ: IEEE, 2000: 55-61.
[4] Boukerche A, Roy A.Dynamic Grid-based Approach to Data Distribution Management[J]. Journal of Parallel and Distributed Computing (S0743-7315), 2002, 62(3): 366-392.
[5] Raczy C, Tan G, Yu J.A Sort-based DDM Matching Algorithm for HLA[J]. ACM Transactions on Modeling and Computer Simulation (S1049-3301), 2005, 15(1): 14-38.
[6] Pan K, Turner S J, Cai W, et al.A Dynamic Sort-based DDM Matching Algorithm for HLA Applications[J]. ACM Transactions on Modeling and Computer Simulation (S1049-3301), 2011, 21(3): 1-17.
[7] Li T, Yao Y, Tang W, et al.An Exponential Search Enhanced Dynamic Sort-based Interest Matching Algorithm for Interest Management in Distributed Simulation[J]. Simulation Modelling Practice and Theory (S1569-190X), 2019, 95: 78-95.
[8] Li T, Tang W, Yao Y, et al.A Sort-based Interest Matching Algorithm with Two Exclusive Judging Conditions for Region Overlap[C]// 2018 Winter Simulation Conference (WSC). Piscataway, NJ: IEEE, 2018: 2167-2178.
[9] 梁洪波, 朱卫国, 姚益平, 等. 一种面向大规模HLA仿真的并行区域匹配算法[J]. 国防科技大学学报, 2013, 35(3): 84-91.
Liang Hongbo, Zhu Weiguo, Yao Yiping, et al.A Parallel Region Matching Algorithm for Large Scale HLA Simulation[J]. Journal of National University of Defense Technology, 2013, 35(3): 84-91.
[10] Marzolla M, D’angelo G, Mandrioli M.A Parallel Data Distribution Management Algorithm[C]// 2013 IEEE/ACM 17th International Symposium on Distributed Simulation and Real Time Applications. Piscataway, NJ: IEEE, 2013: 145-152.
[11] Liu Y, Sun H, Fan W, et al.A Parallel Matching Algorithm Based on Order Relation for HLA Data Distribution Management[J]. International Journal of Modeling, Simulation, and Scientific Computing (S1793-9623), 2015, 6(2): 1540002.
[12] Guan S, De Grande R E, Boukerche A. A Multi-layered Scheme for Distributed Simulations on the Cloud Environment[J]. IEEE Transactions on Cloud Computing (S2168-7161), 2015, 7(1): 5-18.
[13] Nägele T, Hooman J.Scalability Analysis of Cloud-based Distributed Simulations of IoT Systems Using HLA[C]// 2018 IEEE 24th International Conference on Parallel and Distributed Systems (ICPADS). Piscataway, NJ: IEEE, 2018: 1075-1080.
[14] 李伯虎, 林廷宇, 贾政轩, 等. 智能工业系统智慧云设计技术[J]. 计算机集成制造系统, 2019, 25(12): 3090-3102.
Li Bohu, Lin Tingyu, Jia Zhengxuan, et al.Smart Cloud Design Technology Applied to Intelligent Industrial System[J]. Computer Integrated Manufacturing Systems, 2019, 25(12): 3090-3102.