面向多周期循環TTP總線消息操作設計方法

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

(1.北京航空航天大學 電子信息工程學院，北京 100191；2.北京衛星信息工程研究所天地一體化信息技術國家重點實驗室，北京 100086)

0 引 言

時間觸發通信協議，如TTP、TTCAN[1]、FlexRay等，適用于電子系統的綜合化實時控制應用。其中，TTP網絡具有精確的分布式時鐘同步能力，已被應用于波音787的環境控制、M-346教練機的全權限數字發動機控制等，其各節點實時通信任務的調度是設計中必須考慮的問題[2]。

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

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

借鑒FlexRay[5]的信號(signal)與幀(frame)的組織方式，針對TTP網絡的時隙特性進行修正，給出一種多周期消息輪詢操作(handling)架構，并提出相應的MHTT表設計方法。

在該方法中，不同于文獻[6]從不相容關系方面進行劃分，而是依據兩兩相容關系，引進最大團算法[7]求解的多周期任務的相容優化分組問題；同時在考慮嚴格周期性保證和可調度性必要條件的前提下，利用兩組相容性檢查和偏移量查找，解決了候選相容組內周期任務消息排布方法問題。

1 TTP網絡的MHTT操作建模

1.1 TTP網絡節點模型

SAE AS6003標準[8]中的TTP網絡由節點(node)和雙冗余總線構成，如圖1所示，每個節點分為應用層主機、MBI接口和TTP控制器，網絡中的各個節點構成分布式集群(cluster)[9]。

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

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

圖1 TTP網絡節點模型

1.2 周期性通信任務模型

如果保證消息轉運操作的嚴格周期性，則易于與下層時間觸發通信訪問相協調。對于嚴格周期調度任務[10]，Ti的執行時間區間Ii為

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

(1)

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

任務集Λ在單處理器上嚴格周期可調度的充要條件是

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

(2)

文獻[8]可以證明，任意兩個周期任務Ti，Tj在處理器上嚴格周期可調度的充要條件為

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

(3)

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

如果兩個通信任務的周期可調度，則稱之為“相容”；如果通信任務組中任意兩個任務都相容，則稱之為候選相容組。

相容性有利于組織多周期輪詢操作，但對于比較復雜的兩兩相容關系，需要結合MHTT表的操作模型進行合理的分組和排布。

1.3 多周期循環的MHTT表操作

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

圖2 MHTT表操作模型

根據面向多周期循環的MHTT表操作方法，MBI緩存中的各個位置與MG或MQ一一對應。處于相容組的多周期通信任務采用消息組輪詢派發到MBI；少量無法分配到相容組的通信任務通過消息隊列MQ排隊派發到MBI。

根據SAE AS6003標準，TTP節點發送時，除了時隙開始時的4-bits頭部，消息沒有任何協議封裝，僅通過MEDL表中定時進行區分。

2 多周期循環任務與分組方式

2.1 周期任務圖模型

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

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

圖3 消息組中的通信任務

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

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

(4)

2.2 周期任務圖的分組

采用合理的周期任務分組可以使盡可能多的消息滿足嚴格周期性調度，且使給定節點所需的MBI和時隙長度下限更短。依據文獻中的“最大團”(max-group)算法PTG進行合理的分組。

圖4 多周期任務分組

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

3 候選相容組內的消息排布

(5)

對于滿足式(5)條件的候選相容組，根據表1所示的偽代碼構建排布算法。按周期從小到大順序對通信任務排序，記為T1,…,TN； 且排布時需要兩個任務集合，它們分別對應排布算法結束后的消息組，不失一般性，分別記為MG1和MG2。

表1 通信任務的分組相容性

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

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

4 案例研究

通過仿真實驗設定10個周期任務，周期以TDMA周期為單位，包含從2開始的較小質數，以及以質數為因子的12以內的數值，如表2所示，周期任務消息長度參數在10-50中隨機選擇。

表2 典型算例實驗數據

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

圖5 實驗算例周期任務

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

圖6 實驗算例通信任務排布路徑

對路徑1和路徑3采用第3節所述編碼循環方式進行優化篩選，實驗結果見表3。

表3 實驗偏移量數據

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

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

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

圖7 算例實驗數據

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

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

圖8 Haar小波處理結果

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

5 結束語

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