板級互連網關的時間觸發消息轉發調度方法

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

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

1 引言

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

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

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

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

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

2 系統模型

2.1 網關內時間觸發消息模型

假設存在1 條進入網關的時間觸發消息為M，則M 在網關中的屬性可由式(1)表示：

其中，P 為消息的周期，L 為消息的長度， T為TT 消息到達網關的時間，T為TT 消息從網關離開的時間，WT 為TT 消息在網關中的等待時間。 WT 與T和T關系如式(2)所示：

此外，對于一系列TT 消息M，M，…，M，可能存在2 種情況：①TT 消息存在于1 個隊列中，它們具有嚴格的順序關系，即每一TT 幀都有唯一與其對應的在其之后傳輸的TT 幀，一旦順序關系被打亂，就會影響傳遞結果，因此網關轉發過程中要保證隊列內消息順序不變；②TT消息可能來自不同的芯片或傳感器，或經過提前處理，使得TT 消息之間不具有順序關系，此時無論消息以何順序傳輸，都不會對結果產生任何影響，在網關轉發時基于減少等待時間的原則，對其發送順序進行修改。 這2 種情況往往在一個系統中同時存在，因此需要考慮2 種情況下的轉發調度方法。

2.2 帶有網關的芯片間互連結構

圖1 是TTE 拓撲結構的一個示例，該拓撲結構由端系統(A-F)，交換機(SW1、SW2)和雙向鏈路組成，其拓撲結構與采用普通以太網組網的拓撲結構類似。

圖1 TTE 拓撲結構示例Fig.1 An example of TTE topology

本文端系統可由電路板上的時間觸發芯片間綜合化互連網絡構成。 在電路板內，芯片之間通過物理鏈路以分布式結構進行互連，芯片之間采用全雙工通信，芯片的數量和布局根據傳輸的需求決定，一般是不對稱的。 TT 消息在芯片間通過物理鏈路傳輸，對于跨越電路板范圍的芯片以及芯片與模塊之間的互連，選擇某一芯片作為電路板內片間互連的網關，同樣采用介質無關接口，通過物理層驅動器連接板外獨立的交換機節點，實現跨越板級層次數據流的端到端傳輸。 網關可以在滿足芯片間互連網絡和LAN 調度表的基礎上，對消息的觸發時間進行重新規劃，并按照規劃后的觸發時間將其轉發至局域網中。

在孔韻雯提出的綜合化互連架構中，帶有網關的芯片間互連結構如圖2 所示，V1 ～V6 為具有時間觸發片上網絡的芯片，其中V3 被選為網關芯片，當該芯片間互連網絡中的任意芯片發出的TT 消息數據流需要跨越板級向局域網中傳輸時，都必須先通過物理鏈路發送到該網關芯片，再由網關芯片向局域網中轉發。

圖2 帶有網關的芯片間互連結構示意圖Fig.2 Off-chip interconnection topology with gateway

該結構下已經離線生成芯片間互連網絡和局域網的TT 消息調度表，網關芯片根據2 個時間觸發網絡的靜態調度表來派發消息，在此過程中，已經為某條消息預先分配好的時隙可以空閑，但不能傳輸其他消息。 當1 條TT 消息到達網關后，需要在網關芯片中等待，這段時間即為等待時間。圖3 展示了消息2 在網關中等待的情況。 由于消息2 在到達網關時沒有趕上LAN 的前一個觸發時刻，因此需要等待下一個觸發時刻發送，在此期間，消息2 暫存在網關中，到達時刻和實際觸發時刻的差即為等待時間。 若消息1 和2 存在著由應用決定的順序依賴關系時，網關對其進行轉發的時候還需要滿足約束條件，等待時間也會產生變化。

圖3 一種產生等待的情況Fig.3 A situation producing waiting time

3 時間觸發消息轉發調度等待時間算法

3.1 NOPM 方法等待時間算法

NOPM 方法不考慮TT 消息間的順序依賴關系，僅在使得每條消息在網關內的等待時間最短的前提下規劃。 此時，每條TT 消息在網關內的等待時間僅與其首次到達網關的時間at以及LAN 調度表中規定的觸發時間T有關，且對于同一TT 消息在不同周期產生的不同實例，它們在網關內的等待時間也都完全一致。 從芯片間互連網絡時間觸發消息調度表中，可以得到TT 消息的周期、長度和消息的第一個TT 幀到達網關的時間，從LAN 調度表中，也可以得到每條TT 消息在LAN 調度表中的理論觸發時間T。 對于任一消息，其某幀到達網關的時間T與首幀到達網關的時間at滿足式(3)：

其中j 為非負整數，其數值為在該幀之前到達網關的幀數，P為消息M的周期。 對于消息M的1 個TT 幀，其實際觸發時刻T必然滿足式(4)：

式中，k 為非負整數。 在調度時，為了使等待時間最短，根據TT 消息到達網關時間，在所有調度表分配的時隙中尋找最小的滿足約束條件的時刻作為該消息的觸發時間，即尋找最小的k 值。NOPM 中TT 消息等待時間計算方法如算法1所示。

算法1：NOPM 等待時間算法輸入：消息首次到達網關時間ati，消息周期Pi，消息在LAN 中的發送起始時間偏移量Ti輸出：消息在網關內等待時間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 中，對于1 條固定的消息，可能的觸發時刻如式(4)所示，根據離線調度表的性質，每一TT 幀的等待時間WT均為定值，將TT 消息列表中的消息全部用上述方法運算一遍，即可得到所有消息的等待時間。 對于任意一條消息，在已知到達時間T和等待時間WT 的前提下，可求得觸發時間T如式(5)所示：

據此可得到每條消息的每個TT 幀的觸發時間。 此方法完全不考慮TT 消息間的順序依賴關系，雖然最大限度降低了等待時間，但是對于一些具有順序依賴性的消息而言，可能會破壞其順序關系，從而影響消息傳輸結果。

3.2 OPM 方法等待時間算法

OPM 方法的目的是保證TT 消息在經過網關前后的順序完全一致，在OPM 規劃過程中，網關讀取LAN 調度表，獲得每條TT 消息被分配到的所有時隙，并通過讀取芯片間互連網絡的調度表，計算得到TT 消息順序，在可能的觸發時間上重新規劃每條TT 消息流的觸發時間，使其與到達網關的消息順序保持嚴格一致。

一組TT 消息中，所有消息周期的最小公倍數稱為該組TT 消息的超周期(Hyperperiod)。 根據TT 流量的調度規則，在每個超周期內TT 消息的調度結果都與其他超周期相同。 使用到達時間矩陣A來表示在第一個超周期內通過網關的各個TT 消息的到達時間與順序。 矩陣A的計算方法如算法2 所示。

?算法2：到達時間矩陣A 計算方法輸入：TT 消息周期集合P，首次到達網關時間集合AT，超周期hyperperiod，消息數量n輸出：到達時間矩陣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 為求最大公約數的函數，Sort 函數將每條消息第一個TT 幀到達時間按照從小到大的順序重新排序，并存放于數組AT 中。ResortAT 函數將周期集合P 按照與AT 相同的順序重新排序。 接下來根據到達時間的先后求得矩陣A，該矩陣具有如下特征：

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

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

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

計算OPM 中的TT 消息等待時間時，在滿足約束條件前提下，在LAN 的調度表中尋找適合每條消息的觸發時間，并與到達時間相減得到該TT消息在網關中的等待時間。 OPM 求解TT 消息等待時間的算法如算法3 所示。

算法3：OPM 方法中TT 消息等待時間輸入：前3 個超周期的到達時間矩陣At 1，At 2，At 3，消息周期集合P，LAN 中消息發送起始時間偏移量集合T輸出：前2 個超周期內到達網關的消息等待時間矩陣WT1，WT2，等待時間穩定增量矩陣Δ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 行列數相同的矩陣。在B 中每一個非零值都表示A 中相同位置的到達時間對應的觸發時間。

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

為了求得延遲時間的初始值及其穩定增量，需要計算前3 個超周期內的等待時間WT、WT、WT，求出等待時間的初值和穩態增量ΔWT，并得到等待時間矩陣WT的數學表示，如式(7)所示：

之后可將WT中與A中位置相同的數提取出來就可得到每條消息的每幀在通過網關時的等待時間。 并由式(2)得到每條消息的等待時間，網關對每個TT 幀按照計算得到的T進行轉發，即可保證所有消息再通過網關前后的順序一致。

在該規劃方法下，只要網關中還留存有其他在某TT 消息前面的TT 消息，該TT 消息就不能被發送。 在這種情況下，很容易導致TT消息數據流在網關中產生累積，導致了系統的過度配置(Overprovisioning)。 因此，OPM 方法只在對順序要求十分嚴格的系統中適用。

3. 3 POPM 及等待時間算法

POPM 考慮了前2 種方法的優劣性，采用分組保序的思路，對于存在先后順序依賴關系的TT 消息序列使用OPM 規劃；對不具有順序依賴性的TT 消息使用NOPM 規劃，得到的網關內等待時間在符合約束條件的基礎上盡量減少單條消息的等待時間。 通過部分保序網關內時間觸發消息等待時間計算方法計算等待時間對規劃效果進行評價，POPM 等待時間計算方法如算法4 所示。

算法4：POPM 網關內時間觸發消息等待時間計算方法輸入：包含具有順序依賴關系的TT 消息的前3個超周期的到達時間矩陣集合[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 中消息發送起始時間偏移量集合T1， T2，…，Tn 1，無依賴關系消息到達時間at1，at2，… atn 2，周期P1， P2，…， Pn 2，LAN 中消息發送起始時間偏移量T1，T2，…，Tn 2輸出：等待時間矩陣集合[WT1，1 WT1，2 ΔWT1]，[WT2，1 WT2，2ΔWT2]，…[WTn 1，1 WTn 1，2ΔWTn 1]，單條消息等待時間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

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

4 案例分析

4.1 參數設置

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

表1 消息集合參數Table 1 Parameters of the message set

4.2 不同算法的規劃結果比較

4.2.1 NOPM 規劃結果

當4.1 節中的消息組利用NOPM 進行規劃時，使用算法1 求得每條TT 消息的等待時間，如表2 所示。

在此規劃方法下，這6 條TT 消息所有周期產生的TT 幀在網關中等待時間均相等，且為所有規劃方法中可得出的等待時間最小值。

表2 NOPM 調度后TT 消息等待時間Table 2 Waiting time of TT messages after NOPM scheduling

4.2.2 OPM 規劃結果

根據3.2 節中描述，可知該組TT 消息的超周期為16 ms，將各個消息的周期和首次到達網關時間代入算法2，可得前3 個超周期的到達時間矩陣A、A、A分別為式(8)、(9)：

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

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

第i 個超周期內到達網關的所有TT 消息的等待時間矩陣可表示為式(14)：

4.2.3 POPM 規劃結果

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

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

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

由式(17)-(22)可以看出本案例中所有TT消息所有周期所產生的實例在網關中的等待時間均為一個定值，不存在隨著產生的數據流越來越多導致等待時間累積的情況。

4.2.4 結果分析

從等待時間方面考慮，OPM 認為所有消息都具有順序依賴關系，因此會產生許多不必要的等待，特別是當小周期消息等待大周期消息時，會存在大量的等待時間，當到達網關的TT 幀累積時，后來的TT 幀的等待時間也會越來越多。 POPM只產生必要的順序等待，減少了由于排隊而產生的等待時間累積，本文分別以單條TT 消息的總等待時間以前10 個超周期內到達網關的所有TT消息幀的總等待時間為例，將POPM 與OPM 進行比較。 圖4 展示了M至M每條消息在2 種方法下等待時間累積隨轉發的TT 幀數的變化情況。

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

從圖4 中可看出對于每條TT 消息，使用POPM 都會減少其在網關中的等待時間，且隨著消息傳輸TT 幀數量的增加，減少等待時間的效果會越來越明顯。

從整體來看，前10 個超周期內到達網關的所有TT 消息幀的總等待時間變化趨勢如圖5 所示。從圖中可以看出，在本文案例中POPM 的總等待時間比OPM 明顯減少。

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

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

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

使用POPM 時，由于消息M、M處于一個具有順序依賴關系的消息組中，在調度時會根據其順序關系調整實際觸發時間，如圖7 所示。 由于最近的觸發時間會破壞順序關系，將消息M轉到下一個觸發時間觸發，雖然會造成比原來長的等待，但是保證了順序關系。

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

經過分析，POPM 方法分別繼承了OPM 和NOPM 的優點，可以在滿足約束條件的情況下完成對網關內TT 消息的規劃，且盡可能減小了等待時間。

5 結論

1)本文提出的網關內TT 消息等待時間算法可以在系統運行前計算網關內等待時間，為調整網絡TT 消息調度表提供參考。

2)不保序轉發調度方法(NOPM)和完全保序轉發調度方法(OPM)可分別實現網關內等待時間最短和保序性要求，但無法全部滿足。

3) 本文提出的部分保序轉發調度方法(POPM)解決了滿足順序依賴和減少等待時間為目標的轉發調度問題。