社会网络仿真时间同步监管策略范文

Chandy－Misra－Bryant算法是应用最为广泛的保守时间管理算法，该算法通过比较所有逻辑进程的本地虚拟（LocalVirtualTime，简称LVT）来保持全局因果序一致，同时通过发送空消息（NullMessage）来避免死锁；Chandy和Misra在文献中提出的两段（Two－Phase）保守时间管理算法则通过搜索全局最小时戳事件来避免死锁。TimeWarp乐观时间管理算法最早提出了乱序事件处理发掘系统并行性，同时通过回滚保持事件因果序的思想。Steinman则在TimeWarp时间管理算法的基础上对节点间消息发送方式进行限制，提出了呼吸时间桶算法，减少了级联回滚带来的额外开销。

保守和乐观同步策略各有优劣，在复杂应用背景下，仿真开发人员往往难以确定一种合适的时间管理策略，因此从上世纪末开始，研究者试图通过结合两种策略的优势来获取更好的整体性能。目前，这类研究主要分为以下两个方向：（1）一部分研究者认为保守策略在事件处理的限制上过于严格，导致过多的CPU空转；而乐观策略则过于放松，导致了额外的回滚开销，因此希望通过对两者的折衷来减少额外同步开销。Xu和McGinnis提出optimistic－conservative算法将乐观事件处理机制引入保守时间管理算法，以发掘更多的系统并行性；Sokol等人提出的MovingTimeWindow算法和Ball等人提出的Adap－tiveTimeWarp算法则是在乐观时间管理算法中加入一定限制，减少整体回滚次数。（2）另一部分研究者则提出混合时间管理协议，在仿真系统中同时支持保守和乐观时间管理策略，甚至允许在运行时自由切换，从而最大限度地根据应用特征优化系统的性能。李宏亮等提出的一种层次的、混合并行离散事件仿真算法将整个系统分为多个组，组内采用保守策略，组间采用乐观策略。Rajaei等人提出的LocalTimeWarp算法则将仿真应用分为两个层次，底层采用乐观策略发掘系统并行性，而在上层采用保守策略限制回滚。这两个算法适用于实体间交互特征相对稳定的仿真应用，但由于不支持运行时切换时间管理策略，限制了对动态性较强的仿真应用的支持。

Jha和Bagrodia提出的混合策略框架则支持在逻辑进程的粒度上自由选择保守和乐观时间管理策略，同时支持运行时切换时间管理策略，具有较广的适用范围。混合时间管理协议由于能更好地根据应用特征优化系统性能，已应用到多个领域，正逐渐成为研究的热点。混合时间管理协议研究的最主要问题是如何根据应用特征来指定逻辑进程所采用的时间管理策略。据笔者所知，本文是第一次将混合时间管理协议运用到社会网络仿真领域，并根据社会网络仿真中社区结构对仿真性能进行优化的研究。

混合时间管理同步协议

本文采用的混合时间管理同步协议参考了Jha和Bagrodia提出的混合策略框架，其基本思路是将整个时间管理系统分为两个部分：全局控制部分（GlobalControlMechanism，简称GCM）和局部控制部分（LocalControlMechanism，简称LCM）。为描述方便，这里为每个逻辑进程设置两个基本数据结构：（1）事件队列FEL：存储所有未处理的事件，队列按时戳升序排列。Tf表示队列中的最小时戳，如果队列为空，则Tf为无穷大。（2）逻辑进程状态项集SL：该集合由逻辑进程L的所有状态项S［n］组成，每个状态项是一个五元组〈t，I（t），S（t），O（t），c〉，其中，t表示仿真时间，I（t）表示输入事件，S（t）表示t时刻逻辑进程状态，O（t）表示处理后的输出事件集，c为loo－kahead。SL中所有状态项按仿真时间t升序排列，设共有n＋1个项，则S［0］表示最新的已提交状态，S［n］表示最新修改的状态。全局控制部分主要负责全局时间同步、I／O处理和内存管理等工作，其中全局时间同步是时间管理的关键部分，其具体工作是计算每个逻辑进程未来可能处理事件的最小时戳（EarliestInputTime，简称EIT）。该值在保守时间管理机制中做为下界时戳（LowerBoundTimeStamp，简称LBTS）使用，而在乐观时间管理机制中做为全局虚拟时钟（GlobalVirtualTime，简称GTV）使用。计算EIT时，可以选用已有LTBS栅栏算法和GVT算法。局部控制部分主要负责控制逻辑进程采用不同的策略处理相关事件。在逻辑进程采用乐观策略时，允许逻辑进程任意处理到达事件，并通过回滚机制保证因果序一致。如果Tf＞S［n］．t，则表示事件处理时序正确，令I表示最小时戳事件，〈S（t′），O（t′），c〉＝process（S［n］．S（t），I），将O（t′）事件集发送出去，将S［n＋1］：〈Tf，I，S（t′），O（t′），c〉加入到状态记录集；如果Tf＜S［n］．t，则表示事件处理出现乱序需要回滚，找到最大的i，使得Tf＞S［i］．t，回滚到S［i］，将相关事件重新加入到事件队列，重复处理；同时，依据EIT来回收用于存储状态的资源。在逻辑进程采用保守策略时，只允许逻辑进程处理时间戳小于EIT的事件，因此不用保存过多的状态。令〈S（t′），O（t′），c〉＝process（S［n］．S（t），I），将O（t′）事件集发送出去。将S［n＋1］：〈t′，I，S（t′），O（t′），c〉加入到状态集，并删除S［n］。全局控制部分和局部控制部分功能相对独立，逻辑进程可以自由地选用支持不同时间策略的LCM。当逻辑进程需要运行时动态切换时，采用保守策略的逻辑进程可直接进行乐观处理；而由乐观策略向保守策略转化时，有两种转化方法：（1）直接回滚到S［0］，将所有时戳t＞S［0］．t的事件重新加入到事件队列中，状态集只留下S［0］，处理模式由乐观转化为保守。（2）选择性回滚：等待EIT到达S［n］．t，在状态集中只留下S［n］，处理模式由乐观转化为保守；如果事件队列中出现Tf＜S［n］．t，则先使用乐观LCM后半段回滚到Tf，在完成上述操作后转换为保守策略。

基于社区发现的时间管理策略优化设置

社区结构是社会网络的一个显著的拓扑特征，绝大部分的社会网络都是由一些内部结构紧密的社区组成，在一些文献中也称之为聚集性（Clustering）或模块性（Modularity）。社区可以非形式化地定义为社会网络中一系列个体的集合，集合内部个体连接紧密，集合间个体连接稀疏。目前，业界还未形成统一的社区数学描述，其中应用最为广泛的是plantedl－partition模型，该模型为社会网络中的每个个体定义pin和pout两个连接概率，当pin＞pout时则判定该个体属于某一社区。

由于社会网络仿真中存在大量社会各异个体，即使是同一社区中的个体的行为模型也可能存在较大差异，因而难以提取合适的Lookahead以保证保守策略的高效运行，需要采用乐观策略来提高运行效率；而社区结构却对乐观策略的运行效率提出了挑战，社区结构内个体连接紧密，个体间交互频繁，单个个体回滚容易引起社区内关联个体回滚；如果由于关联个体的回滚引起其他社区内个体回滚，则可能导致回滚影响在社区间不断传播，形成系统级的回滚风暴，从而极大地影响整体性能。

因此，面向社会网络仿真的混合时间管理算法需要解决以下两方面的问题：一方面需要尽可能多选取逻辑进程采用乐观策略，以减少个体行为模型差异所带来的空转等待；另一方面通过指定关键通信节点采用保守策略以限制级联回滚的可能性。基于社区发现的混合时间管理策略优化设置思想如图1和图2所示。整个算法主要包含两部分：（1）通过社区发现算法挖掘出社会网络中的社区结构。图1b则显示了图1a所示网络示例通过社区发现算法所得到的社区划分。（2）对社区内的节点进行分析，找到社区间通信的关键节点，将这些节点设置为保守策略以限制回滚在社区间的传播，同时将社区内其他节点设置为乐观策略。图2显示了对图1b各社区的设置。本文采用由Rosvall和Bergstrom提出的In－fomap社区发现算法来挖掘社会网络中的社区结构。

该算法将社区发现问题转化为一个网络结构信息压缩优化问题，即如何最有效地对网络结构进行编码，一方面使得压缩比率尽可能高，另一方面通过该压缩编码还原的网络结构尽可能贴近原有网络结构。算法中采用随机游走（RandomWalk）动态过程来获取压缩编码，并通过随机游走动态过程的最小描述长度（MinimumDescriptionLength）作为评估函数来优化编码，而最优的编码可对应得到最终社区划分。该算法具有社区划分结果优、运行效率高的特点，文献通过对比测试，认为该算法是目前整体性能最优的社区发现算法。

完成社区划分后，逐个分析各个社区内的节点，如果存在与其他社区节点的连接，则将该节点设置为保守策略，否则将该节点设置为乐观策略。设置后系统仿真时间同步可等效分为两个层次：社区内节点时间同步采用基于TimeWarp同步协议的乐观时间管理算法，社区间时间同步则基于保守时间管理策略。设置为保守策略的社区间连接节点作为各个社区的网关，其主要功能包括：（1）参与全局EIT计算；（2）根据全局EIT处理该节点相关事件，并直接调度社区内节点事件；（3）缓存社区间调度事件，将安全的事件调度消息发往其他社区目标节点。设置为乐观策略的社区内部节点处理相关事件则不受EIT的限制，以减少处理器空转等待；而由于社区间连接节点采用保守策略，其乐观处理的不安全事件不会影响到其他社区，因而，当某一社区内节点回滚时，其影响仅限于本社区内，避免出现系统级联回滚。根据上述思想，基于社区发现的混合时间管理策略优化设置启发式算法描述如下：设｜E｜表示网络的边数，Infomap社区发现算法的算法时间复杂度为O（｜E｜），对社区内节点分析算法时间复杂度为O（2｜E｜），则上述启发式算法时间复杂度为O（3｜E｜）。

实验结果与分析

PHOLD测试模型［23］是目前并行仿真领域广泛使用的标准测试程序。本文实验采用基于PHOLD测试模型的社会网络交互测试用例，其基本描述如下：实验仿真系统由N个社会网络个体构成，每个网络个体映射到一个逻辑进程上，负责存储个体状态和处理相关事件，逻辑进程通过事件调度与网络中相邻的逻辑进程进行交互；系统中设置M（M＜N）个初始事件，随机调度到M个逻辑进程上；当一个逻辑进程接受一个事件后，则随机选择网络中相邻的一个逻辑进程，调度该逻辑进程上未来的一个事件；事件调度时间间隔由调度者lookahead决定。实验采用的网络结构基于Barabási和Albert提出的BA模型生成。本次实验参数设置如表1所示。实验仿真软件平台为乔治亚理工学院（Geor－giaInstituteofTechnology）开发的开源并行离散事件仿真平台μsik；硬件环境为4计算节点Linux集群系统，每个计算节点包含两个主频2．53GHzQuadCoreXeon处理器，主存8GB操作系统为KylinServer3．1，GCC版本为4．1．2。

实验结果如图3所示。由测试结果可以看出，在计算资源固定的条件下，在整体负载较轻时，采用乐观策略能减少空转等待，平均性能要优于保守算法，但随着负载的增加，回滚带来的额外开销越来越大，乐观机制性能下降较快，在重负载下保守策略平均性能较优。混合策略时间管理算法则整体性能稳定，对负载不敏感，具有良好的可扩展性；在负载适中时，平均性能优于单纯的乐观和保守策略。

结束语

利用并行仿真技术以满足社会网络仿真对计算资源的需求是当前研究的趋势，而仿真时间同步机制是决定并行仿真性能的重要因素。社会网络仿真中个体间行为模式差异较大，难以提取合适的Lookahead以保证保守策略的高效运行；同时，社会网络仿真中个体交互情况复杂，采用乐观策略时，容易引起系统内大量级联回滚，因此传统粗粒度的保守或乐观时间管理算法都无法适应社会网络仿真的需求。本文提出一种基于社区发现的混合时间管理机制，在仿真系统中同时支持保守和乐观时间管理策略，允许在逻辑进程的粒度上自由选择保守和乐观时间管理策略，并根据社会网络中社区结构特性优化设置逻辑进程所采用的时间管理策略，从而最大限度地发掘系统的性能，同时减少级联回滚的风险。实验结果证明了该算法的有效性。

作者：张颖星姚益平单位：国防科学技术大学计算机学院