趙天鶴，熊華鋼，程子敬，李 峭

(1.北京航空航天大學,a.大型飛機高級人才班; b.電子信息工程學院，北京 100191；2.北京衛(wèi)星信息工程研究所國家重點實驗室，北京 100080)

0 引言

時間觸發(fā)協(xié)議(Time-Triggered Protocol,TTP)是分布式容錯實時系統(tǒng)電子模塊互連的實時通信協(xié)議[1]。TTP主要用于各種航空航天應用，例如波音787發(fā)電系統(tǒng)和環(huán)境控制、空中客車A380的機艙壓力系統(tǒng)以及Aermacchi M-346 的全權數(shù)字發(fā)動機控制(FADEC)系統(tǒng)等。

節(jié)能環(huán)保的“綠色航電”理念已經(jīng)開始滲入到航空電子系統(tǒng)設計的各個層面[2]，在實時應用條件下，有關通信的能量有效性研究關注于能量有效調(diào)度問題；文獻[3]基于具有并行度的調(diào)度提出靜態(tài)電源管理方法，配合兩個動態(tài)電源管理方法(貪婪法和空隙填補法)來節(jié)省盡可能多的能量；文獻[4]權衡了能量有效和可靠性，提出一種約束邏輯編程算法對比了不同動態(tài)錯誤下能量有效和可靠性的相互制約；文獻[5]提出了一種啟發(fā)式能量意識隨機任務調(diào)度算法(ESTS)，比過去的多種能量有效的調(diào)度方法節(jié)省更多的能量。

上述研究提出了信號電平和信號頻率影響數(shù)字電路系統(tǒng)能耗公式，并加以改進，但較少關注將能量有效目標直接用于指導航空電子綜合化系統(tǒng)的調(diào)度問題。具體到TTP總線網(wǎng)絡，既有的可調(diào)度性分析方法[6]包括靜態(tài)單一消息(SM)、靜態(tài)多消息(MM)、動態(tài)消息(DM)和動態(tài)分片(DP)消息分配模型?？紤]文獻[3-5]提出的能量有效策略，給出適合碼元速率調(diào)整的靜態(tài)分片(SP)分配模型，提出一種以能量有效為優(yōu)化目標的消息調(diào)度表生成方法。該方法可用于計算降頻節(jié)能的調(diào)度裕量，通過組合優(yōu)化得到每個節(jié)點包含的調(diào)度裕量的最優(yōu)分配方案，對周期消息調(diào)度表進行降頻節(jié)能優(yōu)化。

隨著航空電子綜合化設計向微小型化智能系統(tǒng)發(fā)展，時間觸發(fā)互連協(xié)議將應用于芯片之間(off-chip)甚至是芯片內(nèi)部(on-chip)[7-8]，在這些應用場景中將應用主頻更高的網(wǎng)絡協(xié)議處理單元，能量消耗對于碼元速率的變化更加敏感，本文方法有望對未來微小型智能航電系統(tǒng)的綜合設計提供參考。

1 模型

1.1 TTP節(jié)點調(diào)度模型

TTP網(wǎng)絡采用總線式結構將各個嵌入式節(jié)點聯(lián)接為分布式系統(tǒng)。TTP節(jié)點由主機、通信網(wǎng)絡接口(CNI)和TTP控制器組成，其中，在一個集群中，發(fā)送節(jié)點從CNI接口獲得帶有狀態(tài)信息的消息數(shù)據(jù)后，立即組幀并發(fā)送給其他需要接收的節(jié)點。每個節(jié)點的發(fā)送時間被保存在事先設定好的消息描述列表(Message Descriptor List,MEDL)中[1]。MEDL是TTP/C控制器的調(diào)度矩陣，用來描述節(jié)點數(shù)據(jù)收發(fā)消息等相關屬性，存儲在控制器RAM中，如圖1所示。

圖1 TTP總線構架圖Fig.1 TTP bus structure

在高安全性領域，一般采用雙冗余通道互連，通過相互冗余的通信通道連接的TTP節(jié)點形成一個集群，采用時分多路訪問(TDMA)方法組織總線通信。一個集群包含多個TDMA round，各個TDMA周期的時隙劃分是固定的。給定的節(jié)點可以按靜態(tài)配置占據(jù)各個周期中的某個時隙，或占據(jù)集群中某個周期的固定時隙(虛擬時隙)；占據(jù)時隙的節(jié)點具有在總線上發(fā)送消息的能力，其他節(jié)點可以偵聽接收到總線上的消息。

當沒有數(shù)據(jù)需要發(fā)送時，傳統(tǒng)的TTP網(wǎng)絡的物理層處于MARK狀態(tài)，對應于沒有被消息占據(jù)的時隙，發(fā)送方發(fā)送填充字符，以保持碼元同步；在更高的協(xié)議層次，這些填充對應于SAE AS6003標準規(guī)定的在沒有數(shù)據(jù)幀(N幀)傳輸時填充發(fā)送初始化幀(I幀)[9]，盡管此時并不需要初始化操作。

對于實用的航電互連設計，為了保證全生命周期的可擴展性，總線利用率往往留有可觀的余量?？梢岳脮r間資源余量降低傳輸真正數(shù)據(jù)負載的能量消耗，且保證其不超出其應占據(jù)的時隙區(qū)間，這就契合了綠色航電的設計理念，而實現(xiàn)的難點在于找到一種復雜度可以接受的能量有效消息組織的方法。

由上說明，由于TTP總線是靜態(tài)調(diào)度的，余量的利用不會影響可擴展性，當新型號的總線利用率提高時，重新設計調(diào)度表就可以釋放已占用的余量。

1.2 SP靜態(tài)分片模型

承載數(shù)據(jù)的N幀最長為240字節(jié)，包含不到4字節(jié)的協(xié)議開銷(4 bit頭部+CRC校驗24 bit)。消息包含一個或多個應用數(shù)據(jù)單元，嵌入幀中；顯然，當消息長度較長時，需要多條幀共同完成消息的發(fā)送，而數(shù)據(jù)單元的組織也為消息的分片提供了可能。TTP網(wǎng)絡完全通過預設的調(diào)度表控制幀的發(fā)送時刻，并在接收端識別幀的類型。

文獻[6]介紹了消息調(diào)度的4種組織方法，其中有靜態(tài)調(diào)度方法，即靜態(tài)單一消息(SM)、靜態(tài)多消息(MM)兩種消息分配模型；另外，還有動態(tài)調(diào)度方法，即動態(tài)消息(DM)和動態(tài)分片(DP)兩種消息分配模型。經(jīng)過對比，認為在精確的時鐘同步基準下，如果將MM模型進一步擴展，事先將MM分片，同樣通過靜態(tài)的調(diào)度表控制各個分片的發(fā)送時刻，不僅可以利用分片調(diào)度的靈活性進一步提高可調(diào)度性，而且不必像DP調(diào)度那樣付出動態(tài)決策的開銷。

因此，提出靜態(tài)分片模型(SP)，由于TTP幀的協(xié)議開銷比例小，在調(diào)度表設計時可暫不考慮；實際工程中可以為每個時隙保留一定比例的開銷余量，將僅含純數(shù)據(jù)的消息封裝為實際的幀，所以在本文中只考慮僅含純數(shù)據(jù)的消息。SP模型的設計思路是消息在被發(fā)送到傳輸線之前，即被分成多個小分片，分別對分片進行調(diào)度組織。因為節(jié)點的時隙長度在每個round中都是一樣的，并且時隙長度應當大于最長的消息長度，所以采用靜態(tài)分片模型可以大大提高總線的利用率，并且更方便后面降頻節(jié)能的實現(xiàn)。

1.3 能量有效消息調(diào)度

在保證通信性能的前提下動態(tài)調(diào)整數(shù)字電路的電平和頻率，可以達到節(jié)能的目的[10]；考慮到總線傳輸抗干擾的特殊性，本文方法僅采用降頻節(jié)能。

當有調(diào)度裕量存在時，傳統(tǒng)的總線傳輸會用無意義的碼元填充空閑時隙，這樣在無效數(shù)據(jù)傳輸時仍然耗能?？紤]到實時通信主要關注消息傳輸?shù)慕刂蛊谙?，只要給定的消息能夠在截止期限之前發(fā)送到總線上，即使拉長消息發(fā)送時間也可保證系統(tǒng)的性能，反之，提早完成傳輸沒有收益而且會增加緩存的負擔[10]。所以，只要能夠保證正好按時完成總線上各個消息的傳輸，就有望適當、合理地動態(tài)降低碼元發(fā)送頻率。

動態(tài)降低碼元發(fā)送頻率增加了發(fā)送、接收器芯片實現(xiàn)的復雜度，為了在能量有效和實現(xiàn)復雜度之間獲得權衡，本文方法規(guī)定(如圖2所示)：1)當存在空閑時段，僅以偶數(shù)倍降低碼元頻率；2)只有在節(jié)點切換的邊沿，頻率才可以進行改變。

TTP總線上的各個節(jié)點加載靜態(tài)的消息調(diào)度表，在精確時鐘定時下對于降頻節(jié)能方案具有一致的操作。

圖2 降頻調(diào)度圖示Fig.2 Illustration of down-frequency scheduling

2 能量有效TTP消息調(diào)度方法

2.1 設計方案

本文設計的方案流程如圖3所示。首先要設定節(jié)點數(shù)、各個節(jié)點的消息數(shù)以及消息周期和消息長度。在SP模型下，計算可用于降頻節(jié)能的調(diào)度裕量數(shù)。在先不考慮調(diào)度裕量時，生成周期性消息調(diào)度表，然后通過組合優(yōu)化得到調(diào)度裕量分配給各個節(jié)點的最佳分配方案，生成優(yōu)化后的能量有效消息調(diào)度表。

值得說明的是，設SP模型下可允許的最小分片時間長度Tmin由設計給定；不失一般性，令Tmin=1，并以其為單位，對round、消息周期、截止期限等參數(shù)的時間長度進行歸一化。

圖3 總體方案流程圖Fig.3 Flow chart of the overall scheme

2.2 調(diào)度裕量的計算方法

降低碼元的發(fā)送頻率，相當于拉長消息的長度，使之最接近它們的截止期限，就可以在保障調(diào)度性能的前提下降低功耗。設N個節(jié)點分時共享TTP總線的每個round，記為節(jié)點i(i=1，2，…，N)。設節(jié)點i的相對截止期限為Di，round的時間長度記為D*，集群中含有round的數(shù)目為R。設計要求D*≤min(Di)。

由節(jié)點i發(fā)送的消息由二元組〈Pi,m,Ci,m〉表示，其中，參數(shù)Pi,m和Ci,m分別表示節(jié)點i的第m種消息的周期和長度。

對于?m，令Di≤Pi,m，對Pi,m進行規(guī)整

(1)

對于R的設定應當保證所有節(jié)點的所有消息都可以執(zhí)行完，定義

(2)

在消息靜態(tài)分片模型中，設消息是可以被分片的。以相同長度的分片大小同時對消息和時隙進行靜態(tài)分片分配。分片長度T定義為

(3)

式中,n=?lbD*」，使得T∈[1,2)，使之盡可能接近Tmin。實際的分片長度T作為分配和利用調(diào)度裕量的單位，進而對消息長度規(guī)整為

(4)

如果不通過降頻利用調(diào)度裕量，節(jié)點i在每個

round中發(fā)送消息必需的分片數(shù)目為

(5)

可以得到round中可用來進行降頻節(jié)能操作的調(diào)度裕量數(shù)目為

(6)

2.3 周期性消息調(diào)度表生成

(7)

將集群周期內(nèi)的round標記為r=1,2,…,R，時隙內(nèi)的分片位置標記為g=1,2,…,Gi，則在節(jié)點i的時隙中任意分片的位置可用矩陣Sr×g表示。

節(jié)點消息分片調(diào)度安排算法如下。

andGi

Output:Sr×g,

(r=1,2,…,R;g=1,2,…,Gi)

fori=1 toNdo

fork=1 toKdo

num=0;

num=num+1;

end

else

break;

end

end

end

end

returnSr×g

算法中，通過find()函數(shù)進行檢查，找到一組可行的位置，容納周期性重復的分片，并使其第一個位置在可行條件下最靠近調(diào)度表的起始點。

節(jié)點消息分片調(diào)度安排如圖4所示。其中，roundx(x=1,2,…,R)代表第x個round。相同顏色形狀的方框是同一個消息的周期性調(diào)度安排。

圖4 節(jié)點消息分片調(diào)度安排示意圖Fig.4 Illustration of node message SP scheduling

2.4 能耗的計算

在SP模型下，由式(6)求得的調(diào)度裕量分片通過組合優(yōu)化分配給各個節(jié)點，設各節(jié)點獲得裕量分片個數(shù)分別為L1,…,Li,…,LN。當Li=0,1,…,L時，節(jié)點i耗能為Ei,Li。節(jié)點i在第x個round中消息分片數(shù)為li,x。

降低時序同步邏輯數(shù)字電路的電平和主頻，都可以降低其動態(tài)功耗。由于降低總線電壓在實現(xiàn)上有一定困難，所以本文采用降頻節(jié)能的方法。設節(jié)點i分配得到Li個分片在第x個round中降頻后的頻率為fi,Li,x，參照文獻[3]的式(4)，本文所討論的li,x和Li相當于原文獻中的平行度為1時每個調(diào)度元素的長度和分配給此調(diào)度元素的靜態(tài)裕量，未降頻的總線碼速率即是公式中的頻率fmax，可得

(8)

對li,x和Li以T為時間單位，并忽略常量fmax和轉換電容Cef，設ei,Li為簡化的Ei,Li，簡化的算式為

(9)

雖然式(9)失去了物理量綱的意義，但并不影響組合優(yōu)化問題的求解。下文中將ei,Li的單位統(tǒng)稱為“能量單位”，進而可以得出所有節(jié)點的總耗能量為

(10)

2.5 調(diào)度裕量組合優(yōu)化分配算法

(11)

得到最優(yōu)的調(diào)度裕量分片的分配方案。常規(guī)可以采用混合整數(shù)線性規(guī)劃(MILP)求解最優(yōu)分配，但考慮到TTP的調(diào)度表是離線生成的，可以采用復雜度較高但易于理解的方法，先枚舉計算各個節(jié)點的ei，Li,然后采用樹結構遞歸[11]的方法求解式(11)。這里的算法偽代碼如下所示。

Global variable：LandNand {L1，L2，…，LN} and Minenergy

treesearch (energysum,Li,i)

end

end

else

ifLi<=L-Lusethen

Compare and Update Minenergy andLi;

end

else

Li++;

treesearch(energysum,Li,i);

end

end

return{L1,L2,…,LN}。

3 案例研究

為了展示以能量有效為優(yōu)化目標的消息調(diào)度表生成方法，這里選取某個節(jié)點數(shù)N為4的案例作為典型算例；隨后再給出擴展節(jié)點數(shù)后能量有效TTP總線調(diào)度表優(yōu)化結果。

3.1 典型算例

設節(jié)點消息數(shù)上限為10條，在實驗中隨機生成4個節(jié)點的消息數(shù)以及每條消息的周期值，取D*=minDi=minPi,m，根據(jù)式(1)將消息周期以D*為單位進行規(guī)整，如表1所示。

表1 規(guī)整后的消息周期(單位D*)Table 1 Regularized message cycle (the unit is D*)

根據(jù)式(4)將消息長度以調(diào)度分片T為單位進行規(guī)整，如表2所示,然后計算出所有消息長度所需要的分片數(shù)量以及剩余的調(diào)度分片裕量。本案例中round數(shù)R為36，一個round的分片數(shù)為32，4個節(jié)點所需要的分片數(shù)量分別為2，5，3，3。剩余的調(diào)度裕量L有19條。

表2 規(guī)整后的消息長度(單位T)Table 2 Regularized message length (the unit is T)

根據(jù)2.3節(jié)中節(jié)點周期性消息分片調(diào)度安排算法將節(jié)點的所有消息分片分配到各個節(jié)點時隙中。如圖5所示的節(jié)點消息分片調(diào)度表，相同的顏色代表同一個消息類，白色表示沒有消息，灰色用來分隔不同節(jié)點，每個分片中消息的高度代表頻率，優(yōu)化前還未降頻節(jié)能，滿格表示最高頻率。

圖5 節(jié)點消息分片調(diào)度表Fig.5 SP scheduling of node message

通過枚舉法和樹結構遞歸法求得不同調(diào)度裕量分配方案的耗能情況,如圖6所示。

圖6 不同調(diào)度裕量分配方案的耗能分布圖Fig.6 Energy consumption distribution map of different scheduling slack allocation schemes

由圖6可以看出,當分配給4個節(jié)點的調(diào)度裕量{L1,L2,L3,L4}={2,7,5,5}時，可以通過降頻節(jié)能方法節(jié)省最多的能量。選擇此分配方案并進行降頻，得到能量有效優(yōu)化節(jié)點消息調(diào)度表，如圖7所示。

圖7 能量有效優(yōu)化節(jié)點消息調(diào)度表Fig.7 Energy-efficient optimal node message scheduling

通過式(10)、式(11)可以求得采用以能量有效為優(yōu)化目標的消息調(diào)度表生成方法前后的能耗分別為232.0能量單位和38.4能量單位。

3.2 擴展案例

將典型算例中的節(jié)點個數(shù)由4節(jié)點擴展到8節(jié)點，其余不變。實驗中得到調(diào)度裕量有5條，節(jié)點消息分片調(diào)度表和能量有效優(yōu)化節(jié)點消息調(diào)度表如圖8所示。

同樣可以求得采用以能量有效為優(yōu)化目標的消息調(diào)度表生成方法前后的能耗分別為367.9能量單位和181.1能量單位。

圖8 8節(jié)點案例結果圖Fig.8 The case result of 8 nodes

4 結論

本文結合“綠色航電”的理念提出一種以能量有效為優(yōu)化目標的消息調(diào)度表生成方法，提出了靜態(tài)分片分配方法，將調(diào)度裕量組合優(yōu)化以耗能最小的分配方案分配給各個節(jié)點，從而達到合理降頻節(jié)能的效果，并通過了仿真案例驗證。針對本文的應用對象TTP總線，該方法可以保證消息的可調(diào)度性。

微小型智能片上系統(tǒng)的片間甚至片內(nèi)的互連有望采用類似的時間觸發(fā)總線的實時通信方式[7]，降頻等數(shù)字電路節(jié)能方法對于集成電路效果更加明顯[8]，本文方法有望對未來微小型智能航電系統(tǒng)的綜合設計提供參考。

參考文獻

[1] 陳長勝,劉智武,李曉慶,等.時間觸發(fā)總線時鐘同步技術研究[J].電光與控制,2017，24(6):74-78.

[2] TIANRAN Z,XIONG H.Design of energy-efficient hierarchical scheduling for integrated modular avionics systems[J].Chinese Journal of Aeronautics,2012,25(1):109-114.

[3]MISHRA R,RASTOGI N,ZHU D,et al.Energy aware scheduling for distributed real-time systems[C]//International Symposium on Parallel and Distributed Processing,IEEE Computer Society,2003.doi:10.1109/IPDPS.2003.1213099.

[4]POP P,POULSEN K,HARBO R,et al.Scheduling and voltage scaling for energy/reliability trade-offs in fault-to-lerant time-triggered embedded systems[C]//IEEE/ACM International Conference on Hardware/Software Codesign and System Synthesis,IEEE,2007:233-238.

[5]LI K,TANG X,LI K.Energy-efficient stochastic task scheduling on heterogeneous computing systems[J].IEEE Transactions on Parallel & Distributed Systems,2014,25(11):2867-2876.

[6] POP P,ELES P,PENG Z.Bus access optimization for

distributed embedded systems based on schedulability analysis[C]//Design,Automation and Test in Europe Conference and Exhibition,IEEE,2000:567-575.

[7] OLIVER R S,CRACIUNAS S S.Hierarchical scheduling over off-and on-chip deterministic networks[J].ACM SIGBED Review,2016,13(4):14-19.

[8] SCHOEBERL M.A time-triggered network-on-chip[C]//International Conference on Field Programmable Logic and Applications,IEEE,2007:377-382.

[9] SAE Aerospace.SAE AS6003 TTP communication protocol [S].[S.l.]:SAE International,2009.

[10] ZHAI B,BLAAUW D,SYLVESTER D,et al.The limit of dynamic voltage scaling and insomniac dynamic voltage scaling[J].IEEE Transactions on Very Large Scale Integration Systems,2005,13(11):1239-1252.

[11] 唐青松.深度優(yōu)先算法在創(chuàng)建樹形結構中的應用研究[J].計算機技術與發(fā)展,2014(9):226-229.