面向多周期循環(huán)TTP總線消息操作設(shè)計(jì)方法

連天野，熊華鋼，程子敬，李 峭+

(1.北京航空航天大學(xué) 電子信息工程學(xué)院，北京 100191；2.北京衛(wèi)星信息工程研究所天地一體化信息技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，北京 100086)

0 引 言

時(shí)間觸發(fā)通信協(xié)議，如TTP、TTCAN[1]、FlexRay等，適用于電子系統(tǒng)的綜合化實(shí)時(shí)控制應(yīng)用。其中，TTP網(wǎng)絡(luò)具有精確的分布式時(shí)鐘同步能力，已被應(yīng)用于波音787的環(huán)境控制、M-346教練機(jī)的全權(quán)限數(shù)字發(fā)動(dòng)機(jī)控制等，其各節(jié)點(diǎn)實(shí)時(shí)通信任務(wù)的調(diào)度是設(shè)計(jì)中必須考慮的問題[2]。

通過設(shè)定集群循環(huán)(cluster cycle)、TDMA周期(TDMA round)、時(shí)隙(slot)等參數(shù)，TTP總線控制器根據(jù)MEDL(message descriptor list)表進(jìn)行時(shí)間觸發(fā)通信。在不同的調(diào)度策略[3]下有相應(yīng)的時(shí)隙占用方式，其中靜態(tài)多消息分配(MM)是最為常用，且被TTTech公司的TTP-Plan工具支持。

主機(jī)端應(yīng)用進(jìn)程根據(jù)的周期產(chǎn)生多種待發(fā)送的消息，需要依據(jù)消息操作時(shí)間表(message handling time table，MHTT)表將消息通過消息底層接口(message base interface，MBI)轉(zhuǎn)運(yùn)到TTP控制器。然而，SAE AS6003標(biāo)準(zhǔn)并未規(guī)定具有針對性的MHTT消息操作方法，也沒有明確的MHTT表設(shè)計(jì)生成方法；文獻(xiàn)[4]中雖然涉及了多種消息在時(shí)隙中的排布模型，但采用一條FIFO隊(duì)列與MBI相連，意味著輸出排隊(duì)可以破壞應(yīng)用層通信任務(wù)固有的周期性。

借鑒FlexRay[5]的信號(signal)與幀(frame)的組織方式，針對TTP網(wǎng)絡(luò)的時(shí)隙特性進(jìn)行修正，給出一種多周期消息輪詢操作(handling)架構(gòu)，并提出相應(yīng)的MHTT表設(shè)計(jì)方法。

在該方法中，不同于文獻(xiàn)[6]從不相容關(guān)系方面進(jìn)行劃分，而是依據(jù)兩兩相容關(guān)系，引進(jìn)最大團(tuán)算法[7]求解的多周期任務(wù)的相容優(yōu)化分組問題；同時(shí)在考慮嚴(yán)格周期性保證和可調(diào)度性必要條件的前提下，利用兩組相容性檢查和偏移量查找，解決了候選相容組內(nèi)周期任務(wù)消息排布方法問題。

1 TTP網(wǎng)絡(luò)的MHTT操作建模

1.1 TTP網(wǎng)絡(luò)節(jié)點(diǎn)模型

SAE AS6003標(biāo)準(zhǔn)[8]中的TTP網(wǎng)絡(luò)由節(jié)點(diǎn)(node)和雙冗余總線構(gòu)成，如圖1所示，每個(gè)節(jié)點(diǎn)分為應(yīng)用層主機(jī)、MBI接口和TTP控制器，網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)構(gòu)成分布式集群(cluster)[9]。

TTP集群進(jìn)行時(shí)間觸發(fā)通信，即：采用采時(shí)分多址復(fù)用(time division multiple access，TDMA)方式依次訪問總線。離線設(shè)定TDMA周期(round)及其時(shí)隙(slot)劃分，根據(jù)MEDL表，每個(gè)節(jié)點(diǎn)只有在給定的時(shí)隙內(nèi)才能執(zhí)行總線發(fā)送操作。

如圖1所示，在應(yīng)用層，MHTT作用于等待隊(duì)列和MBI接口之間，其中，通信任務(wù)具有周期性，消息作為通信任務(wù)的實(shí)例被等待隊(duì)列緩存，而等待隊(duì)列的組織方式直接決定了任務(wù)實(shí)例向下層的轉(zhuǎn)運(yùn)方式。

圖1 TTP網(wǎng)絡(luò)節(jié)點(diǎn)模型

1.2 周期性通信任務(wù)模型

如果保證消息轉(zhuǎn)運(yùn)操作的嚴(yán)格周期性，則易于與下層時(shí)間觸發(fā)通信訪問相協(xié)調(diào)。對于嚴(yán)格周期調(diào)度任務(wù)[10]，Ti的執(zhí)行時(shí)間區(qū)間Ii為

[φi+kpi,φi+kpi+ei](k∈Z)

(1)

式中：φi,pi,ei分別表示相位(第一個(gè)作業(yè)的釋放時(shí)間)、周期(作業(yè)的固定釋放時(shí)間間隔)和每個(gè)作業(yè)的執(zhí)行時(shí)間。

任務(wù)集Λ在單處理器上嚴(yán)格周期可調(diào)度的充要條件是

Ii∩Ij=?(i≠j且i,j∈1,2…N)

(2)

文獻(xiàn)[8]可以證明，任意兩個(gè)周期任務(wù)Ti，Tj在處理器上嚴(yán)格周期可調(diào)度的充要條件為

e(oi)≤(s(oi)-s(oj))modg≤g-e(oj)

(3)

其中：g=gcd(p(oi),p(oj))，s(oi)，s(oj) 是兩個(gè)周期任務(wù)開始時(shí)間，e(oi),e(oj) 為處理兩個(gè)周期任務(wù)消息所用時(shí)間。

如果兩個(gè)通信任務(wù)的周期可調(diào)度，則稱之為“相容”；如果通信任務(wù)組中任意兩個(gè)任務(wù)都相容，則稱之為候選相容組。

相容性有利于組織多周期輪詢操作，但對于比較復(fù)雜的兩兩相容關(guān)系，需要結(jié)合MHTT表的操作模型進(jìn)行合理的分組和排布。

1.3 多周期循環(huán)的MHTT表操作

在每個(gè)TDMA周期，節(jié)點(diǎn)只有在所屬的時(shí)隙獲得發(fā)送權(quán)，因此MHTT表操作的功能是：在時(shí)隙到達(dá)的時(shí)候，將本輪次中就緒的消息派發(fā)到主機(jī)接口；在運(yùn)行時(shí)間組織等待隊(duì)列，對通信任務(wù)產(chǎn)生的消息排序。本文提出一種面向多周期循環(huán)的MHTT表操作方法，如圖2所示，即：MHTT表中含有多個(gè)消息組MGi，i=1,2…，分別對應(yīng)于時(shí)隙中待加載的消息位置，采用輪詢(round-robin)操作加載；對于具有周期相容性的通信任務(wù)，采用循環(huán)式的等待隊(duì)列，保證各個(gè)通信任務(wù)的嚴(yán)格周期性。另外，設(shè)置一個(gè)局部先入先出(local FIFO)型的消息隊(duì)列MQ，用以兼顧難以納入相容組的通信任務(wù)。

圖2 MHTT表操作模型

根據(jù)面向多周期循環(huán)的MHTT表操作方法，MBI緩存中的各個(gè)位置與MG或MQ一一對應(yīng)。處于相容組的多周期通信任務(wù)采用消息組輪詢派發(fā)到MBI；少量無法分配到相容組的通信任務(wù)通過消息隊(duì)列MQ排隊(duì)派發(fā)到MBI。

根據(jù)SAE AS6003標(biāo)準(zhǔn)，TTP節(jié)點(diǎn)發(fā)送時(shí)，除了時(shí)隙開始時(shí)的4-bits頭部，消息沒有任何協(xié)議封裝，僅通過MEDL表中定時(shí)進(jìn)行區(qū)分。

2 多周期循環(huán)任務(wù)與分組方式

2.1 周期任務(wù)圖模型

采用周期任務(wù)圖(periodical task graph，PTG)反映通信任務(wù)之間的相容關(guān)系，周期任務(wù)圖是對主機(jī)通信任務(wù)之間相關(guān)性的建模，其模型G=(V,E) 由任務(wù)集合V、無向邊集合E構(gòu)成。周期任務(wù)抽象為PTG中的頂點(diǎn)。

頂點(diǎn)之間是否存在邊取決于兩頂點(diǎn)對應(yīng)周期任務(wù)的相容性。各條消息的長度不同，發(fā)送的執(zhí)行時(shí)間e不同；然而，分組僅需考慮以TDMA周期為單位的通信任務(wù)實(shí)例之間的間隔，如圖3所示。圖中每行均代表一定循環(huán)次序下準(zhǔn)備輸入MBI的消息，下文中將這樣的消息排布的位置稱為消息組的“行”。

圖3 消息組中的通信任務(wù)

所以，令所有通信任務(wù)的周期均以TDMA周期為單位，且令式(3)中e(oi)和e(oj)縮展為單位1，即驗(yàn)證是否滿足式(4)，如果滿足，則頂點(diǎn)間存在無向邊，反之邊不存在

1≤(s(oi)-s(oj))modg≤g-1

(4)

2.2 周期任務(wù)圖的分組

采用合理的周期任務(wù)分組可以使盡可能多的消息滿足嚴(yán)格周期性調(diào)度，且使給定節(jié)點(diǎn)所需的MBI和時(shí)隙長度下限更短。依據(jù)文獻(xiàn)中的“最大團(tuán)”(max-group)算法PTG進(jìn)行合理的分組。

圖4 多周期任務(wù)分組

對于候選相容組內(nèi)的任意任務(wù)，如果與其它任務(wù)均兩兩相容，則稱任務(wù)之間完全相容。分組后候選相容組內(nèi)的通信任務(wù)并不一定完全相容，需要在消息排布過程中進(jìn)行進(jìn)一步的檢驗(yàn)和組合優(yōu)化。

3 候選相容組內(nèi)的消息排布

(5)

對于滿足式(5)條件的候選相容組，根據(jù)表1所示的偽代碼構(gòu)建排布算法。按周期從小到大順序?qū)νㄐ湃蝿?wù)排序，記為T1,…,TN； 且排布時(shí)需要兩個(gè)任務(wù)集合，它們分別對應(yīng)排布算法結(jié)束后的消息組，不失一般性，分別記為MG1和MG2。

表1 通信任務(wù)的分組相容性

該算法降低了兩兩相容判斷的規(guī)模，MG1中的任務(wù)可保證完全相容；給定MG1條件下再對MG2中的任務(wù)根據(jù)式(4)兩兩檢查；排除未通過檢查的情況，MG1和MG2組內(nèi)完全相容即成為一種可選排布方式。

在可選排布方式中，MG2中消息采用數(shù)字編碼循環(huán)方式進(jìn)行優(yōu)化分析；消息占位設(shè)為1，空占位設(shè)為0，以包含所有消息占位的最短數(shù)字序列作為數(shù)字循環(huán)組，對循環(huán)編碼組進(jìn)行平移排布。平移后的消息通過靜態(tài)多消息分配(MM)方式與MG1中消息進(jìn)行調(diào)度，利用偏移量查找確定最終優(yōu)化解。下文將結(jié)合案例進(jìn)行說明。

4 案例研究

通過仿真實(shí)驗(yàn)設(shè)定10個(gè)周期任務(wù)，周期以TDMA周期為單位，包含從2開始的較小質(zhì)數(shù)，以及以質(zhì)數(shù)為因子的12以內(nèi)的數(shù)值，如表2所示，周期任務(wù)消息長度參數(shù)在10-50中隨機(jī)選擇。

表2 典型算例實(shí)驗(yàn)數(shù)據(jù)

依據(jù)2.2節(jié)所述的步驟得到周期任務(wù)如圖5所示。利用最大團(tuán)回溯法得到候選相容組V=(2,4,6,8,10,12)。

圖5 實(shí)驗(yàn)算例周期任務(wù)

在MG1中周期任務(wù)完全相容的條件下，每一條路徑代表一種MG2中任務(wù)相容關(guān)系，如圖6所示。經(jīng)過算法的進(jìn)一步檢查，其中路徑1和路徑3為可選排布方式。

圖6 實(shí)驗(yàn)算例通信任務(wù)排布路徑

對路徑1和路徑3采用第3節(jié)所述編碼循環(huán)方式進(jìn)行優(yōu)化篩選，實(shí)驗(yàn)結(jié)果見表3。

表3 實(shí)驗(yàn)偏移量數(shù)據(jù)

其中循環(huán)方式1編碼為：111000；方式2編碼為：011100；方式3編碼為001110；方式4編碼為000111；方式5編碼為0000111；方式6編碼為00000111。

各個(gè)消息組偏移量值之和決定了時(shí)隙的長度，較短的偏移量可以適用于較短的TDMA周期長度，而且意味著緩存的容量較少，因此優(yōu)先選擇具有最短偏移量的MHTT表排布方案。

優(yōu)化的結(jié)果可能出現(xiàn)多個(gè)排布方案，它們的偏移量都為最短。如圖7所示，序號4,8,12的排布方案各有不同，但均為最小偏移量。此時(shí)，如果選用其中的任一個(gè)，在總體上優(yōu)化效果都是可以接受的。然而，在MHTT離線設(shè)計(jì)中，可以利用更精細(xì)地評價(jià)手段選取最優(yōu)的結(jié)果。

圖7 算例實(shí)驗(yàn)數(shù)據(jù)

注意到如果排布方案的波峰、波谷起伏不規(guī)則，則對以后的擴(kuò)展(即：在不改變現(xiàn)有方案的條件下增量化添加通信任務(wù))造成困難。這種情況以信號處理的觀點(diǎn)，對應(yīng)著更豐富的高頻分量。用離散傅氏變換的方法可以對高頻分量進(jìn)行觀察，但在數(shù)字頻率π附近存在混疊。理想的方法是采用小波變換對高頻分量部分進(jìn)行比較。

設(shè)排布方案的離散數(shù)據(jù)為x，則一級離散小波變換得到尺度函數(shù)的展開系數(shù)cA1[k]和小波函數(shù)的展開系數(shù)cD1[k]，其中后者代表信號的細(xì)節(jié)(即：高頻)部分。如圖8所示，Haar小波對圖7中偏移量數(shù)據(jù)進(jìn)行變換。經(jīng)過比對，序號12對應(yīng)較小的小波展開系數(shù)絕對值。

圖8 Haar小波處理結(jié)果

最佳排布方案中相容組最大偏移量與非相同組Local FIFO最大偏移量總和為186 μs。不考慮次序的多周期消息排布方式，偏移量總和為308 μs。本方法偏移量降低40%，從而使給定節(jié)點(diǎn)所需的MBI和時(shí)隙長度下限更短。

5 結(jié)束語

本文提出了適用于輪詢調(diào)度MHTT架構(gòu)的消息操作方法，該方法分為周期消息候選相容性分組和組內(nèi)優(yōu)化排布兩個(gè)步驟；①考慮了兩兩相容性構(gòu)成的任務(wù)圖模型并采用了最大團(tuán)分組方法得到候選相容分組；②分別利用兩組相容性檢查和偏移量查找對組內(nèi)周期通信任務(wù)進(jìn)行組內(nèi)排布。案例研究表明，綜合利用該方法，與不考慮次序優(yōu)化的多周期消息操作相比，不僅完全保證相容周期任務(wù)的可調(diào)度性，而且使給定節(jié)點(diǎn)所需的MBI和時(shí)隙長度下限更短。