面向复杂系统应用的并行离散事件仿真性能优化技术研究

发布时间：2020-07-10 21:23

【摘要】：仿真技术已成为研究复杂系统的重要手段,而随着复杂性科学研究的快速发展,复杂系统仿真规模越来越大,个体模型复杂度越来越高,使得大规模复杂系统仿真对计算资源的需求不断增加,如何缩短大规模复杂系统仿真的运行时间,满足复杂系统研究对时效性的需求,是一个亟待研究的问题。近年来,将时间离散的复杂系统模型映射到并行离散事件仿真中的逻辑进程范型上,利用并行离散事件仿真技术提高复杂系统仿真的运行效率已成为解决上述问题的一个重要研究方向。然而,由于复杂系统仿真应用具有交互结构复杂、动态性、个体多样性等特点,使得目前的并行离散事件仿真技术难以充分挖掘复杂系统仿真应用的并行性,从而导致其运行性能不理想。因此,开展面向复杂系统应用的并行离散事件仿真性能优化技术研究,对于提高复杂系统仿真运行效率,提升复杂系统研究能力,适应国民经济和国防建设不断发展的应用需求具有重要的理论意义和实用价值。论文针对复杂系统仿真应用的相关特性,以进一步提高复杂系统仿真应用运行效率为根本目标,围绕负载划分、仿真时间同步、兴趣管理等影响并行离散事件仿真性能的关键问题展开研究,论文的主要创新点如下: (1)提出了一种面向具有无标度特性交互结构的非均匀静态负载划分算法。由于背景负载等因素的影响,静态负载划分往往需要根据实际可用计算资源非均匀分配仿真任务,而现有主流的面向无标度交互结构的基于赋权图多层k划分的静态负载划分算法主要基于递归二分的划分思想,难以适应计算负载非均匀划分的需求。针对上述问题,论文提出了一个基于集散节点聚合的负载划分算法HAPart,该算法将静态负载划分优化问题转换为一个二部图最小代价赋值问题,从而能够根据实际可用计算资源情况对仿真任务进行非均匀划分;理论证明该算法在解决赋权图非均匀k划分这一NP难问题时,获得了小于3的近似率,且时间复杂度不超过O((k!+1)?kn)(n为顶点个数,k为划分数),实验结果表明HAPart算法相比现有算法平均提高约19%的仿真运行性能。 (2)提出了一种乐观时间同步机制下负载划分动态优化算法。现有乐观时间同步机制下负载划分动态优化研究往往分别考虑计算负载平衡和通信优化,难以取得理想的整体优化效果。针对上述问题,论文基于赋权图k划分的动态负载划分模型,提出了一种基于启发式局部搜索策略的增量式迁移算法ALSPart,该算法首先根据计算负载和可用计算资源的变化情况对当前的负载划分进行调整,在此基础上通过顶点集合交换的图划分算法对通信负载进行优化,从而在综合考虑计算负载平衡和通信开销优化的前提下,尽量减少迁移开销;实验结果表明该动态负载划分算法相比现有相关算法平均减少约38%的回滚开销,从而可有效提高仿真系统总体性能。 (3)提出了一种基于社区发现的混合时间同步算法。复杂系统仿真中个体的多样性导致单纯使用乐观或是保守时间同步机制都难以得到较好的运行性能。针对该问题,论文结合混合时间同步协议框架,提出了一种基于社区发现的混合时间同步算法HCDSyn,该算法首先通过随机游走过程发掘逻辑进程交互网络中的社区结构,然后根据逻辑进程在社区中的位置为其自动选择恰当的同步机制,从而能在充分发掘系统并行性的同时有效减少系统中级联回滚的发生;实验结果表明该混合时间同步算法相对单纯的保守或乐观时间同步算法平均提升约10%的整体性能。 (4)提出了一种多维空间中基于历史信息的动态区域匹配算法。在个体兴趣域动态改变的情况下,直接匹配算法和基于分类的匹配算法匹配速度较慢,而基于网格划分的匹配算法无法兼顾匹配速度和匹配精度。针对该问题,论文提出了一种多维空间中基于历史信息的动态区域匹配算法HIMat,利用位向量表快速确定各维度上相对位置变化的范围以减少需要进行匹配的候选区域,进而通过与存储相交历史信息的二进制位矩阵进行位操作得到变化后各区域的匹配关系,从而提高匹配效率;该算法匹配计算量小于等于O ( d*k)(d为空间维度,k为变化区域所经过的平均区域界点个数),实验结果表明在通常只有部分兴趣区域发生变化的条件下,HIMat算法明显优于直接区域匹配算法和基于分类的区域匹配算法,而与采用稀疏网格的网格法性能接近,但采用稀疏网格的网格法过滤效果差,存在虚假连接,HIMat算法则实现了精确匹配。在上述研究成果的基础上,论文结合课题组研制的YH-SUPE并行离散事件仿真引擎设计实现了一个面向复杂系统应用的开放式并行离散事件仿真框架;并通过突发公共事件条件下的民意趋势模型对其进行了综合测试,结果表明论文所提出的优化技术可使得整体仿真系统平均获得约35%的性能提高。
【学位授予单位】：国防科学技术大学
【学位级别】：博士
【学位授予年份】：2011
【分类号】：N945.13

【相似文献】