板級互連網(wǎng)關(guān)的時間觸發(fā)消息轉(zhuǎn)發(fā)調(diào)度方法

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

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

1 引言

綜合模塊化航電系統(tǒng)(Integrated Modular Avionics，IMA)架構(gòu)在航天電子領(lǐng)域得到了廣泛應(yīng)用。 NASA 提議將IMA 架構(gòu)與集成安全關(guān)鍵高級航空電子通信和控制(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)采用具有時間觸發(fā)通信能力的交換式網(wǎng)絡(luò)作為航天平臺的骨干綜合化互連。 隨著電子信息系統(tǒng)向著多核處理、片上系統(tǒng)(System on Chip， SoC)和智能化方向發(fā)展，出現(xiàn)了微小型化的可綜合模塊，綜合化互連將不僅限于局域網(wǎng)，逐漸產(chǎn)生了電路板級的芯片間(off-chip)綜合化互連。

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

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

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

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

2 系統(tǒng)模型

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

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

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

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

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

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

在孔韻雯提出的綜合化互連架構(gòu)中，帶有網(wǎng)關(guān)的芯片間互連結(jié)構(gòu)如圖2 所示，V1 ～V6 為具有時間觸發(fā)片上網(wǎng)絡(luò)的芯片，其中V3 被選為網(wǎng)關(guān)芯片，當(dāng)該芯片間互連網(wǎng)絡(luò)中的任意芯片發(fā)出的TT 消息數(shù)據(jù)流需要跨越板級向局域網(wǎng)中傳輸時，都必須先通過物理鏈路發(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 個時間觸發(fā)網(wǎng)絡(luò)的靜態(tài)調(diào)度表來派發(fā)消息，在此過程中，已經(jīng)為某條消息預(yù)先分配好的時隙可以空閑，但不能傳輸其他消息。 當(dāng)1 條TT 消息到達(dá)網(wǎng)關(guān)后，需要在網(wǎng)關(guān)芯片中等待，這段時間即為等待時間。圖3 展示了消息2 在網(wǎng)關(guān)中等待的情況。 由于消息2 在到達(dá)網(wǎng)關(guān)時沒有趕上LAN 的前一個觸發(fā)時刻，因此需要等待下一個觸發(fā)時刻發(fā)送，在此期間，消息2 暫存在網(wǎng)關(guān)中，到達(dá)時刻和實際觸發(fā)時刻的差即為等待時間。 若消息1 和2 存在著由應(yīng)用決定的順序依賴關(guān)系時，網(wǎng)關(guān)對其進(jìn)行轉(zhuǎn)發(fā)的時候還需要滿足約束條件，等待時間也會產(chǎn)生變化。

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

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

3.1 NOPM 方法等待時間算法

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

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

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

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

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

3.2 OPM 方法等待時間算法

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

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

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

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

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

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

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

算法3：OPM 方法中TT 消息等待時間輸入：前3 個超周期的到達(dá)時間矩陣At 1，At 2，At 3，消息周期集合P，LAN 中消息發(fā)送起始時間偏移量集合T輸出：前2 個超周期內(nèi)到達(dá)網(wǎng)關(guān)的消息等待時間矩陣WT1，WT2，等待時間穩(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 中每一個非零值都表示A 中相同位置的到達(dá)時間對應(yīng)的觸發(fā)時間。

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

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

之后可將WT中與A中位置相同的數(shù)提取出來就可得到每條消息的每幀在通過網(wǎng)關(guān)時的等待時間。 并由式(2)得到每條消息的等待時間，網(wǎng)關(guān)對每個TT 幀按照計算得到的T進(jìn)行轉(zhuǎn)發(fā)，即可保證所有消息再通過網(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)的過度配置(Overprovisioning)。 因此，OPM 方法只在對順序要求十分嚴(yán)格的系統(tǒng)中適用。

3. 3 POPM 及等待時間算法

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

算法4：POPM 網(wǎng)關(guān)內(nèi)時間觸發(fā)消息等待時間計算方法輸入：包含具有順序依賴關(guān)系的TT 消息的前3個超周期的到達(dá)時間矩陣集合[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ā)送起始時間偏移量集合T1， T2，…，Tn 1，無依賴關(guān)系消息到達(dá)時間at1，at2，… atn 2，周期P1， P2，…， Pn 2，LAN 中消息發(fā)送起始時間偏移量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

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

4 案例分析

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

本文采用已有的芯片間互連網(wǎng)絡(luò)調(diào)度表和LAN 調(diào)度表進(jìn)行驗證，其中芯片間互連網(wǎng)絡(luò)調(diào)度表由汪晶晶等提出的方法求得，LAN 調(diào)度表由宋梓旭等提出的方法求得。 消息的首次到達(dá)網(wǎng)關(guān)時間和LAN 調(diào)度表中首次觸發(fā)時刻都可從調(diào)度表中直接讀取。 TT 消息由芯片間互連網(wǎng)絡(luò)中的芯片發(fā)出，經(jīng)由網(wǎng)關(guān)芯片傳入局域網(wǎng)，消息集合的具體參數(shù)如表1 所示，TT 消息的幀長從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)的時間，且到達(dá)時間滿足約束條件。 在此條件下，分別用OPM、NOPM和POPM 規(guī)劃網(wǎng)關(guān)內(nèi)消息，并就等待時間和順序關(guān)系兩方面來評價規(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ī)劃時，使用算法1 求得每條TT 消息的等待時間，如表2 所示。

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

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

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

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

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

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

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

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

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

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

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

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

4.2.4 結(jié)果分析

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

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

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

從整體來看，前10 個超周期內(nèi)到達(dá)網(wǎng)關(guān)的所有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 消息選擇使自身的等待時間最短的觸發(fā)時刻，從而使得具有順序依賴關(guān)系的TT 消息順序混亂，在本文案例中，如圖6 所示，M的每一TT幀都有唯一與其對應(yīng)的M的一個TT 幀，當(dāng)它們以特定順序傳遞時，消息的傳遞結(jié)果才能正確，但是在NOPM 中，每個周期內(nèi)消息M、M的TT 幀之間的順序關(guān)系被破壞，在此情況下調(diào)度的結(jié)果可能也會改變。

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

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

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

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

5 結(jié)論

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

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

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