并行分布實(shí)時(shí)仿真平臺(tái)任務(wù)調(diào)度技術(shù)研究.pdf

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

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

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

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

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

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

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