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