并行分布實時仿真平臺任務調(diào)度技術研究.pdf

1、隨著仿真應用的不斷深入，仿真規(guī)模正在逐步擴大，仿真模型越來越復雜，其對計算資源的要求也越來越高。特別是在實時仿真應用中，由于對時間約束的要求非常苛刻，其對處理平臺的計算性能提出了更高的要求。而一些大規(guī)模系統(tǒng)內(nèi)部往往存在一些并行因素，若能直接用分布、并行方法實現(xiàn)這部分的仿真當然就更符合系統(tǒng)的實際特征了，因此并行分布仿真逐漸成為實時仿真研究的焦點。然而，并行分布仿真有許多尚待解決的問題，其中任務調(diào)度是影響仿真系統(tǒng)運行性能和效率的關鍵因素之一

2、，不恰當?shù)恼{(diào)度不僅不會帶來性能的提升，甚至會帶來比串行仿真更差的結果。論文圍繞并行分布實時仿真中的任務調(diào)度問題，從仿真任務分配和周期仿真任務集可調(diào)度性分析兩方面展開研究。
　　本文在對仿真任務調(diào)度策略進行了一般性研究的基礎上，首先分析了實時仿真的可調(diào)度性問題。為保證并行分布實時仿真的實時性要求，需要在系統(tǒng)設計階段就對仿真任務集進行可調(diào)度性分析。一般并行分布實時仿真中任務集都是周期性的，論文研究了周期仿真任務集在同構多處理器平臺下采

3、用固定作業(yè)優(yōu)先級調(diào)度算法的可調(diào)度性分析。由于傳統(tǒng)可調(diào)度性分析采用的理論方法不具備完備性，論文采用了模擬運行的方式進行可調(diào)度性分析。根據(jù)周期仿真任務集特點，可調(diào)度性分析主要是求可調(diào)度區(qū)間。論文首先給出一個基本可調(diào)度區(qū)間，并歸納出求解可調(diào)度區(qū)間的基本思路；然后從仿真任務執(zhí)行狀態(tài)界限出發(fā)，給出了兩個改進的可調(diào)度區(qū)間，并將這兩個改進結果合并得到最終結果，保證所求的可調(diào)度區(qū)間范圍達到最小。
　　然后針對分布式實時仿真平臺、多核實時仿真平臺和

4、異構多處理器實時仿真平臺三個典型仿真應用平臺，依次展開研究：
　　（1）對于使用最廣泛的分布式仿真平臺，平臺的復雜性將大大增加系統(tǒng)失效的可能性，因此可靠性是其一個關鍵性需求，對運行實時仿真應用的分布式仿真平臺尤為重要。使用任務分配的方法來提高分布式實時仿真平臺的可靠性，不需要增加額外的軟硬件資源，具備更廣泛的適用性。論文通過對系統(tǒng)可靠性及約束條件分析，將仿真任務分配問題建模為組合優(yōu)化問題，并提出了一個混沌自適應模擬退火算法XASA

5、用以求解該問題。XASA算法首先在混沌優(yōu)化算法的基礎上進行解空間的混沌遍歷，得到一個局部最優(yōu)集，然后采用自適應策略對模擬退火算法進行改進，在局部最優(yōu)集的基礎上進一步尋優(yōu)。
　　（2）多核處理器集群作為當前最熱門的處理平臺，在并行分布實時仿真中逐漸成為主流。相比較于傳統(tǒng)的并行分布式仿真平臺，多核集群的特點是節(jié)點內(nèi)通信代價不可忽略，針對這一特點，論文著重分析了節(jié)點內(nèi)通信對仿真任務分配問題帶來的影響。通過分析單個節(jié)點的節(jié)點內(nèi)/節(jié)點間通信

6、代價，建立關于一致代價仿真任務分配問題的最小費用流模型，進而推廣到一般意義下的多核處理器集群仿真任務分配問題，并建立廣義最小費用流模型。通過分析通信代價凹函數(shù)的特點將凹費用網(wǎng)絡流轉換為帶固定費用網(wǎng)絡流問題之后，設計遺傳模擬退火組合算法求解該問題。
　?。?）仿真的實時性因任務的不同而存在很大差異，因此針對不同實時性要求的仿真任務需要不同類型的處理器來處理，而同一個仿真任務在不同類型的處理器上執(zhí)行結果也不盡相同。論文通過分析異構多處

7、理器平臺特性，選擇仿真任務在同類處理器內(nèi)部自由遷移的內(nèi)遷移問題作為研究對象，將異構多處理器仿真任務調(diào)度問題轉化為內(nèi)遷移仿真任務分配問題。在對該問題建模為整數(shù)線性規(guī)劃問題的基礎上，松弛為線性規(guī)劃問題，將因松弛產(chǎn)生的未完整分配的仿真任務稱為“散碎仿真任務”，論文證明了在包含有t類處理器的異構多處理器環(huán)境下，最多只有t1個散碎仿真任務。然后根據(jù)散碎仿真任務建立二分圖模型，提出通過調(diào)整邊權值的方法消除圖中的環(huán)，最后設計算法將散碎仿真任務完整分配