臧光界，李 峭，王 彤，熊華鋼

(北京航空航天大學(xué)電子信息工程學(xué)院， 北京100191)

1 引言

綜合模塊化航電系統(tǒng)(Integrated Modular Avionics，IMA)架構(gòu)在航天電子領(lǐng)域得到了廣泛應(yīng)用。 NASA 提議將IMA 架構(gòu)與集成安全關(guān)鍵高級(jí)航空電子通信和控制(Integrated Safety-Critical Advanced Avionics Communication and Control，ISAACC)系統(tǒng)相配合，用于載人航天器安全關(guān)鍵系統(tǒng)的控制和監(jiān)視。 在IMA 的基礎(chǔ)上，分布式綜合模塊化航電系統(tǒng)(Distributed Integrated Modular Avionics， DIMA)采用具有時(shí)間觸發(fā)通信能力的交換式網(wǎng)絡(luò)作為航天平臺(tái)的骨干綜合化互連。 隨著電子信息系統(tǒng)向著多核處理、片上系統(tǒng)(System on Chip， SoC)和智能化方向發(fā)展，出現(xiàn)了微小型化的可綜合模塊，綜合化互連將不僅限于局域網(wǎng)，逐漸產(chǎn)生了電路板級(jí)的芯片間(off-chip)綜合化互連。

時(shí)間觸發(fā)以太網(wǎng)(Time-Triggered Ethernet，TTE)提供了分布式的全局精確時(shí)鐘同步，能夠保證時(shí)間觸發(fā)(Time-Triggered， TT)消息傳輸?shù)膰?yán)格時(shí)間確定性，已作為NASA 的Orion 多用途運(yùn)輸載人飛船的骨干互連技術(shù)得到了實(shí)際應(yīng)用，并有望推廣應(yīng)用到航天電子綜合化系統(tǒng)。

飛船或星載的數(shù)據(jù)處理(On-Board Data Handling，OBDH)子系統(tǒng)不僅承擔(dān)了遙測(cè)、跟蹤和指揮(Telemetry， Track and Command， TT＆C)信息與地面測(cè)控系統(tǒng)之間的數(shù)據(jù)傳輸與存儲(chǔ)，而且在分布式綜合航電體系架構(gòu)下，也需要擔(dān)負(fù)空間平臺(tái)內(nèi)部電子組件之間的綜合化互連。 綜合化互連的對(duì)象包含IMA 處理機(jī)之間的局域網(wǎng)(Local Area Network，LAN)級(jí)別的骨干互連，未來(lái)也將包含微小型化的智能組件的接入互連。 如果將時(shí)間觸發(fā)通信技術(shù)從TTE 網(wǎng)絡(luò)延伸到板級(jí)的片上系統(tǒng)，形成芯片間的綜合化互連，有望減少OBDH子系統(tǒng)的互連種類和協(xié)議層次，同時(shí)增強(qiáng)其可重構(gòu)能力。

骨干互連和芯片間互連之間網(wǎng)關(guān)的轉(zhuǎn)發(fā)調(diào)度方法關(guān)系到平臺(tái)內(nèi)部消息傳輸實(shí)時(shí)性和合理性，目前研究人員已對(duì)系統(tǒng)模型進(jìn)行研究，并提出時(shí)間觸發(fā)總線和網(wǎng)絡(luò)的調(diào)度方法。 藺玥等、Dutertre 等、徐乾舜等分別在全局時(shí)鐘精度方面進(jìn)行了研究；Maheshwarappa 等、Heilmann等也分別提出了基于不同優(yōu)化目的的TTE 調(diào)度方法；Kopetz提出了時(shí)間觸發(fā)多處理器片上系統(tǒng)的第一個(gè)學(xué)術(shù)模型，通過(guò)片上網(wǎng)絡(luò)實(shí)現(xiàn)多個(gè)片上IP 核的互連；Durrieu 等提出了通過(guò)TTE交換機(jī)實(shí)現(xiàn)多個(gè)多核芯片互連的跨層次體系結(jié)構(gòu)；Obermaisser 等提出了一個(gè)帶有網(wǎng)關(guān)的系統(tǒng)模型，用來(lái)實(shí)現(xiàn)芯片間的互相訪問(wèn)；汪晶晶等提出了一種芯片間時(shí)間觸發(fā)通信綜合規(guī)劃方法，包括對(duì)芯片間互連拓?fù)洹⑾⒌穆窂胶蜁r(shí)刻的規(guī)劃；孔韻雯提出了一個(gè)以時(shí)間觸發(fā)通信為主要互連模式，能夠容納混合關(guān)鍵性流量的統(tǒng)一互連結(jié)構(gòu)和芯片間互連網(wǎng)絡(luò)消息的調(diào)度方法。 在目前的解決方案中，調(diào)度消息時(shí)需要對(duì)消息進(jìn)行分組和排序，但都是根據(jù)消息的周期或幀長(zhǎng)，以容易調(diào)度為目的進(jìn)行排序，而忽略了TT 消息之間由應(yīng)用決定的順序關(guān)系。 同時(shí)，調(diào)度范圍也僅限于局域網(wǎng)或芯片間互連網(wǎng)絡(luò)自身，而未考慮到連接它們的網(wǎng)關(guān)芯片轉(zhuǎn)發(fā)調(diào)度，無(wú)法實(shí)現(xiàn)兩級(jí)不同網(wǎng)絡(luò)之間的互連和消息轉(zhuǎn)發(fā)。 當(dāng)TT 消息跨越骨干網(wǎng)互連和板級(jí)互連時(shí)，在全局同步時(shí)鐘控制下，由于2 種網(wǎng)絡(luò)中的TT 消息調(diào)度表生成方法互相獨(dú)立，因此2 張調(diào)度表中的消息順序也可能不同， TT消息到達(dá)和離開網(wǎng)關(guān)的時(shí)間也不一定連續(xù)， TT消息可能需要在到達(dá)網(wǎng)關(guān)后等待一段時(shí)間才能轉(zhuǎn)發(fā)，這段時(shí)間稱為網(wǎng)關(guān)內(nèi)等待時(shí)間(Waiting Time，WT)。 不同順序的調(diào)度表還可能造成原本應(yīng)在另一消息之后傳輸?shù)南⑻崆皞鬏?，從而使傳輸結(jié)果出現(xiàn)錯(cuò)誤。

對(duì)芯片間互連網(wǎng)絡(luò)網(wǎng)關(guān)設(shè)計(jì)時(shí)，為了解決由于離線調(diào)度表不同導(dǎo)致的TT 消息經(jīng)過(guò)網(wǎng)關(guān)前后順序依賴關(guān)系被打亂的問(wèn)題，并使得每條消息的等待時(shí)間盡可能短，本文考慮在順序依賴關(guān)系約束條件下的網(wǎng)關(guān)調(diào)度，給出不保序TT 消息轉(zhuǎn)發(fā)調(diào)度方法(Non-Order-Preserving Method， NOPM)和完全保序轉(zhuǎn)發(fā)調(diào)度方法(Order-Preserving Method， OPM)的等待時(shí)間計(jì)算方法。 并進(jìn)一步將2種方法結(jié)合，提出考慮依賴關(guān)系約束的部分保序TT 消息轉(zhuǎn)發(fā)調(diào)度方法(Partial-Order-Preserving Method， POPM)及其網(wǎng)關(guān)內(nèi)等待時(shí)間算法，在保證約束條件的同時(shí)減少了等待時(shí)間，并進(jìn)行了案例分析。 以規(guī)劃后的等待時(shí)間和是否滿足約束條件為標(biāo)準(zhǔn)，分別對(duì)3 種方法的規(guī)劃結(jié)果進(jìn)行了評(píng)價(jià)和對(duì)比。

2 系統(tǒng)模型

2.1 網(wǎng)關(guān)內(nèi)時(shí)間觸發(fā)消息模型

假設(shè)存在1 條進(jìn)入網(wǎng)關(guān)的時(shí)間觸發(fā)消息為M，則M 在網(wǎng)關(guān)中的屬性可由式(1)表示：

其中，P 為消息的周期，L 為消息的長(zhǎng)度， T為TT 消息到達(dá)網(wǎng)關(guān)的時(shí)間，T為TT 消息從網(wǎng)關(guān)離開的時(shí)間，WT 為TT 消息在網(wǎng)關(guān)中的等待時(shí)間。 WT 與T和T關(guān)系如式(2)所示：

此外，對(duì)于一系列TT 消息M，M，…，M，可能存在2 種情況：①TT 消息存在于1 個(gè)隊(duì)列中，它們具有嚴(yán)格的順序關(guān)系，即每一TT 幀都有唯一與其對(duì)應(yīng)的在其之后傳輸?shù)腡T 幀，一旦順序關(guān)系被打亂，就會(huì)影響傳遞結(jié)果，因此網(wǎng)關(guān)轉(zhuǎn)發(fā)過(guò)程中要保證隊(duì)列內(nèi)消息順序不變；②TT消息可能來(lái)自不同的芯片或傳感器，或經(jīng)過(guò)提前處理，使得TT 消息之間不具有順序關(guān)系，此時(shí)無(wú)論消息以何順序傳輸，都不會(huì)對(duì)結(jié)果產(chǎn)生任何影響，在網(wǎng)關(guān)轉(zhuǎn)發(fā)時(shí)基于減少等待時(shí)間的原則，對(duì)其發(fā)送順序進(jìn)行修改。 這2 種情況往往在一個(gè)系統(tǒng)中同時(shí)存在，因此需要考慮2 種情況下的轉(zhuǎn)發(fā)調(diào)度方法。

2.2 帶有網(wǎng)關(guān)的芯片間互連結(jié)構(gòu)

圖1 是TTE 拓?fù)浣Y(jié)構(gòu)的一個(gè)示例，該拓?fù)浣Y(jié)構(gòu)由端系統(tǒng)(A-F)，交換機(jī)(SW1、SW2)和雙向鏈路組成，其拓?fù)浣Y(jié)構(gòu)與采用普通以太網(wǎng)組網(wǎng)的拓?fù)浣Y(jié)構(gòu)類似。

圖1 TTE 拓?fù)浣Y(jié)構(gòu)示例Fig.1 An example of TTE topology

本文端系統(tǒng)可由電路板上的時(shí)間觸發(fā)芯片間綜合化互連網(wǎng)絡(luò)構(gòu)成。 在電路板內(nèi)，芯片之間通過(guò)物理鏈路以分布式結(jié)構(gòu)進(jìn)行互連，芯片之間采用全雙工通信，芯片的數(shù)量和布局根據(jù)傳輸?shù)男枨鬀Q定，一般是不對(duì)稱的。 TT 消息在芯片間通過(guò)物理鏈路傳輸，對(duì)于跨越電路板范圍的芯片以及芯片與模塊之間的互連，選擇某一芯片作為電路板內(nèi)片間互連的網(wǎng)關(guān)，同樣采用介質(zhì)無(wú)關(guān)接口，通過(guò)物理層驅(qū)動(dòng)器連接板外獨(dú)立的交換機(jī)節(jié)點(diǎn)，實(shí)現(xiàn)跨越板級(jí)層次數(shù)據(jù)流的端到端傳輸。 網(wǎng)關(guān)可以在滿足芯片間互連網(wǎng)絡(luò)和LAN 調(diào)度表的基礎(chǔ)上，對(duì)消息的觸發(fā)時(shí)間進(jìn)行重新規(guī)劃，并按照規(guī)劃后的觸發(fā)時(shí)間將其轉(zhuǎn)發(fā)至局域網(wǎng)中。

在孔韻雯提出的綜合化互連架構(gòu)中，帶有網(wǎng)關(guān)的芯片間互連結(jié)構(gòu)如圖2 所示，V1 ～V6 為具有時(shí)間觸發(fā)片上網(wǎng)絡(luò)的芯片，其中V3 被選為網(wǎng)關(guān)芯片，當(dāng)該芯片間互連網(wǎng)絡(luò)中的任意芯片發(fā)出的TT 消息數(shù)據(jù)流需要跨越板級(jí)向局域網(wǎng)中傳輸時(shí)，都必須先通過(guò)物理鏈路發(fā)送到該網(wǎng)關(guān)芯片，再由網(wǎng)關(guān)芯片向局域網(wǎng)中轉(zhuǎn)發(fā)。

圖2 帶有網(wǎng)關(guān)的芯片間互連結(jié)構(gòu)示意圖Fig.2 Off-chip interconnection topology with gateway

該結(jié)構(gòu)下已經(jīng)離線生成芯片間互連網(wǎng)絡(luò)和局域網(wǎng)的TT 消息調(diào)度表，網(wǎng)關(guān)芯片根據(jù)2 個(gè)時(shí)間觸發(fā)網(wǎng)絡(luò)的靜態(tài)調(diào)度表來(lái)派發(fā)消息，在此過(guò)程中，已經(jīng)為某條消息預(yù)先分配好的時(shí)隙可以空閑，但不能傳輸其他消息。 當(dāng)1 條TT 消息到達(dá)網(wǎng)關(guān)后，需要在網(wǎng)關(guān)芯片中等待，這段時(shí)間即為等待時(shí)間。圖3 展示了消息2 在網(wǎng)關(guān)中等待的情況。 由于消息2 在到達(dá)網(wǎng)關(guān)時(shí)沒(méi)有趕上LAN 的前一個(gè)觸發(fā)時(shí)刻，因此需要等待下一個(gè)觸發(fā)時(shí)刻發(fā)送，在此期間，消息2 暫存在網(wǎng)關(guān)中，到達(dá)時(shí)刻和實(shí)際觸發(fā)時(shí)刻的差即為等待時(shí)間。 若消息1 和2 存在著由應(yīng)用決定的順序依賴關(guān)系時(shí)，網(wǎng)關(guān)對(duì)其進(jìn)行轉(zhuǎn)發(fā)的時(shí)候還需要滿足約束條件，等待時(shí)間也會(huì)產(chǎn)生變化。

圖3 一種產(chǎn)生等待的情況Fig.3 A situation producing waiting time

3 時(shí)間觸發(fā)消息轉(zhuǎn)發(fā)調(diào)度等待時(shí)間算法

3.1 NOPM 方法等待時(shí)間算法

NOPM 方法不考慮TT 消息間的順序依賴關(guān)系，僅在使得每條消息在網(wǎng)關(guān)內(nèi)的等待時(shí)間最短的前提下規(guī)劃。 此時(shí)，每條TT 消息在網(wǎng)關(guān)內(nèi)的等待時(shí)間僅與其首次到達(dá)網(wǎng)關(guān)的時(shí)間at以及LAN 調(diào)度表中規(guī)定的觸發(fā)時(shí)間T有關(guān)，且對(duì)于同一TT 消息在不同周期產(chǎn)生的不同實(shí)例，它們?cè)诰W(wǎng)關(guān)內(nèi)的等待時(shí)間也都完全一致。 從芯片間互連網(wǎng)絡(luò)時(shí)間觸發(fā)消息調(diào)度表中，可以得到TT 消息的周期、長(zhǎng)度和消息的第一個(gè)TT 幀到達(dá)網(wǎng)關(guān)的時(shí)間，從LAN 調(diào)度表中，也可以得到每條TT 消息在LAN 調(diào)度表中的理論觸發(fā)時(shí)間T。 對(duì)于任一消息，其某幀到達(dá)網(wǎng)關(guān)的時(shí)間T與首幀到達(dá)網(wǎng)關(guān)的時(shí)間at滿足式(3)：

其中j 為非負(fù)整數(shù)，其數(shù)值為在該幀之前到達(dá)網(wǎng)關(guān)的幀數(shù)，P為消息M的周期。 對(duì)于消息M的1 個(gè)TT 幀，其實(shí)際觸發(fā)時(shí)刻T必然滿足式(4)：

式中，k 為非負(fù)整數(shù)。 在調(diào)度時(shí)，為了使等待時(shí)間最短，根據(jù)TT 消息到達(dá)網(wǎng)關(guān)時(shí)間，在所有調(diào)度表分配的時(shí)隙中尋找最小的滿足約束條件的時(shí)刻作為該消息的觸發(fā)時(shí)間，即尋找最小的k 值。NOPM 中TT 消息等待時(shí)間計(jì)算方法如算法1所示。

算法1：NOPM 等待時(shí)間算法輸入：消息首次到達(dá)網(wǎng)關(guān)時(shí)間ati，消息周期Pi，消息在LAN 中的發(fā)送起始時(shí)間偏移量Ti輸出：消息在網(wǎng)關(guān)內(nèi)等待時(shí)間WTi Function NOPMWT 1：k ←0 2： while Ti + k × Pi ＜ati do 3： k ←k + 1 4： end while 5：WTi ←Ti + k × Pi - ati End function?

在算法1 中，對(duì)于1 條固定的消息，可能的觸發(fā)時(shí)刻如式(4)所示，根據(jù)離線調(diào)度表的性質(zhì)，每一TT 幀的等待時(shí)間WT均為定值，將TT 消息列表中的消息全部用上述方法運(yùn)算一遍，即可得到所有消息的等待時(shí)間。 對(duì)于任意一條消息，在已知到達(dá)時(shí)間T和等待時(shí)間WT 的前提下，可求得觸發(fā)時(shí)間T如式(5)所示：

據(jù)此可得到每條消息的每個(gè)TT 幀的觸發(fā)時(shí)間。 此方法完全不考慮TT 消息間的順序依賴關(guān)系，雖然最大限度降低了等待時(shí)間，但是對(duì)于一些具有順序依賴性的消息而言，可能會(huì)破壞其順序關(guān)系，從而影響消息傳輸結(jié)果。

3.2 OPM 方法等待時(shí)間算法

OPM 方法的目的是保證TT 消息在經(jīng)過(guò)網(wǎng)關(guān)前后的順序完全一致，在OPM 規(guī)劃過(guò)程中，網(wǎng)關(guān)讀取LAN 調(diào)度表，獲得每條TT 消息被分配到的所有時(shí)隙，并通過(guò)讀取芯片間互連網(wǎng)絡(luò)的調(diào)度表，計(jì)算得到TT 消息順序，在可能的觸發(fā)時(shí)間上重新規(guī)劃每條TT 消息流的觸發(fā)時(shí)間，使其與到達(dá)網(wǎng)關(guān)的消息順序保持嚴(yán)格一致。

一組TT 消息中，所有消息周期的最小公倍數(shù)稱為該組TT 消息的超周期(Hyperperiod)。 根據(jù)TT 流量的調(diào)度規(guī)則，在每個(gè)超周期內(nèi)TT 消息的調(diào)度結(jié)果都與其他超周期相同。 使用到達(dá)時(shí)間矩陣A來(lái)表示在第一個(gè)超周期內(nèi)通過(guò)網(wǎng)關(guān)的各個(gè)TT 消息的到達(dá)時(shí)間與順序。 矩陣A的計(jì)算方法如算法2 所示。

?算法2：到達(dá)時(shí)間矩陣A 計(jì)算方法輸入：TT 消息周期集合P，首次到達(dá)網(wǎng)關(guān)時(shí)間集合AT，超周期hyperperiod，消息數(shù)量n輸出：到達(dá)時(shí)間矩陣At 1 Function ATMCAUL 1：m ←hyperperiod/gcd{P1，P2…，Pn}2：At1 ←Om×n，3：AT ＝Sort{[at1，at2…，atn]}4：P ←ResortAT(P)5：Δt ←hyperperiod/m，a1 ←AT(1)6：for i ←1 to n do 7： x ←hyperperiod/P(i)8： for j ←1 to xdo 9： tem ＝AT(i) + (j - 1) × P(i)10： for k ←1 to m do 11： if a1 +(k -1)Δt ≤tem ＜a1 +kΔt then

12： At1(k，i) ←tem 13： end if 14： end for 15： end for 16：end for 17：return At1 End function

在算法2 中， gcd 為求最大公約數(shù)的函數(shù)，Sort 函數(shù)將每條消息第一個(gè)TT 幀到達(dá)時(shí)間按照從小到大的順序重新排序，并存放于數(shù)組AT 中。ResortAT 函數(shù)將周期集合P 按照與AT 相同的順序重新排序。 接下來(lái)根據(jù)到達(dá)時(shí)間的先后求得矩陣A，該矩陣具有如下特征：

1)該矩陣每一行的非零值均為升序排列；

2)該矩陣每一列的非零值均為升序排列；

3)a、b 分別為該矩陣在第i 行和第j 行的任意兩個(gè)非零值，若i＞j，則a＞b；若i＜j，則a＜b。

計(jì)算OPM 中的TT 消息等待時(shí)間時(shí)，在滿足約束條件前提下，在LAN 的調(diào)度表中尋找適合每條消息的觸發(fā)時(shí)間，并與到達(dá)時(shí)間相減得到該TT消息在網(wǎng)關(guān)中的等待時(shí)間。 OPM 求解TT 消息等待時(shí)間的算法如算法3 所示。

算法3：OPM 方法中TT 消息等待時(shí)間輸入：前3 個(gè)超周期的到達(dá)時(shí)間矩陣At 1，At 2，At 3，消息周期集合P，LAN 中消息發(fā)送起始時(shí)間偏移量集合T輸出：前2 個(gè)超周期內(nèi)到達(dá)網(wǎng)關(guān)的消息等待時(shí)間矩陣WT1，WT2，等待時(shí)間穩(wěn)定增量矩陣ΔWT Function OPMWT 1：A ←(AT t3)T，B ←A，[m，n]←size(B)3：tem ←B(1，1)3：for i ←1 to m do 4： for j ←1 to ndo 5： if B(i，j) ≠0 then 6： if T(j) ＜tem then 7： while T(j) ＜tem do 8： T(j) ←T(j) + P(j)9： end while 10： end if 11： if T(j) ＜A(i，j) then 12： while T(j) ＜A(i，j) do t1，AT t2，AT

13： T(j) ←T(j) + P(j)14： end while 15： B(i，j) ←T(j)，tem ←T(j)16： end if 17： end if 18： end for 19：end for 20：B1，B2，B3 ←DivideMatrix(B，m/3)21：WT1 ←B1 -At1，WT2 ←B2 -At2，WT3 ←B3 -At3 22：ΔWT ←WT3 - WT2 End function

在算法3 中，B 為與A 行列數(shù)相同的矩陣。在B 中每一個(gè)非零值都表示A 中相同位置的到達(dá)時(shí)間對(duì)應(yīng)的觸發(fā)時(shí)間。

由于每條TT 消息都是在前一條消息后尋找最近的觸發(fā)時(shí)間，且每個(gè)超周期內(nèi)都由相同數(shù)量的消息以相同順序進(jìn)行傳輸，因此，只要經(jīng)歷過(guò)一次完整循環(huán)后，每個(gè)超周期的A內(nèi)相同位置的消息都會(huì)對(duì)上一超周期A內(nèi)該位置消息的等待時(shí)間增加產(chǎn)生相同的影響，即在對(duì)第1 個(gè)超周期矩陣A內(nèi)的消息進(jìn)行規(guī)劃后，從第2 個(gè)超周期矩陣A開始，每個(gè)超周期發(fā)送時(shí)間規(guī)劃結(jié)束后產(chǎn)生的等待時(shí)間矩陣WT， 總存在式(6)關(guān)系：

為了求得延遲時(shí)間的初始值及其穩(wěn)定增量，需要計(jì)算前3 個(gè)超周期內(nèi)的等待時(shí)間WT、WT、WT，求出等待時(shí)間的初值和穩(wěn)態(tài)增量ΔWT，并得到等待時(shí)間矩陣WT的數(shù)學(xué)表示，如式(7)所示：

之后可將WT中與A中位置相同的數(shù)提取出來(lái)就可得到每條消息的每幀在通過(guò)網(wǎng)關(guān)時(shí)的等待時(shí)間。 并由式(2)得到每條消息的等待時(shí)間，網(wǎng)關(guān)對(duì)每個(gè)TT 幀按照計(jì)算得到的T進(jìn)行轉(zhuǎn)發(fā)，即可保證所有消息再通過(guò)網(wǎng)關(guān)前后的順序一致。

在該規(guī)劃方法下，只要網(wǎng)關(guān)中還留存有其他在某TT 消息前面的TT 消息，該TT 消息就不能被發(fā)送。 在這種情況下，很容易導(dǎo)致TT消息數(shù)據(jù)流在網(wǎng)關(guān)中產(chǎn)生累積，導(dǎo)致了系統(tǒng)的過(guò)度配置(Overprovisioning)。 因此，OPM 方法只在對(duì)順序要求十分嚴(yán)格的系統(tǒng)中適用。

3. 3 POPM 及等待時(shí)間算法

POPM 考慮了前2 種方法的優(yōu)劣性，采用分組保序的思路，對(duì)于存在先后順序依賴關(guān)系的TT 消息序列使用OPM 規(guī)劃；對(duì)不具有順序依賴性的TT 消息使用NOPM 規(guī)劃，得到的網(wǎng)關(guān)內(nèi)等待時(shí)間在符合約束條件的基礎(chǔ)上盡量減少單條消息的等待時(shí)間。 通過(guò)部分保序網(wǎng)關(guān)內(nèi)時(shí)間觸發(fā)消息等待時(shí)間計(jì)算方法計(jì)算等待時(shí)間對(duì)規(guī)劃效果進(jìn)行評(píng)價(jià)，POPM 等待時(shí)間計(jì)算方法如算法4 所示。

算法4：POPM 網(wǎng)關(guān)內(nèi)時(shí)間觸發(fā)消息等待時(shí)間計(jì)算方法輸入：包含具有順序依賴關(guān)系的TT 消息的前3個(gè)超周期的到達(dá)時(shí)間矩陣集合[A1，t 1 A2，t 2 A3，t 3]， [A2，t 1 A2，t 2 A3，t 3]，…， [An 1，t 1 An 1，t 2 An 1，t 3]，周期集合P1， P2，…， Pn 1， LAN 中消息發(fā)送起始時(shí)間偏移量集合T1， T2，…，Tn 1，無(wú)依賴關(guān)系消息到達(dá)時(shí)間at1，at2，… atn 2，周期P1， P2，…， Pn 2，LAN 中消息發(fā)送起始時(shí)間偏移量T1，T2，…，Tn 2輸出：等待時(shí)間矩陣集合[WT1，1 WT1，2 ΔWT1]，[WT2，1 WT2，2ΔWT2]，…[WTn 1，1 WTn 1，2ΔWTn 1]，單條消息等待時(shí)間WT1， WT2，…，WTn 2 Function POPMWT 1： for i ←1 to n1 do Ai ＝(AT i，t1，AT i，t2，AT i，t3)T[WTi，1，WTi，2，ΔWTi] ←OPMWT(Ai，Ti，Pi)4： end for 5： for j ←1 to n2 do 6：WTj ←SWTIG(atj，Pj，Tj)7： end for End function

該調(diào)度方法中，首先將所有具有順序依賴性的TT 消息的等待時(shí)間使用算法3 求出，在將其他獨(dú)立TT 消息自身的等待時(shí)間由算法1 求得，最終根據(jù)每條消息的等待時(shí)間由式(5)求得每條消息的觸發(fā)時(shí)間，在約束條件滿足的前提下，實(shí)現(xiàn)了最短等待時(shí)間規(guī)劃。

4 案例分析

4.1 參數(shù)設(shè)置

本文采用已有的芯片間互連網(wǎng)絡(luò)調(diào)度表和LAN 調(diào)度表進(jìn)行驗(yàn)證，其中芯片間互連網(wǎng)絡(luò)調(diào)度表由汪晶晶等提出的方法求得，LAN 調(diào)度表由宋梓旭等提出的方法求得。 消息的首次到達(dá)網(wǎng)關(guān)時(shí)間和LAN 調(diào)度表中首次觸發(fā)時(shí)刻都可從調(diào)度表中直接讀取。 TT 消息由芯片間互連網(wǎng)絡(luò)中的芯片發(fā)出，經(jīng)由網(wǎng)關(guān)芯片傳入局域網(wǎng)，消息集合的具體參數(shù)如表1 所示，TT 消息的幀長(zhǎng)從64 ～1518 Byte 中隨機(jī)選取，其周期取值為2ms，n 為0 ～4 之間的整數(shù)。 其中消息M，M和M，M分別具有順序依賴關(guān)系。 它們分別與芯片間互連網(wǎng)絡(luò)中以及LAN中的其他消息共同參與調(diào)度，得到關(guān)于它們的2 組調(diào)度數(shù)據(jù)，其中芯片間互連網(wǎng)絡(luò)調(diào)度表中已給出首次到達(dá)網(wǎng)關(guān)的時(shí)間，且到達(dá)時(shí)間滿足約束條件。 在此條件下，分別用OPM、NOPM和POPM 規(guī)劃網(wǎng)關(guān)內(nèi)消息，并就等待時(shí)間和順序關(guān)系兩方面來(lái)評(píng)價(jià)規(guī)劃結(jié)果。

表1 消息集合參數(shù)Table 1 Parameters of the message set

4.2 不同算法的規(guī)劃結(jié)果比較

4.2.1 NOPM 規(guī)劃結(jié)果

當(dāng)4.1 節(jié)中的消息組利用NOPM 進(jìn)行規(guī)劃時(shí)，使用算法1 求得每條TT 消息的等待時(shí)間，如表2 所示。

在此規(guī)劃方法下，這6 條TT 消息所有周期產(chǎn)生的TT 幀在網(wǎng)關(guān)中等待時(shí)間均相等，且為所有規(guī)劃方法中可得出的等待時(shí)間最小值。

表2 NOPM 調(diào)度后TT 消息等待時(shí)間Table 2 Waiting time of TT messages after NOPM scheduling

4.2.2 OPM 規(guī)劃結(jié)果

根據(jù)3.2 節(jié)中描述，可知該組TT 消息的超周期為16 ms，將各個(gè)消息的周期和首次到達(dá)網(wǎng)關(guān)時(shí)間代入算法2，可得前3 個(gè)超周期的到達(dá)時(shí)間矩陣A、A、A分別為式(8)、(9)：

其中矩陣HP 如式(10)所示，且行列數(shù)與A相同。

從A第一行可知每列所代表的消息分別為M、M、M、M、M、M，將得到的到達(dá)時(shí)間矩陣A、A、A代入算法3，得到前2 個(gè)超周期內(nèi)輸入消息的等待時(shí)間WT，WT和等待時(shí)間穩(wěn)定增量矩陣ΔWT，分別為式(11)～(13)：

第i 個(gè)超周期內(nèi)到達(dá)網(wǎng)關(guān)的所有TT 消息的等待時(shí)間矩陣可表示為式(14)：

4.2.3 POPM 規(guī)劃結(jié)果

在POPM 中，先將具有順序依賴關(guān)系的TT消息分為一組，分別求得各個(gè)組的到達(dá)時(shí)間矩陣。在本文中消息M，M為一組，消息M，M為一組，將這2 組TT 消息前3 個(gè)超周期到達(dá)網(wǎng)關(guān)時(shí)間矩陣合并，分別記為A，A，具體如式(15)、(16)所示：

對(duì)于第1 組消息，網(wǎng)關(guān)算法需要使其在每個(gè)周期進(jìn)出網(wǎng)關(guān)前后均滿足M→M的順序，對(duì)于第2 組消息，需要使其出網(wǎng)關(guān)時(shí)滿足M→M的順序。 使用算法3 對(duì)其等待時(shí)間進(jìn)行計(jì)算，得到其等待時(shí)間矩陣如式(17)～(20)所示：

對(duì)于M，M，由于其與其他消息無(wú)順序依賴關(guān)系，因此直接使用算法1，求得其等待時(shí)間為式(21)～(22)：

由式(17)-(22)可以看出本案例中所有TT消息所有周期所產(chǎn)生的實(shí)例在網(wǎng)關(guān)中的等待時(shí)間均為一個(gè)定值，不存在隨著產(chǎn)生的數(shù)據(jù)流越來(lái)越多導(dǎo)致等待時(shí)間累積的情況。

4.2.4 結(jié)果分析

從等待時(shí)間方面考慮，OPM 認(rèn)為所有消息都具有順序依賴關(guān)系，因此會(huì)產(chǎn)生許多不必要的等待，特別是當(dāng)小周期消息等待大周期消息時(shí)，會(huì)存在大量的等待時(shí)間，當(dāng)?shù)竭_(dá)網(wǎng)關(guān)的TT 幀累積時(shí)，后來(lái)的TT 幀的等待時(shí)間也會(huì)越來(lái)越多。 POPM只產(chǎn)生必要的順序等待，減少了由于排隊(duì)而產(chǎn)生的等待時(shí)間累積，本文分別以單條TT 消息的總等待時(shí)間以前10 個(gè)超周期內(nèi)到達(dá)網(wǎng)關(guān)的所有TT消息幀的總等待時(shí)間為例，將POPM 與OPM 進(jìn)行比較。 圖4 展示了M至M每條消息在2 種方法下等待時(shí)間累積隨轉(zhuǎn)發(fā)的TT 幀數(shù)的變化情況。

圖4 單條TT 消息前10 個(gè)TT 幀總等待時(shí)間Fig.4 The total waiting time in first 10 frames of single message

從圖4 中可看出對(duì)于每條TT 消息，使用POPM 都會(huì)減少其在網(wǎng)關(guān)中的等待時(shí)間，且隨著消息傳輸TT 幀數(shù)量的增加，減少等待時(shí)間的效果會(huì)越來(lái)越明顯。

從整體來(lái)看，前10 個(gè)超周期內(nèi)到達(dá)網(wǎng)關(guān)的所有TT 消息幀的總等待時(shí)間變化趨勢(shì)如圖5 所示。從圖中可以看出，在本文案例中POPM 的總等待時(shí)間比OPM 明顯減少。

圖5 OPM 與POPM 方法前10 個(gè)超周期總等待時(shí)間Fig.5 The total waiting time in first 10 hyper periods of OPM and POPM

從保證約束條件方面考慮，NOPM 只考慮單條TT 消息選擇使自身的等待時(shí)間最短的觸發(fā)時(shí)刻，從而使得具有順序依賴關(guān)系的TT 消息順序混亂，在本文案例中，如圖6 所示，M的每一TT幀都有唯一與其對(duì)應(yīng)的M的一個(gè)TT 幀，當(dāng)它們以特定順序傳遞時(shí)，消息的傳遞結(jié)果才能正確，但是在NOPM 中，每個(gè)周期內(nèi)消息M、M的TT 幀之間的順序關(guān)系被破壞，在此情況下調(diào)度的結(jié)果可能也會(huì)改變。

圖6 NOPM 破壞TT 消息順序Fig.6 NOPM destroys TT message sequence

使用POPM 時(shí)，由于消息M、M處于一個(gè)具有順序依賴關(guān)系的消息組中，在調(diào)度時(shí)會(huì)根據(jù)其順序關(guān)系調(diào)整實(shí)際觸發(fā)時(shí)間，如圖7 所示。 由于最近的觸發(fā)時(shí)間會(huì)破壞順序關(guān)系，將消息M轉(zhuǎn)到下一個(gè)觸發(fā)時(shí)間觸發(fā)，雖然會(huì)造成比原來(lái)長(zhǎng)的等待，但是保證了順序關(guān)系。

圖7 POPM 方法下消息M2，M3 的實(shí)際觸發(fā)時(shí)間Fig.7 The real trigger time of message M2 and M3 in POPM

經(jīng)過(guò)分析，POPM 方法分別繼承了OPM 和NOPM 的優(yōu)點(diǎn)，可以在滿足約束條件的情況下完成對(duì)網(wǎng)關(guān)內(nèi)TT 消息的規(guī)劃，且盡可能減小了等待時(shí)間。

5 結(jié)論

1)本文提出的網(wǎng)關(guān)內(nèi)TT 消息等待時(shí)間算法可以在系統(tǒng)運(yùn)行前計(jì)算網(wǎng)關(guān)內(nèi)等待時(shí)間，為調(diào)整網(wǎng)絡(luò)TT 消息調(diào)度表提供參考。

2)不保序轉(zhuǎn)發(fā)調(diào)度方法(NOPM)和完全保序轉(zhuǎn)發(fā)調(diào)度方法(OPM)可分別實(shí)現(xiàn)網(wǎng)關(guān)內(nèi)等待時(shí)間最短和保序性要求，但無(wú)法全部滿足。

3) 本文提出的部分保序轉(zhuǎn)發(fā)調(diào)度方法(POPM)解決了滿足順序依賴和減少等待時(shí)間為目標(biāo)的轉(zhuǎn)發(fā)調(diào)度問(wèn)題。