基于重要性抽樣的時間觸發(fā)調(diào)度表生成方法

羅澤雄，曲國遠，嚴龍，湯雪乾

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 兩階段重要性抽樣

2.1 重要性抽樣過程

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

+1=(1-)+,sa

(1)

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

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

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

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

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

2個階段所采用的IS算法過程類似，所不同的只是評價方法和停止條件，如圖2所示。

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

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

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

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

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

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

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

表1 第1階段的評價方法Table 1 Evaluation methods in the first stage

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

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

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

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

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

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

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

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

2.4 抽樣實驗的漸近等概特性

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

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

(2)

(3)

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

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

2) 第2階段評價指標計算的開銷較大，分成兩階段進行層次化評價，可減小這部分開銷。

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

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

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

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

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

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

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

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

dest,,=src,,+sum,

(4)

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

dest_delay,,=dest,,-dest,,

(5)

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

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

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

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

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

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

4 案例分析

4.1 拓撲結(jié)構(gòu)與流量配置

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

圖7 時間觸發(fā)網(wǎng)絡(luò)案例的拓撲結(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ū)間通信的特點，設(shè)定一條包含6條VL的作業(yè)鏈，其時序依賴關(guān)系如圖8所示。

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

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

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

表3 分區(qū)與時間觸發(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。

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

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

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

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

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

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

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

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

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

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

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

參照表3、表4，在不同的分區(qū)和網(wǎng)絡(luò)同步場景下分別采用不排序SMT方法、可調(diào)度排序增量化SMT方法、樹搜索方法計算圖8所示作業(yè)鏈的延遲，與本文提出的兩階段IS方法計算結(jié)果進行對比，如圖11所示。其中:IS為本文兩階段IS方法；增量SMT為可調(diào)度排序增量化SMT方法；SMT最大為采用不排序SMT方法后得到的最大值；SMT最小為采用不排序SMT方法后得到的最小值；SMT平均為采用不排序SMT方法后得到的平均值。不排序的SMT方法分別取最大、最小和平均值；由于樣本少，只取排序的增量化SMT方法得到的最小延遲；對于樹搜索算法，使與作業(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è)鏈延遲最小的原則評價樣本的重要程度加以篩選，作業(yè)鏈的延遲性能明顯優(yōu)于其他方法。相反，基于SPU的增量化SMT方法雖然具有可調(diào)度性保證和快速性的優(yōu)勢，但目前還無法將作業(yè)鏈延遲優(yōu)化融入預(yù)處理排序過程。如圖11(c)，不排序的SMT方法求解的可行范圍略小于(因為IS方法允許無法嚴格周期調(diào)度的VL采用最小時延抖動調(diào)度)；但由于不論是可調(diào)度性排序還是樹搜索排序，只要它們沒有融入作業(yè)鏈優(yōu)化的內(nèi)容，在一般性條件下，其可行范圍和與第二階段優(yōu)化求解的樣本集合均有偏離。

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

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

5 結(jié) 論

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

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

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

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

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

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