羅澤雄，曲國遠(yuǎn)，嚴(yán)龍，湯雪乾

中國航空無線電電子研究所 電子部，上海 200233

航空電子系統(tǒng)經(jīng)歷了分立式、聯(lián)合式、綜合式和先進(jìn)綜合式的發(fā)展階段，目前正在發(fā)展分布式綜合模塊化航空電子(Distributed Integrated Modular Avionics，DIMA)體系架構(gòu)，并使分時(shí)分區(qū)處理與時(shí)間觸發(fā)通信綜合化互連技術(shù)相結(jié)合。

SAE AS6802標(biāo)準(zhǔn)定義的時(shí)間觸發(fā)以太網(wǎng)(Time-Triggered Ethernet，TTE)是可以容納時(shí)間觸發(fā)(Time Trigered,TT)、速率約束(Rate Constraint，RC)事件觸發(fā)和“盡力傳”(Best Effort，BE)流量的混合關(guān)鍵性綜合化互連技術(shù)，其中TT流量具有嚴(yán)格的時(shí)間確定性，適用于安全和任務(wù)關(guān)鍵性的航空電子信息傳輸，并已經(jīng)用于美國航空航天局(NASA)載人飛船。在基于協(xié)議控制幀(Protocol Control Frame，PCF)的分布式時(shí)鐘同步機(jī)制的支持下，根據(jù)離線生成的調(diào)度表進(jìn)行TT流量調(diào)度，并在預(yù)留保護(hù)間隔的條件下允許RC和BE流量在“孔隙”(Porosity)中傳輸。

將周期性的TT流量作為虛擬鏈路(Virtual Link，VL)，并將實(shí)時(shí)調(diào)度和網(wǎng)絡(luò)拓?fù)涞募s束轉(zhuǎn)化為可滿足性模理論(Satisfiability Modulo Theories，SMT)問題，利用形式化求解器求解。可以采用根據(jù)可調(diào)度的難度由難到易排序的方法，增量化SMT求解提高求解效率。時(shí)間觸發(fā)調(diào)度表也可以借鑒IMA系統(tǒng)中嚴(yán)格周期調(diào)度，文獻(xiàn)[11]采用混合整數(shù)線性規(guī)劃(MILP)方法和博弈理論進(jìn)行建模和求解，文獻(xiàn)[12]則對(duì)MILP模型進(jìn)行了線搜索解釋。

形式化描述不便于描述作業(yè)鏈等較為復(fù)雜的應(yīng)用要求，可以采用啟發(fā)式算法。文獻(xiàn)[13-15]則分別采用了“盡可能快”(As Soon As Possible，ASAP)、免疫算法和樹搜索算法求解TT調(diào)度表；其中，文獻(xiàn)[15]給出了根據(jù)交換轉(zhuǎn)發(fā)的延遲將路徑上各物理鏈路的待調(diào)度時(shí)隙左移并回卷，隨后將它們已占用的時(shí)隙以“或”邏輯相掩(Masked)，求得空閑時(shí)隙的方法。

文獻(xiàn)[16]創(chuàng)造性地給出了處理任務(wù)與通信任務(wù)的聯(lián)合調(diào)度，但處理任務(wù)的粒度較細(xì)，與分時(shí)分區(qū)的航空電子ARINC 653操作系統(tǒng)的應(yīng)用場景有所不同。文獻(xiàn)[18]則將分區(qū)作為整體考慮，實(shí)現(xiàn)了求解增量化和生命周期的大增量化，并在SMT+MILP的基礎(chǔ)上引入了MAX-SAT問題，以不滿足的可能性最小為優(yōu)化條件。

文獻(xiàn)[15]為每條VL構(gòu)造相掩的時(shí)隙軸，采用ASAP調(diào)度表生成算法；借鑒文獻(xiàn)[18]的思想，對(duì)于無法嚴(yán)格周期調(diào)度的VL可以放寬到最小抖動(dòng)時(shí)隙分配，并且采用重要性抽樣(Importance Sampling，IS)方法進(jìn)行優(yōu)化。

早在20世紀(jì)40年代的曼哈頓工程中，IS方法就被發(fā)明用于大幅度加快稀有事件仿真的速度；隨后被廣泛應(yīng)用于失效概率評(píng)估等工程領(lǐng)域，但它也是一種通過扭曲樣本概率分布進(jìn)行啟發(fā)式尋優(yōu)的方法，可根據(jù)應(yīng)用設(shè)置各種優(yōu)化準(zhǔn)則，包含考慮作業(yè)之間復(fù)雜的時(shí)序依賴關(guān)系(類似于文獻(xiàn)[21])。

本文所述研究工作的創(chuàng)新性思路為：① 對(duì)于TT VL的可調(diào)度性和某些VL作業(yè)鏈延遲的2種不同的優(yōu)化準(zhǔn)則，提出兩階段的基于IS的TT調(diào)度表生成方法，克服了SMT求解器只能得到可行解且求解過程為“黑盒”的不足；② 給出面向應(yīng)用的TT VL作業(yè)鏈的描述方法和串聯(lián)、匯合關(guān)系下延遲的累加方法，既考慮TT通信任務(wù)實(shí)例(即：作業(yè))之間的時(shí)序依賴關(guān)系，又能通過最壞情況下最好準(zhǔn)則評(píng)價(jià)任務(wù)組的性能，并可以靈活適用于網(wǎng)絡(luò)與處理分區(qū)同步或不同步的情況。

1 時(shí)間觸發(fā)流量模型

設(shè)TT通信任務(wù)的集合{,∈}為周期性的，周期為{Ф}；設(shè)每個(gè)TT通信任務(wù)的數(shù)據(jù)包長度是給定的，且以時(shí)間為單位，記為{}。時(shí)間觸發(fā)調(diào)度表的集成循環(huán)(Integrated Cycle，IC)為{Ф}中的最小值，而集群循環(huán)(Cluster Cycle，CC)為各個(gè)周期的最小公倍數(shù)。

考慮到TT流量和RC流量共用物理鏈路，為了能夠使處理TT流量的嵌入式程序及時(shí)阻斷RC流量，設(shè)置保護(hù)間隔(Guard Margin)。

為了進(jìn)一步實(shí)現(xiàn)多孔調(diào)度，TT網(wǎng)絡(luò)規(guī)劃中一般限定“孔”的最小值。一般要求“孔”中至少能夠容納一個(gè)最長幀。對(duì)于物理碼速率為1 Gbit/s 或100 Mbit/s的TTE網(wǎng)絡(luò)，傳輸一幀長度為1 518字節(jié)的以太網(wǎng)最長幀耗時(shí)分別約為12 μs 或120 μs，物理鏈路速率為1 Gbit/100 Mbit/s條件下,TTTech公司的TT-Plan軟件默認(rèn)的TT窗口之間最小間隔值分別為20、200 μs。

調(diào)度的時(shí)候不妨令TT通信實(shí)例長度=++，即TT調(diào)度表考慮各條TT VL的實(shí)例分別以占用時(shí)間軸，這樣調(diào)度的效果就同時(shí)考慮了保護(hù)間隔和多孔調(diào)度要求。

TT通信調(diào)度表將時(shí)間軸分解為時(shí)隙，時(shí)隙長度等于常量，則周期Ф、TT通信實(shí)例長度(對(duì)變長時(shí)間段除以并上取整，占據(jù)1個(gè)或多個(gè)時(shí)隙)、IC循環(huán)和CC循環(huán)的長度和都可以用時(shí)隙為單位整數(shù)表示。

與文獻(xiàn)[7]類似，要求為所有的物理鏈路生成TT調(diào)度表，且調(diào)度表的長度等于CC中時(shí)隙的數(shù)目。注意到TTE網(wǎng)絡(luò)是采用交換機(jī)互連，對(duì)于每條VL，交換機(jī)的技術(shù)時(shí)延以及與數(shù)據(jù)包長度有關(guān)的存儲(chǔ)轉(zhuǎn)發(fā)延遲。在圖1的例子中，設(shè)從ES發(fā)出的某條VL經(jīng)過交換機(jī)Sw和Sw，先驗(yàn)已知分別延遲與。如果還沒有對(duì)這條VL分配時(shí)隙，要決定可以分配給該VL(設(shè)為VL)的實(shí)例的空閑時(shí)隙，可以ES接入物理鏈路的調(diào)度表為基準(zhǔn)，將第2級(jí)和第3級(jí)物理鏈路的調(diào)度表分別左移,和sum,=,+,，并將早于基準(zhǔn)0點(diǎn)的部分回卷之后接到后面；隨后將各物理鏈路現(xiàn)有的調(diào)度表中已經(jīng)占用的部分邏輯“或”相掩之后，形成“合成時(shí)隙”，其時(shí)間軸上的空閑時(shí)隙才是可以無沖突占用的。

值得說明的是，在TTE網(wǎng)絡(luò)中，每個(gè)IC均有PCF同步過程，同步過程時(shí)間段是不能被TT占用的開銷。

如果采用ASAP方法進(jìn)行嚴(yán)格周期調(diào)度，則對(duì)于未調(diào)度的VL，在現(xiàn)有的“合成時(shí)隙”下指定一個(gè)嘗試偏移量起點(diǎn),0，如果實(shí)例時(shí)間段的集合{[,,,+-1]}都處于空閑區(qū)間，則找到了一個(gè)可行解，其中,=,0+×Ф，= 0,1,…,-1,=Ф；如果實(shí)例時(shí)間段與已占據(jù)的時(shí)隙沖突，則嘗試偏移量右移一個(gè)時(shí)隙，重復(fù)此操作。ASAP方法取最早找到的一個(gè)可行偏移量作為VL的起始相位,0。經(jīng)過ASSP方法找到可行偏移量的VL的調(diào)度信息為{Ф,, ,0}。

圖1 時(shí)隙的左移、回卷和相掩Fig.1 Shift, wrap and masking of slots

如果遍歷所有的起點(diǎn)都找不到嚴(yán)格調(diào)度的可行解，可以從某個(gè)嘗試點(diǎn)出發(fā)選定第一個(gè)實(shí)例可行的嘗試偏移量,0，其他實(shí)例依次遍歷空閑的時(shí)隙，并利用類似于文獻(xiàn)[19]的方法評(píng)價(jià)該方案與嚴(yán)格周期方案相比的抖動(dòng)。可以枚舉嘗試偏移量,0的取值，選擇所有方案中抖動(dòng)量最小的。但調(diào)度信息需要記錄所有實(shí)例的相位，得到的調(diào)度信息為{Ф,,{,0,,1, …,,-1}}。

與SMT調(diào)度方法一樣，本文所述的方法也是依次進(jìn)行時(shí)隙嘗試和分配的，顯然先嘗試的VL獲得嚴(yán)格周期調(diào)度的機(jī)會(huì)大。根據(jù)文獻(xiàn)[8]采用嚴(yán)格周期利用率(Strict-Periodic Utilization, SPU)對(duì)各TT VL的可調(diào)度性進(jìn)行排序，先調(diào)度難調(diào)度的流量，可以提高系統(tǒng)整體的可調(diào)度性。

2 兩階段重要性抽樣

2.1 重要性抽樣過程

重要性抽樣是一種面向?qū)嶒?yàn)或仿真的迭代優(yōu)化方法。其思路為，將待確定的參數(shù)作為隨機(jī)變量，設(shè)定其離散的概率密度函數(shù)；每次從各個(gè)隨機(jī)變量的樣本空間抽樣，并記錄樣本值；利用優(yōu)化準(zhǔn)則對(duì)實(shí)驗(yàn)或仿真結(jié)果進(jìn)行評(píng)價(jià)。運(yùn)行多次仿真，將評(píng)價(jià)結(jié)果排序，設(shè)定一個(gè)比例作為閾值，有0<<1。選出較優(yōu)的樣本，使被選出的樣本數(shù)目與樣本總數(shù)的比例為，對(duì)所選出的樣本值進(jìn)行統(tǒng)計(jì)，形成經(jīng)驗(yàn)分布概率密度函數(shù),sa；并設(shè)定一個(gè)更新因子，0 <<1，令

+1=(1-)+,sa

(1)

隨后利用更新的概率密度函數(shù)+1改變樣本空間的總體，重新進(jìn)行抽樣，迭代上述過程，直至找到滿足指標(biāo)要求的參數(shù)設(shè)置，或者使評(píng)價(jià)結(jié)果的統(tǒng)計(jì)量在誤差范圍內(nèi)不再變化。

具體到TT調(diào)度表生成問題，需要解決TT調(diào)度表的可調(diào)度性問題，以及給定作業(yè)鏈的延遲時(shí)間較短的優(yōu)化目標(biāo)。

這2個(gè)優(yōu)化目標(biāo)屬于不同性質(zhì)的問題，所以它們的評(píng)價(jià)指標(biāo)很難結(jié)合表達(dá)，所以采用兩階段重要性抽樣。

第1階段以可調(diào)度性(即：作業(yè)盡可能按照嚴(yán)格周期進(jìn)行調(diào)度，不能遵循嚴(yán)格周期調(diào)度，則要求每個(gè)作業(yè)發(fā)生時(shí)間偏離周期的間隔抖動(dòng)較小)為優(yōu)化準(zhǔn)則，迭代一定輪次，嘗試各VL偏移量,0的取值使得整個(gè)TT調(diào)度的可調(diào)度性較好，減少ASAP盲目嘗試的次數(shù)。

在第2階段，保留第1階段扭曲的各VL嘗試偏移量,0的分布，描述并評(píng)價(jià)作業(yè)鏈起始到結(jié)束的延遲，并適當(dāng)結(jié)合可調(diào)度性(如：不可調(diào)度的罰函數(shù))進(jìn)行重要性抽樣，啟發(fā)式得出近優(yōu)的TT調(diào)度表，同時(shí)保證可調(diào)度性和作業(yè)鏈及時(shí)性。

2個(gè)階段所采用的IS算法過程類似，所不同的只是評(píng)價(jià)方法和停止條件，如圖2所示。

圖2 時(shí)間觸發(fā)調(diào)度表生成的重要性抽樣Fig.2 Important sampling for TT scheduling generation

2.2 第1階段：優(yōu)化可調(diào)度性

在第次迭代的第輪嘗試中，對(duì)于第條TT VL，第1階段的評(píng)價(jià)方法主要考慮3方面的因素，計(jì)算代價(jià)的數(shù)值,,，如表1所示，有,,=1,,,+2,,,。求和得到本輪次總代價(jià),。

在表1中，為指示函數(shù)，在腳標(biāo)中邏輯函數(shù)成立的情況下為1，否則為0；例如：表1中,0<,0表示在,0<,0成立的條件下取值為1，否則為0。對(duì)于非嚴(yán)格周期調(diào)度的情況，在代價(jià)2中加上整個(gè)CC的時(shí)隙數(shù)作為懲罰；而完全不可調(diào)度，則選取一個(gè)很大的罰值，經(jīng)驗(yàn)上可以取的10倍。

在進(jìn)行重要性抽樣之前，已經(jīng)對(duì)每條物理鏈路進(jìn)行了利用率檢查，保證TT流量加上保護(hù)間隔導(dǎo)致的利用率小于1。但在這種情況以及允許有抖動(dòng)的條件下，仍可能出現(xiàn)TT VL不可調(diào)度的情況，原因在于被占用的時(shí)隙之間連續(xù)存在的空閑時(shí)隙過短，無法容納未調(diào)度的數(shù)據(jù)包。

在計(jì)算經(jīng)驗(yàn)分布函數(shù)的過程中，將記錄3種指標(biāo)：第次迭代中代價(jià){,}(=1,2,…,)的最小值,min、經(jīng)過排序后最小的·嘗試的部分和,TH，以及本次迭代所用的時(shí)間。這3個(gè)指標(biāo)的減小都能說明可調(diào)度性得到了改善，其中減小的意義在于，進(jìn)行最小抖動(dòng)的非嚴(yán)格周期調(diào)度所需時(shí)間遠(yuǎn)大于嚴(yán)格周期可調(diào)度情況下的ASAP，越短說明本次迭代整體上有更多的TT VL滿足嚴(yán)格周期可調(diào)度條件，所選的嘗試偏移量越合理。

除了達(dá)到迭代的輪次退出最外層循環(huán)之外，還通過上述3個(gè)參數(shù),min、,TH、判定停止條件，由于隨機(jī)因素的影響，某個(gè)參數(shù)可能在不同的

表1 第1階段的評(píng)價(jià)方法Table 1 Evaluation methods in the first stage

迭代輪次有所起伏，所以規(guī)定只有這3個(gè)參數(shù)全都不再減小的時(shí)候，才退出循環(huán)。

2.3 第2階段：優(yōu)化作業(yè)鏈延遲時(shí)間

第2階段的重要性抽樣是在第1階段得到的可調(diào)度性增強(qiáng)的樣本空間概率密度分布的基礎(chǔ)上進(jìn)行的。

由于第2階段主要關(guān)注作業(yè)鏈的延遲時(shí)間，因此代價(jià),等于系統(tǒng)中各條作業(yè)鏈的延遲之和，其計(jì)算方法在第4節(jié)說明。除此之外，僅考慮不可調(diào)度時(shí)，設(shè)定極大的罰值，令,=。

除了指定迭代的次數(shù)，第2階段的迭代終止條件是找到每次迭代所有輪次的最小值,，代表的是所有輪次中作業(yè)鏈最壞延遲之和的最好情況，符合“最壞最好”的實(shí)時(shí)系統(tǒng)尋優(yōu)的原則。同時(shí)還要記錄這些最小值對(duì)應(yīng)的TT調(diào)度表參數(shù)。

設(shè)置迭代次數(shù)的經(jīng)驗(yàn)上限值，如果迭代次數(shù)達(dá)到經(jīng)驗(yàn)上限值時(shí)，,min的當(dāng)前值沒有比已記錄的歷史值更小，即可以提前退出最外層循環(huán)。

此時(shí)，取所有迭代中最小值，并根據(jù)記錄的參數(shù)得到嚴(yán)格周期可調(diào)度性和作業(yè)鏈及時(shí)性雙重最優(yōu)的TT調(diào)度表。

在實(shí)際工作中，也可以適當(dāng)減少第1階段的迭代次數(shù)，在保證樣本空間概率密度分布具有一定的可調(diào)度性優(yōu)化的同時(shí)，對(duì)于嘗試偏移量保持足夠的隨機(jī)性，避免過早陷于局部最優(yōu)。

2.4 抽樣實(shí)驗(yàn)的漸近等概特性

根據(jù)信息論的類型理論，隨機(jī)事件發(fā)生的概率由樣本總體中的典型事件決定，具有漸近等概(Asympotic Equipartition Property，AEP)特性，非典型事件的發(fā)生概率是稀有的。利用ASAP得到可調(diào)度結(jié)果和作業(yè)鏈延遲優(yōu)化的可調(diào)度結(jié)果的事件是稀有的，設(shè)分別對(duì)應(yīng)集合Г和Г，如圖3所示。

圖3 樣本總體和集合的示意圖Fig.3 Diagram for total samples and sample sets

(2)

(3)

盡管兩階段抽樣很難降低迭代的次數(shù)，但它的優(yōu)勢在于：

1) 迭代中構(gòu)造經(jīng)驗(yàn)分布函數(shù)(圖2中標(biāo)注 ① 到 標(biāo)注 ②)的每次嘗試為常規(guī)抽樣，特別是剛開始迭代時(shí)參數(shù)近乎均勻分布，均可得到加速。

2) 第2階段評(píng)價(jià)指標(biāo)計(jì)算的開銷較大，分成兩階段進(jìn)行層次化評(píng)價(jià)，可減小這部分開銷。

3) 工程設(shè)計(jì)中往往也被分為2個(gè)階段，第1階段得到可調(diào)度性強(qiáng)的參數(shù)分布，便于第2階段集中精力針對(duì)不同條件進(jìn)行分區(qū)和通信聯(lián)合調(diào)度的性能比較。

3 作業(yè)鏈的時(shí)序關(guān)系和延遲計(jì)算

航空電子處理任務(wù)的實(shí)例對(duì)應(yīng)嵌入式終端或分區(qū)的一次運(yùn)行，通信任務(wù)的實(shí)例是一次數(shù)據(jù)幀的端到端傳輸，將它們統(tǒng)稱為作業(yè)(Job)。

類似于在航空電子體系架構(gòu)描述中對(duì)于流時(shí)延的時(shí)序依賴關(guān)系累加，應(yīng)用要求一些作業(yè)之間保證時(shí)序依賴關(guān)系。最常見的應(yīng)用場景是嵌入式系統(tǒng)周期性采樣物理量，通過數(shù)據(jù)集中到綜合化處理模塊進(jìn)行處理，處理模塊在給定的分區(qū)窗口開始的時(shí)候從ARINC 653操作系統(tǒng)規(guī)定的“偽分區(qū)”讀取采樣數(shù)據(jù)，處理后在分區(qū)窗口結(jié)束前由ES發(fā)送，或是進(jìn)行分區(qū)間通信傳遞給其他模塊。這種場景下的依賴關(guān)系可分解為串聯(lián)、匯合和分叉，可以用運(yùn)籌學(xué)的任務(wù)圖表示(這種任務(wù)圖中的任務(wù)是指作業(yè)，如圖4所示)。對(duì)于任務(wù)圖中的關(guān)鍵路徑所對(duì)應(yīng)的作業(yè)鏈，計(jì)算從所有作業(yè)的起始時(shí)刻到完成時(shí)刻的最壞情況下的累積值。

既有的時(shí)序依賴關(guān)系的分析(例如：Job-Shop問題)僅針對(duì)作業(yè)；但考慮到系統(tǒng)中大多數(shù)任務(wù)是周期性的，受文獻(xiàn)[20]的啟發(fā)，可以兼顧任務(wù)，即選取任務(wù)圖中關(guān)鍵路徑所對(duì)應(yīng)的作業(yè)鏈作為“主干”，選取它的起始任務(wù)在一個(gè)周期內(nèi)的作業(yè)為定時(shí)的起點(diǎn)，分別計(jì)算它周期內(nèi)每個(gè)作業(yè)所對(duì)應(yīng)的鏈上到終點(diǎn)最壞時(shí)間延遲，并將延遲的最大值作為評(píng)價(jià)指標(biāo)。如果主干鏈上的中間作業(yè)依賴于某些前續(xù)作業(yè)的串聯(lián)或匯合，則可以使該作業(yè)為終點(diǎn)，計(jì)算該分支最壞延遲下作業(yè)的偏移量。

圖4 作業(yè)之間依賴關(guān)系的類型Fig.4 Types of job dependencies

TT調(diào)度表保證了交換式網(wǎng)絡(luò)中作業(yè)之間是無沖突的，因此對(duì)于具有依賴關(guān)系的作業(yè)，不需要考慮它們相遇的交換機(jī)輸出鏈路的時(shí)隙分配關(guān)系，只需要直接考慮目的ES接入物理鏈路上的時(shí)隙占用情況。

例如在圖5中，生成的TT調(diào)度表給定了嵌入式系統(tǒng)Emb的任務(wù)的作業(yè)在源端Src(ES)的接入物理鏈路上的偏移量src,,，以及源端ES到目的端Dest(ES)交換路徑上的延遲偏移量之和sum,(交換網(wǎng)絡(luò)偏移量即圖1中的左移值，當(dāng)路徑確定后為先驗(yàn)已知)。則目的端接入物理鏈路的時(shí)隙位置為

dest,,=src,,+sum,

(4)

同理,可計(jì)算嵌入式系統(tǒng)Emb的任務(wù)的作業(yè)在目的端接入物理鏈路的時(shí)隙位置dest,,。則當(dāng)Emb與Emb產(chǎn)生的數(shù)據(jù)包在目的端交匯(圖4(b))時(shí)，需要等待時(shí)間為

dest_delay,,=dest,,-dest,,

(5)

考慮到時(shí)間的不可逆性，如果物理量需要因果性，即要求引發(fā)作業(yè)的物理事件的先后關(guān)系在目的ES也必須得到保持，則必須研究目的接入鏈路與源接入鏈路上各作業(yè)的時(shí)隙之間的對(duì)應(yīng)關(guān)系。將這種因果性的先后關(guān)系稱為串聯(lián),如圖4(a) 所示。

圖6用時(shí)序圖給出了串聯(lián)關(guān)系分析的例子，由于傳輸延遲，嵌入式系統(tǒng)Emb的通信任務(wù)的實(shí)例落后通信任務(wù)的實(shí)例超過一個(gè)周期，在必須考慮因果性的處理節(jié)點(diǎn)4，不能利用離它最近的的數(shù)據(jù)。因此串聯(lián)關(guān)系需要將目的端接入物理鏈路的時(shí)隙反向回溯，檢查它們?cè)炊藭r(shí)的時(shí)序先后關(guān)系，進(jìn)而確定在目的端接入物理鏈路上屬于不同任務(wù)的作業(yè)之間的時(shí)隙先后關(guān)系。

對(duì)于圖4(c)所示的分支關(guān)系，則可以分解為2個(gè)串聯(lián)依賴關(guān)系，分別計(jì)算兩路作業(yè)之間的延遲。

作業(yè)鏈同樣適用于表達(dá)TT數(shù)據(jù)包與分區(qū)處理之間的時(shí)序關(guān)系。類似于文獻(xiàn)[17]，分時(shí)分區(qū)調(diào)度可以被抽象為TT自鏈路(Self Link)，當(dāng)處理任務(wù)與通信任務(wù)不存在同步時(shí)，以分區(qū)調(diào)度的周期作為最壞延遲，當(dāng)它們之間存在同步時(shí)，可以根據(jù)分區(qū)調(diào)度窗口與TT調(diào)度表的偏移量，進(jìn)行一次“匯合”依賴關(guān)系的延遲計(jì)算。

圖5 源端和目的端接入物理鏈路的時(shí)隙分配Fig.5 Time slot allocations of access of source and destination end-system to physical links

圖6 串聯(lián)作業(yè)的時(shí)序圖Fig.6 Sequence diagram of series jobs

4 案例分析

4.1 拓?fù)浣Y(jié)構(gòu)與流量配置

給定如圖7所示的TTE網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)配置，對(duì)于所提出的兩階段基于IS的調(diào)度表生成方法進(jìn)行案例分析。該案例設(shè)置有4個(gè)交換節(jié)點(diǎn)，交換節(jié)點(diǎn)之間采用全雙工互連，每個(gè)交換節(jié)點(diǎn)各接入4個(gè)ES。所有的物理鏈路均為全雙工。圖7在ES和交換機(jī)的圖標(biāo)中標(biāo)明了各個(gè)節(jié)點(diǎn)的標(biāo)號(hào)，在節(jié)點(diǎn)之間的有向連線上標(biāo)出了物理鏈路的編號(hào)，要求為每條物理鏈路生成TT VL的調(diào)度表。設(shè)物理鏈路碼速率為100 Mbit/s，IC=1 ms，時(shí)隙=8 μs，保護(hù)間隔為2個(gè)時(shí)隙，“孔”的最小值為200 μs(25個(gè)時(shí)隙)。該案例的VL配置如表2所示。

圖7 時(shí)間觸發(fā)網(wǎng)絡(luò)案例的拓?fù)浣Y(jié)構(gòu)Fig.7 Topology of a time-triggered network

表2 案例中的VL配置Table 2 Configuration of VLs in case

4.2 作業(yè)鏈的設(shè)定

為了體現(xiàn)航空電子系統(tǒng)綜合化處理和分區(qū)間通信的特點(diǎn)，設(shè)定一條包含6條VL的作業(yè)鏈，其時(shí)序依賴關(guān)系如圖8所示。

圖8 作業(yè)鏈依賴關(guān)系示例Fig.8 Example of dependencies within a job chain

如圖8，設(shè)定VL、VL、VL承載的信息具有物理上因果性要求，因此可以表達(dá)為VL串聯(lián)VL、VL串聯(lián)VL；隨后它們都通過物理鏈路12進(jìn)入ES，并在綜合化分區(qū)中處理；設(shè)定應(yīng)用還需要從VL到綜合化分區(qū)處理之后的結(jié)果，它和綜合化分區(qū)的結(jié)果是匯合關(guān)系。設(shè)處理后會(huì)形成VL的數(shù)據(jù)載荷，這需要處理分區(qū)到ES網(wǎng)絡(luò)接口偽分區(qū)，具有一個(gè)常量的分區(qū)間通信延遲，隨后以VL的周期串聯(lián)VL發(fā)送到ES。

如果案例場景的設(shè)定受到2種因素的影響，記為、，前者為分區(qū)處理是否與網(wǎng)絡(luò)同步的設(shè)定，后者為分時(shí)分區(qū)調(diào)度窗口，則仿真場景可以用(,)表示，和的設(shè)定情況分別見表3和表4。其中，表3中的分區(qū)相位為分區(qū)的釋放時(shí)刻在整個(gè)分區(qū)調(diào)度周期內(nèi)的位置；表4中設(shè)定了典型的分區(qū)周期值，實(shí)際應(yīng)用中分區(qū)調(diào)度的時(shí)間粒度隨著處理機(jī)能力的不同而有差異，每個(gè)分區(qū)的時(shí)間窗口可以是十幾微秒到幾百微秒，所以分區(qū)調(diào)度周期一般可以為幾百微秒到幾毫秒。

表3 分區(qū)與時(shí)間觸發(fā)網(wǎng)絡(luò)同步關(guān)系的場景設(shè)定

表4 分區(qū)調(diào)度周期的場景設(shè)定

4.3 重要性抽樣與調(diào)度表生成的優(yōu)化

設(shè)定第1階段的較優(yōu)樣本比例閾值為=0.5，更新因子為=0.2。

觀測第次迭代中代價(jià)的最小值,min、經(jīng)過排序后代價(jià)最小部分的代價(jià)之和,TH，以及第次迭代所用的時(shí)間。由于前兩者的取值范圍不同，不便在一張圖形下繪制；且在不同的計(jì)算機(jī)上程序執(zhí)行的具體數(shù)值相差較大；所以將這3種參數(shù)的所有數(shù)據(jù)各自除以其第1次迭代時(shí)得到的值進(jìn)行歸一化。圖9給出了圖7、表2所設(shè)定算例第1階段迭代32次的結(jié)果。

如圖9所示，可見在利用IS仿真計(jì)算進(jìn)行嘗試偏移量分布的啟發(fā)式優(yōu)化過程中，3種評(píng)價(jià)參數(shù)指標(biāo)均呈現(xiàn)下降的趨勢，但由于仿真的隨機(jī)抽樣特性，過程中存在著局部的起伏。

由于第1階段相當(dāng)于“粗篩”出易于調(diào)度的ASAP和最小抖動(dòng)時(shí)隙分配的嘗試起始點(diǎn)，而第2階段則要精細(xì)地考察任務(wù)鏈的延遲，因此IS過程中經(jīng)驗(yàn)上取較小的較優(yōu)樣本比例閾值，即令=0.1；更新因子仍取=0.2。

在實(shí)際應(yīng)用中，為了保證第2階段的優(yōu)化仍具有抽樣的隨機(jī)性，可以采用使第1階段迭代次數(shù)減半的方法，在優(yōu)化效果和樣本的隨機(jī)性之間取得權(quán)衡。

圖9 案例第1階段IS優(yōu)化的評(píng)價(jià)指標(biāo)Fig.9 Evaluation metrics for the first stage IS optimization in case

可以選取第2階段中代價(jià)最小的TT時(shí)隙分配方案作為最終的TT調(diào)度表。也可以保持第1階段結(jié)束后經(jīng)過了優(yōu)化的嘗試偏移量分布，再進(jìn)行若干次仿真實(shí)驗(yàn)，選擇代價(jià)最小的某次TT時(shí)隙分配方案作為最終的TT調(diào)度表。

在案例研究中，根據(jù)表3和表4的設(shè)定分別進(jìn)行了基于IS的仿真實(shí)驗(yàn)和分析計(jì)算(,)，求得圖8定義任務(wù)鏈起始到終止的延遲，并選擇在最壞情況下延遲最小的結(jié)果作為TT調(diào)度表的輸出。

不同(,)仿真場景所對(duì)應(yīng)的作業(yè)鏈延遲最小值如圖10所示?？梢姡?dāng)分時(shí)分區(qū)與時(shí)間觸發(fā)網(wǎng)絡(luò)同步時(shí)，可以降低作業(yè)鏈的延遲，特別是對(duì)于分區(qū)調(diào)度周期較長的應(yīng)用效果更明顯。然而，實(shí)際應(yīng)用中分區(qū)與網(wǎng)絡(luò)TT消息的同步的驅(qū)動(dòng)程序改造和協(xié)議開銷也不能忽略，需要服從于整體系統(tǒng)和網(wǎng)絡(luò)的規(guī)劃，可以僅選定部分關(guān)鍵的處理模塊和TT VL進(jìn)行精確時(shí)鐘同步，其他流量仍保持事件觸發(fā)的解決方案。

圖10 案例第2階段基于IS求得的任務(wù)鏈延遲Fig.10 Job chain delay values from the second stage IS optimization in case

4.4 調(diào)度表生成方法下作業(yè)鏈的延遲性能

針對(duì)圖7、表2設(shè)定的案例，分別采用SMT求解器、基本的樹搜索算法生成時(shí)間觸發(fā)調(diào)度表。前者又分為兩種方法，不進(jìn)行可調(diào)度性排序的SMT方法每次求得可行解，得到10種不同的可行TT調(diào)度表；基于SPU排序的增量化SMT方法進(jìn)行可調(diào)度性排序預(yù)處理，限定的求解次序降低了可行調(diào)度的多樣性，用這樣方法得到3種不同的可行TT調(diào)度表。樹搜索算法的效果則受到VL求解次序的很大影響。

參照表3、表4，在不同的分區(qū)和網(wǎng)絡(luò)同步場景下分別采用不排序SMT方法、可調(diào)度排序增量化SMT方法、樹搜索方法計(jì)算圖8所示作業(yè)鏈的延遲，與本文提出的兩階段IS方法計(jì)算結(jié)果進(jìn)行對(duì)比，如圖11所示。其中:IS為本文兩階段IS方法；增量SMT為可調(diào)度排序增量化SMT方法；SMT最大為采用不排序SMT方法后得到的最大值；SMT最小為采用不排序SMT方法后得到的最小值；SMT平均為采用不排序SMT方法后得到的平均值。不排序的SMT方法分別取最大、最小和平均值；由于樣本少，只取排序的增量化SMT方法得到的最小延遲；對(duì)于樹搜索算法，使與作業(yè)鏈有關(guān)的VL依次優(yōu)先輸入，得出1種可行調(diào)度表及其相應(yīng)的延遲。

圖11 不同TT調(diào)度表生成方法下作業(yè)鏈延遲Fig.11 Job chain delay values via different TT time table scheduling methods

由于第2階段的重要性抽樣依據(jù)作業(yè)鏈延遲最小的原則評(píng)價(jià)樣本的重要程度加以篩選，作業(yè)鏈的延遲性能明顯優(yōu)于其他方法。相反，基于SPU的增量化SMT方法雖然具有可調(diào)度性保證和快速性的優(yōu)勢，但目前還無法將作業(yè)鏈延遲優(yōu)化融入預(yù)處理排序過程。如圖11(c)，不排序的SMT方法求解的可行范圍略小于(因?yàn)镮S方法允許無法嚴(yán)格周期調(diào)度的VL采用最小時(shí)延抖動(dòng)調(diào)度)；但由于不論是可調(diào)度性排序還是樹搜索排序，只要它們沒有融入作業(yè)鏈優(yōu)化的內(nèi)容，在一般性條件下，其可行范圍和與第二階段優(yōu)化求解的樣本集合均有偏離。

借鑒文獻(xiàn)[17]，使用基本SMT求解器可以通過添加約束實(shí)現(xiàn)分區(qū)處理和通信的聯(lián)合優(yōu)化，但該SMT求解器是“黑盒”，很難掌控求解過程，且求解速度較慢。表5列出了不排序SMT方法、可調(diào)度排序增量化SMT方法、樹搜索方法與本文所提方法相比的優(yōu)缺點(diǎn)。

表5 其他求解方法相比IS方法的優(yōu)缺點(diǎn)

5 結(jié) 論

采用重要性抽樣方法進(jìn)行時(shí)間觸發(fā)網(wǎng)絡(luò)TT調(diào)度表的生成，允許僅使用簡單的ASAP算法處理復(fù)雜的約束關(guān)系，其優(yōu)越性具體體現(xiàn)于。

1) 2個(gè)階段的重要性抽樣優(yōu)化相互配合，第1階段保證了可以在嚴(yán)格周期可調(diào)度性較好的條件下進(jìn)行偏移量選擇，第2階段適時(shí)進(jìn)行面向作業(yè)鏈實(shí)時(shí)性的TT調(diào)度表優(yōu)化。

2) 克服了SMT方法為黑盒求解且只得到可行解的缺點(diǎn)，本文方法可以靈活地處理無法嚴(yán)格周期調(diào)度的情況以及復(fù)雜的作業(yè)依賴關(guān)系，能夠在保證部分嚴(yán)格周期調(diào)度的同時(shí)，其余部分進(jìn)行帶有時(shí)延抖動(dòng)的時(shí)隙分配，并且根據(jù)可調(diào)度性和作業(yè)鏈的及時(shí)性,采用啟發(fā)式算法對(duì)時(shí)隙分配結(jié)果進(jìn)行了優(yōu)化。

3) 通過描述作業(yè)之間的時(shí)序依賴關(guān)系給出了相應(yīng)的延遲計(jì)算方法，并兼顧了任務(wù)和作業(yè)的性能，既體現(xiàn)了作業(yè)鏈的延遲，而且CC循環(huán)中含有多個(gè)作業(yè)的任務(wù)，可以分別計(jì)算各條作業(yè)鏈的延遲情況。

4) 本文方法可以適用于分區(qū)與網(wǎng)絡(luò)TT調(diào)度同步，或是不同步的場景，特別是可以靈活地適用于部分節(jié)點(diǎn)同步的場景。

基于重要性抽樣進(jìn)行TT調(diào)度表生成需要依次進(jìn)行TT流量的ASAP或最小抖動(dòng)時(shí)隙分配，在第1階段可根據(jù)嚴(yán)格周期性調(diào)度的難易程度進(jìn)行排序；但第2階段的可調(diào)度性還將受到作業(yè)鏈的影響，考慮到源于應(yīng)用層的約束較為靈活，本文未安排重新排序，需要在未來的研究中進(jìn)一步完善。