計算機生成兵力模型的實時調度技術

吳雨淋，龔光紅，李妮

(北京航空航天大學 自動化科學與電氣工程學院，北京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.