计算机生成兵力模型的实时调度技术

吴雨淋，龚光红，李妮

(北京航空航天大学 自动化科学与电气工程学院，北京100191)

计算机生成兵力(CGF)代表了虚拟的作战人员、装备及单位在虚拟的战场上进行交互，可用于军事训练、装备效能评估等目的.CGF的实时运行是保障仿真结果可信的一个重要条件.当前不断增长的仿真规模和逼真度为CGF模型的实时调度带来了挑战.

与CGF实时性相关的研究包括3个方面:①实时运行支撑环境(RTI).CGF系统一般基于高层体系结构［1］(HLA)标准，RTI是该标准的实现，其性能对系统实时性具有重要影响.国内外近十年来对RTI的实时性进行了大量研究，主要有:减小网络延迟与服务开销、扩展传输规范以支持Qos、优化时间管理、使用负载平衡技术等［2-7］.最新的HLA Evolved标准引入了数据智能更新速率降低、自定义传输类型等特性［1］，也有助于提高RTI的实时性.实时RTI已经用于连接模拟器的实时仿真中［8］.②RTI应用的优化.文献［9］使用多联邦桥接实现并行加速从而改进实时性.文献［10］使用变步长技术来实时推进仿真时间，但存在步长难以估计和开销大的问题.文献［11］使用外部节点来管理时间，以避免RTI时间管理带来的性能瓶颈，但事件因果关系难以保证.文献［12］针对特定RTI优化了Tick操作来保证实时性.③模型的实时调度.调度是对模型执行进行合理安排以满足其截止期要求，可分为静态和动态两类:前者指在运行前就安排好运行时刻表，后者指在运行时动态确定需要执行的模型，例如最早截止期算法(EDF)将具有最早截止期的任务赋予最高优先级.EDF是最常使用的实时调度算法［13］，并且针对不同应用得到了优化［13-14］.最近有研究［15］将EDF直接应用到HLA环境，但并不针对CGF应用，性能也未经过验证.

新一代的CGF采用组装和复用技术来支持模型的快速开发，例如美军的OneSAF［16］.这时模型被构建为独立的组件，可作为传统实时系统中的任务来调度.这样的CGF具有如下特点:①仿真实体由多个模型组装而成，例如坦克包含机动、探测、毁伤等模型;②部分模型按周期执行，这类模型通常使用了系统中大部分的计算资源;③仿真想定设定了初始的实体集合，该集合在仿真过程中会发生变化;④实体内部采用不跨越网络的高效通讯机制，因此把实体作为仿真节点的分配单位，而把模型作为节点内的处理器调度单位.

本文主要研究模型实时调度问题，以及引入RTI后必须考虑的时间推进问题.RTI的逻辑时间和仿真步长概念为调度施加了限制.本文主要贡献在于提出了将时间推进和模型调度过程分离的框架，并设计了基于步长的负载平衡的静态调度算法，从而获得良好的实时性和调度性能.

1 调度框架

1.1 现有的实时推进方法

实时仿真是指仿真系统推进仿真时间使其与自然时间保持1∶1的关系.HLA使用时间管理概念来保证仿真事件的因果顺序.它要求仿真成员在推进逻辑时间前先发出请求，并判断推进时间安全后才予以批准.下式给出了判断方法:

其中，j是除i以外的其他盟员;Tj是j的当前逻辑时间或请求推进时间;Lj是设置的时间前瞻量;Gi是盟员i的当前最大安全推进时间.

图1表示了目前工程实践中主要采用的基于步长的实时推进方法［6］.其中，“同步”用于请求时间推进并等待所有盟员时间一致，“时间补偿”则与自然时间进行对照，等待步长Δt到期后启动下一步长.与自然时间均匀流逝不同，在每个步长内仿真时间均相同并等于该步长开始的时刻.

图1 基于高层体系结构(HLA)的实时推进Fig.1 Advancement with real-time based on high level architecture(HLA)

这种方法通过测试和统计手段来调整可用资源，使得每一步长有较充足的补偿时间.其优点是保证了事件因果顺序，然而根据式(1)可知，时间推进速度取决于最慢的节点，一旦某节点出现偶然的过载，就会引起整个系统的时间滞后.

1.2 改进的独立时间推进方法

上述方法是串行化的，时间同步和模型处理依次进行.为解决上述问题，图2给出了改进的仿真框架.其特点是:①引入模型调度过程;②将时间推进与模型的调度及运行分离(图中分别由步骤1.x和2.x表示)并采用独立线程并行处理;③逻辑时间的推进由物理时间周期性驱动.

图2 计算机生成兵力(CGF)实时调度框架Fig.2 Real-time scheduling framework of computer generated forces(CGF)

在多线程环境下，偶然的过载可能导致步骤2.4发生在步骤1.2和1.5之间，这时待发送数据的时戳值滞后，进而可能引起错误.图2中的RTI服务代理用于串行化RTI调用，因此能够发现这种问题，它允许用户根据需要采取丢弃数据、为数据增加时戳值或者报错等策略.

2 仿真模型的调度

2.1 调度问题的描述

设有模型集合 S={M1，M2，…，Mn}，运行周期分别是 T1，T2，…，Tn，最坏执行时间是 C1，C2，…，Cn，这里只考虑由仿真节点上的单一线程调度并执行模型的情况，因此模型Mi(i=1，2，…，n)在运行过程中不允许被抢占.对于多核环境，可以将模型集合划分为多个子集，每个子集使用单独线程调度.

定义1 模型集合的处理器利用率(负载)为

公理1 在单处理器上，模型集合满足可调度的必要条件是U≤1.在m个相同的处理器上，模型集合满足可调度的必要条件是U≤m.

在工程实际中还要考虑系统其他功能的开销，它取决于操作系统、RTI、CGF引擎、调度算法等各种因素，因此并不能达到最大的处理器利用率.具体开销可由实验统计获得.

定理1 在单处理器上，模型集合可实时调度的必要条件是min(Ti)≥Tstep＞max(Ci).这里，Tstep是仿真步长，在每个步长里可调度多个模型.

证明 用反证法.首先，如果min(Ti)＜Tstep，则在Tstep时间内具有min(Ti)的模型至少应执行2次，而根据步长概念，在连续的Tstep自然时间内逻辑时间是相同的，因此在此期间无法为该模型调度2次，从而该集合无法调度.其次，如果Tstep≤max(Ci)，那么当具有max(Ci)的模型被执行时，它将跨越2个连续步长，导致了1次执行却拥有2种逻辑时间，因此该集合无法调度. 证毕

由于上述可调度条件均是必要条件，而充分条件取决于具体的调度算法，不一定能简单描述，因此后文介绍具体算法时将对不可调度的情况进行排除.为了高效调度，本文将不同模型的运行周期Ti对齐，为此做以下约束:

2.2 调度策略

为了减少运行过程中动态调度产生的额外开销，同时使得系统具有更好的预测性，这里采用静态调度的方案，即预先安排好每步长应执行的模型.调度过程采用负载均衡的原则:各个节点的运算量相当，各个步长的运算量相当.其原因有:①更容易压缩时间以实现超实时仿真，因为能压缩的程度受限于负载最大的步长;②更容易调度仿真运行中新创建的模型，减少因某一步长负载过高而需要重新调度其他模型的情况;③尽可能为每一步长都能保留一定的空余，应对偶然的过载.

2.3 调度算法

依据上述策略，设计了负载均衡实时调度算法(LBRS)，包括3个阶段:为仿真实体分配节点;产生各节点的调度计划表;在运行时调整调度表.

2.3.1 节点分配

仿真实体是节点分配的基本单位.分配目标是使得各节点的模型总运算量相当，算法如下:

1)设有N个实体，第i个实体有n(i)个模型.按式(2)计算每个实体的处理器利用率Ui，并从大到小排序形成待分配队列;

2)设有m个节点，将各节点的空闲率idle初始化为1;

3)取下实体队列的首个实体i，将其分配给空闲率最大的节点 r，更新空闲率为 idler=idler－Ui;

4)重复步骤3)，直到待分配实体链表为空.如果出现某个节点的空闲率小于0，则表示资源不足，应停止分配并增加仿真节点.

2.3.2 产生调度表

设某节点共分配了n个模型，这些模型共使用了s(s≤n)种不同的运行周期，从小到大依次为 T1，T2，…，Ts.由式(3)可知，Tj/Ti=2t，其中1≤i≤j≤s，t=0，1，2，….由此易证，每隔 Ts的时间，调度结果是重复的，称 Ts为调度周期.记TotalSteps=Ts/Tstep，表示一个调度周期内的步长总数.调度算法如下.

1)将调度周期内各个步长的空闲率初始化为 1，即 idlek=1，1≤k≤TotalSteps.

2)按从小到大的顺序遍历 T1，T2，…，Ts，执行以下步骤:

① 计算 L=Ti/Tstep，1≤i≤s，L 表示 Ti内包含的步长数;

② 创建Ti内各步长的调度表Tableij，0≤j＜L，调度表用来存放模型;

③将运行周期为Ti的所有模型按执行时间从大到小排序形成队列，遍历队列执行以下步骤;

④选择从idle1到idleL中的最大值，设其下标为r;

⑤将当前模型分配给第r个步长，记录在Tableir中;

⑥设当前被调度模型的执行时间为C，更新该步长和后续受影响步长的空闲率，即idler+L×l=idler+L×l－ C/Tstep，其中 0≤l＜ Ts/Ti.当空闲率小于0时，则表示该算法无法调度，需停止分配并增加资源.

调度表是负载均衡的，即模型计算量被均匀地分摊到每个步长.证明:①当调度最小运行周期T1时，每次均选择T1内最大空闲的步长，因此T1内是均衡的，且由于T1之后的步长均重复T1，因此整个调度表是平衡的;②不失一般性，设调度完周期为 Tk的模型后，调度表是平衡的;③由式(3)可知，Tk+1/Tk=2t(t＞0)，由于Tk平衡并且重复，所以Tk×2t=Tk+1也是平衡且重复的;④现在开始调度周期为Tk+1的模型，同理，每次选择Tk+1内最大空闲的步长，Tk+1保持了平衡并且重复，因此整个调度表依然保持平衡;⑤依次类推，当周期为Ts时，得证.

在调度表创建后，运行时可以直接查表并执行.设仿真开始时刻为Ts0，当前时刻为Ts1.需要处理每一种运行周期Ti的调度表，按下式计算Ti当前应执行的步长号:

图3给出了一个调度实例.

图3 负载均衡实时调度算法(LBRS)调度实例Fig.3 An example of load balancing real-time scheduling(LBRS)

2.3.3 调度表的调整

运行时可能发生实体被销毁(例如车辆被击毁)或者产生新的实体(例如发射导弹)的情况，这时需要修改调度表.当被删除的模型集中于某一步长时，如果为新模型调度一个最空闲的步长可能反而导致后面某个步长的负载变为最高，因此难以进行全局调度.这时的调度问题可转化为局部调度问题:当所有的Ti局部负载平衡时，整个Ts也就基本达到负载平衡了.通过下式计算Ti的失衡程度:

其中，Lij表示Ti内第j步长的负载，等于Tableij中被分配模型的执行时间总和.

当删除实体时进行检测，如发现Bi超过失衡阈值时则在Ti内负载最高和负载最低步长对应的调度表之间迁移模型.新建实体时在选择负载最低的节点后再选择负载最低的步长.

3 实验分析

基于本文设计的独立时间推进方法和LBRS算法，构造了CGF仿真引擎，在KD-RTI环境下与传统串行时间推进方法和非抢占式的EDF调度算法进行了性能对比测试.实验中调度和运行了周期分别为 50，100，200，400，800 ms 的模型，模型的执行时间为0.2～2 ms的均匀分布(计算时间长的模型可分解为小模型)，系统步长为50ms.最大仿真步长设为1 200步.整个实验设置都满足可调度条件.为了模拟动态环境，50%的模型在仿真过程中被添加和删除，失衡阈值设置为2 ms.

3.1 实时性对比

为了体现偶然的过载对实时性的影响，在仿真进行到100步以后，测试程序在每步长随机增加了0～10 ms的延迟.表1给出了测试结果的一个片段(精确到ms).

表1 实时性测试结果Table1 Result of real time performance ms

由表1可见，LBRS能够较好地实现实时推进，出现1 ms的不同步是由于使用多媒体定时器引起的误差;而传统方法虽然采用了时间补偿技术(即当出现延迟时则适当减少下一步长大小)来减轻整体上的延迟累加现象，但局部延迟依然明显.这是由于本文方法使得时间推进只与物理时间有关，不受模型调度及运行的影响.LBRS使得各个步长留有一定的空余资源，并且在该实验条件下能够容纳延迟，因而未出现事件时戳滞后的现象.EDF算法尽可能利用当前可用的剩余资源，一旦在串行推进过程中发生延迟，并且有大量模型的截止期位于该步长时，就会造成过载，这时其他节点都必须等待其解算完成后才能进行同步.

3.2 算法开销对比

调度开销是指使用额外的处理器资源来确定需要执行的模型而不是用来执行模型本身.由于仿真节点之间进行负载平衡时的开销对于不同的模型调度算法是相同的，因此这里只对盟员内部的调度开销进行对比测试.图4是当模型数量增长时每秒钟调度开销的统计结果.

图4 负载均衡实时调度算法(LBRS)和最早截止期算法(EDF)调度开销对比Fig.4 Comparison of overhead between LBRS and EDF

由图4可以看到，EDF算法需要较大的开销，并且随模型数量增加而增长较快，而LBRS算法开销较小并且比较稳定.LBRS算法通过查表直接获取模型，因此其时间开销只与表的长度有关(每个子表内需要执行的模型可由式(4)直接计算得到)，即复杂度为O(s)，s是系统中不同模型周期类型的数量，该数量远远低于模型的数量.虽然模型的动态变化带来调度表的调整也需要额外资源，但实验结果表明这种开销很小，在实际中模型变化的频率将会更低，因而不会对算法性能带来较大影响.EDF则需要按截止期排序，一方面截止期通过动态计算得到，另一方面排序算法的时间复杂度通常为O(n lb n).因此随模型数量增长，开销将迅速增大.

3.3 处理器的最大利用率

处理器的最大利用率是衡量实时调度算法性能的一个重要参数，它决定了可调度的模型规模.EDF理论上能达到100%，但非抢占式环境以及系统开销会削弱其性能.该组实验采用试探法，即通过不断增加模型数量来寻找最大利用率，一旦超过该值后将会出现模型超出截止期以致调度失败.每次测试均在前面实验采用的初始模型集合基础上增加具有特定计算时间的模型(见图5).

图5 负载均衡实时调度算法(LBRS)和最早截止期算法(EDF)最大利用率对比Fig.5 Comparison of maximum processor utilization LBRS and EDF

从图5中可以看到EDF平均能达到95%左右的利用率，LBRS能超过85%.LBRS稍弱于EDF是因为EDF尽可能地利用当前剩余资源，而LBRS将空余资源均匀分散在每个步长导致了时间碎片，不利于调度计算时间长的模型.这也解释了对于图中执行时间为0.2 ms的模型LBRS具有更高的利用率，因为大量小的模型使得时间碎片得以利用，EDF则因为过多的模型导致了较大的调度开销.LBRS的性能完全可以满足CGF需要，它并没有浪费处理器，空余资源可以被引擎以及非周期模型所利用，在实际中还需要预留更多的资源.

4 结论

本文研究了RTI之上的CGF模型实时调度问题，在仿真时间实时推进的基础上，确保模型运行能够满足截止期要求.实验结果表明:

1)本文所用的时间推进方法在保留RTI时间管理服务的同时实现了良好的实时性.目前在军事仿真领域中RTI已经被广泛采用，对于许多应用尤其是人在回路的军事训练来说，实时性是最基本的要求，因此该方法具有潜在的应用价值.

2)本文所用调度算法具有较低并且稳定的开销，理论上能够满足单个节点可包含成百上千个模型的大规模仿真的需要.该算法还同时具有较高的处理器利用率，尤其适合于大量小模型.这符合大规模仿真的特点，因为如果单个模型运行时间过长，仿真规模将会降级.

针对本文未考虑的非周期性模型，可以与EDF算法相结合，并使用额外资源或者与LBRS算法按比例使用资源［15］的方式进行调度.

References)

［1］ IEEE Std 1516-2010 IEEE standard for modeling and simulation(M＆S)high level architecture(HLA)-framework and rules［S］.Piscataway，NJ:IEEE，2010:1-38.

［2］ d’Ausbourg B，Siron P，Noulard E，et al.Running real time distributed simulations under Linux and CERTI［C］//Simulation Interoperability Standards Organization-SISO European Simulation Interoperability Workshop，EURO SIW 2008.Orlando，FL:Simulation Interoperability Standards Organization，2008:355-363.

［3］ Chaudron E，Adelantado M，Noulard E，et al.HLA high performance and real-time simulation studies with CERTI［C］//ESM 2011-2011 European Simulation and Modelling Conference:Modelling and Simulation 2011.Portugal:EUROSIS，2011:69-75.

［4］ 翟永翠，程健庆.基于HLA的实时仿真研究［J］.系统仿真学报，2004，16(9):1966-1969.Zhai Y C，Cheng J Q.Researching of real-time simulation using HLA［J］.Journal of System Simulation，2004，16(9):1966-1969(in Chinese).

［5］ Adelantado M，Siron P，Chaudron J B.Towards an HLA run-time infrastructure with hard real-time capabilities［C］//International Simulation Multi-Conference.Donavan Drive Bedford，MA:Simulation Interoperability Standards Organization，2010:42-52.

［6］ Chaudron J B，Noulard E，Siron P.Design and modeling techniques for real-time RTI time management［C］//Spring Simulation Interoperability Workshop 2011，2011 Spring SIW.Donavan Drive Bedford，MA:Simulation Interoperability Standards Organization，2011:284-293.

［7］ Boukerche A，Shadid A，Zhang M.Efficient load balancing schemes for large-scale real-time HLA/RTI based distributed simulations［C］//Proceedings-IEEE International Symposium on Distributed Simulation and Real-Time Applications，DS-RT.Piscataway，NJ:IEEE，2007:103-112.

［8］ Gervais C，Chaudron J，Siron P，et al.Real-time distributed aircraft simulation through HLA［C］//Proceedings-IEEE International Symposium on Distributed Simulation and Real-Time Applications.Piscataway，NJ:IEEE，2012:251-254.

［9］ 李东，陈源龙，张达，等.HLA仿真系统实时性改进方法关键技术的分析［J］.哈尔滨工业大学学报，2013，45(3):70-75.Li D，Chen Y L，Zhang D，et al.Key technology of real time performance improvement of the simulation system based on HLA［J］.Journal of Harbin Institute of Technology，2013，45(3):70-75(in Chinese).

［10］ 李智，张恒源.HLA变步长实时仿真方法研究［J］.装备指挥技术学院学报，2009，20(2):106-110.Li Z，Zhang H Y.Research of hla real-time simulation method based on alterable time advance step［J］.Journal of the Academy of Equipment Command ＆ Technology，2009，20(2):106-110(in Chinese).

［11］ 梁彦刚，唐国金，王锋.基于HLA仿真系统的实时性改进策略研究［J］.系统仿真学报，2005，17(2):361-363.Liang Y G，Tang G J，Wang F.Research on strategy to improve real-time performance of HLA-based simulation system［J］.Journal of System Simulation，2005，17(2):361-363(in Chinese).

［12］ Malik A W，Khan S A，Hassan S R.An HLA based real time simulation engine for man-in-loop net centric system［J］.Pak J Engg ＆ Appl Sci，2010，7:47-54.

［13］ Stavrinides G L，Karatza H D.Scheduling multiple task graphs in heterogeneous distributed real-time systems by exploiting schedule holes with bin packing techniques［J］.Simulation Modelling Practice and Theory，2011，19(1):540-552.

［14］ 程禹，赵宏伟，龙曼丽，等.最早截止期优先调度算法的改进［J］.吉林大学学报:工学版，2013，43(5):1338-1342.Cheng Y，Zhao H W，Long M L，et al.Improvement of earliest deadline first scheduling algorithm［J］.Journal of Jilin University:Engineering and Technology Edition，2013，43(5):1338-1342(in Chinese).

［15］ 刘述田，戴树岭，张亚琳.HLA/RTI下周期与非周期任务调度的实时性改进［J］.北京航空航天大学学报，2014，40(1):110-114.Liu S T，Dai S L，Zhang Y L.Improvement of HLA/RTI realtime performance by scheduling periodic and aperiodic tasks［J］.Journal of Beijing University of Aeronautics and Astronautics，2014，40(1):110-114(in Chinese).

［16］ Parsons D，Surdu J R.The U.S.Army’s next generation simulation modelling the response to the world’s future threat［C］//NATO Modelling and Simulation Group Conference.Neuillysur-Seine，France:NATO-RTO，2005(19):1-14.