一种基于共享存储的并行层次兴趣匹配算法

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

系统仿真学报 ›› 2021, Vol. 33 ›› Issue (5): 1086-1094.doi: 10.16182/j.issn1004731x.joss.20-0019

一种基于共享存储的并行层次兴趣匹配算法

唐文杰, 程俊玮, 姚益平^*, 朱峰

国防科技大学系统工程学院,湖南长沙 410073

收稿日期:2020-01-07 修回日期:2020-04-20 出版日期:2021-05-18 发布日期:2021-06-09
作者简介:唐文杰(1984-),男,博士,副教授,研究方向为复杂系统建模与高性能仿真。E-mail: tangwenjie@nudt.edu.cn
基金资助:
国家自然科学基金(61702527,61903368)

A Shared Memory Based Parallel Hierarchical Interest Matching Algorithm

Tang Wenjie, Cheng Junwei, Yao Yiping^*, Zhu Feng

College of Systems Engineering, National University of Defense Technology, Changsha 410073, China

Received:2020-01-07 Revised:2020-04-20 Online:2021-05-18 Published:2021-06-09

摘要/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

中图分类号:

TP391.9

唐文杰, 程俊玮, 姚益平, 朱峰. 一种基于共享存储的并行层次兴趣匹配算法[J]. 系统仿真学报, 2021, 33(5): 1086-1094.

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.

参考文献

[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.

一种基于共享存储的并行层次兴趣匹配算法

A Shared Memory Based Parallel Hierarchical Interest Matching Algorithm

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

本文评价

[1]	李宏宏, 康凤举. 基于改进B树的多层次仿真系统搜索算法[J]. 系统仿真学报, 2017, 29(2): 332-336.
[2]	张运银, 刘春光, 马晓军, 廖自力. 装甲车辆电传动系统实时仿真平台构建[J]. 系统仿真学报, 2017, 29(1): 107-114.
[3]	王石, 郭建文, 江务学, 曹文梁. 微细电火花加工中材料蚀除机理的仿真研究[J]. 系统仿真学报, 2015, 27(12): 2891-2897.