孔韻雯，李峭, *，熊華鋼，程子敬

1.北京航空航天大學(xué) 電子信息工程學(xué)院，北京 100083 2.北京衛(wèi)星信息工程研究所，北京 100080

綜合化航空電子系統(tǒng)經(jīng)歷了分立式、聯(lián)合式、綜合式到高度綜合的發(fā)展過(guò)程[1-2]，目前，高度綜合的分布式綜合模塊化航空電子(Distributed Integrated Modular Avionics， DIMA)體系結(jié)構(gòu)，其特征在于利用分布式架構(gòu)將所有綜合化模塊分布在整個(gè)飛行器中[3]，通過(guò)時(shí)間確定網(wǎng)絡(luò)實(shí)現(xiàn)安全關(guān)鍵性消息的嚴(yán)格周期確定性。文獻(xiàn)[4]提到未來(lái)航電系統(tǒng)計(jì)算體系結(jié)構(gòu)向著智能化、多核處理、微內(nèi)核和片上系統(tǒng)(System on Chip, SoC)的方向發(fā)展。更進(jìn)一步，隨著可綜合模塊微小型化的發(fā)展，例如：美國(guó)國(guó)防高級(jí)研究計(jì)劃局(DARPA)的MTO辦公室推出新型片內(nèi)微結(jié)構(gòu)的研究項(xiàng)目[5]，歐洲e2V公司推出了幾百克重的航電多核處理機(jī)[6]，微小型智能片間互連系統(tǒng)有望成為未來(lái)航空航天電子系統(tǒng)分布式綜合對(duì)象。

迄今為止航電綜合化互連技術(shù)屬于局域網(wǎng)(LAN)或系統(tǒng)域網(wǎng)(SAN)范疇,尚未出現(xiàn)廣為認(rèn)可的跨越處理核內(nèi)部總線、外部局部總線、I/O總線、SAN和LAN等計(jì)算體系結(jié)構(gòu)[7]層次的互連技術(shù)。針對(duì)微小型智能片上系統(tǒng)亟待解決的片間互連問(wèn)題，串行外設(shè)接口(SPI)和Rapid-IO支持的最大速率雖然遠(yuǎn)高于I2C的5 Mbit/s[8-9],但是沒(méi)有提供固定規(guī)則的尋址方案和數(shù)據(jù)流量控制[10]，基于SPI總線和Rapid-IO的消息傳輸尋址都需要設(shè)計(jì)人員的特定規(guī)劃?？紤]到未來(lái)應(yīng)用遷移的方便性，本文采用開放性介質(zhì)無(wú)關(guān)接口實(shí)現(xiàn)芯片間互連，滿足跨體系結(jié)構(gòu)層次互連的功能一致性。

對(duì)于跨越微小型智能器件的綜合化互連系統(tǒng)，文獻(xiàn)[11]研究了混合關(guān)鍵性系統(tǒng)分布式實(shí)時(shí)架構(gòu)，通過(guò)時(shí)間觸發(fā)以太網(wǎng)(Time-Triggered Ethernet, TTE)實(shí)現(xiàn)了多個(gè)多核芯片互連的跨層次體系結(jié)構(gòu)，其側(cè)重于該架構(gòu)下的可重配置方法。文獻(xiàn)[12]研究了片上和片間跨層次體系結(jié)構(gòu)模型，并分別將基于靜態(tài)調(diào)度表和基于優(yōu)先級(jí)的兩種調(diào)度方法應(yīng)用于該模型，但前者會(huì)引入調(diào)度切換開銷，后者由于不同層次結(jié)構(gòu)中流量約束優(yōu)先級(jí)不同，可能會(huì)對(duì)可組合性產(chǎn)生影響。更有甚者，文獻(xiàn)[13-14]提出了時(shí)間觸發(fā)片上系統(tǒng)(Time-Triggered System on Chip, TTSoC)架構(gòu)，通過(guò)時(shí)間觸發(fā)片上網(wǎng)絡(luò)[15](Time-Triggered Network-on-Chip，TTNoC)實(shí)現(xiàn)片上多個(gè)異構(gòu)IP塊的互連，但與底層硬件聯(lián)系緊密。

得益于時(shí)間觸發(fā)網(wǎng)絡(luò)中TT流量調(diào)度方法的積累，可以為片間互連網(wǎng)絡(luò)拓?fù)渲蠺T流量的調(diào)度方法提供參考。如：文獻(xiàn)[16-17]采用可滿足模理論(Satisfiability Modulo Theories, SMT)求解器，通過(guò)網(wǎng)絡(luò)拓?fù)浜土髁颗渲眠M(jìn)行約束，生成滿足約束的TT網(wǎng)絡(luò)時(shí)間觸發(fā)調(diào)度表；文獻(xiàn)[18]則提出了利用最早期限(EDF)算法調(diào)度異步任務(wù)的增量化調(diào)度方法；文獻(xiàn)[19]綜合考慮了時(shí)間觸發(fā)控制器處理和通信的約束關(guān)系，但片間互連往往是多網(wǎng)段分布式交換結(jié)構(gòu)，無(wú)法直接應(yīng)用上述總線調(diào)度結(jié)果。對(duì)于更細(xì)粒度的片間TT流量調(diào)度，文獻(xiàn)[20-21]基于特征任務(wù)的嚴(yán)格周期性任務(wù)可調(diào)度分析方法可供借鑒。

另外，對(duì)于端系統(tǒng)主機(jī)組成的TTE網(wǎng)絡(luò)，雖然TT流量的單跳交換延遲為μs量級(jí)，但應(yīng)用層事件觸發(fā)和時(shí)間觸發(fā)機(jī)制配合的等待時(shí)間甚至達(dá)到流量周期的量級(jí)，TTTech公司的操作系統(tǒng)中間件[22]可以部分解決上述問(wèn)題；但對(duì)于片上系統(tǒng)組成的網(wǎng)絡(luò)，應(yīng)用的操作環(huán)境是輕量化的，很難在源、宿節(jié)點(diǎn)嵌入純軟件實(shí)現(xiàn)的中間件，且具有多級(jí)交換轉(zhuǎn)發(fā)，為了保證各物理鏈路上TT流量的嚴(yán)格實(shí)時(shí)性，只得將等待時(shí)間分散于各交換節(jié)點(diǎn)。

本文的貢獻(xiàn)在于建立基于開放性介質(zhì)無(wú)關(guān)接口的芯片間綜合化互連模型，并在現(xiàn)有嚴(yán)格周期性任務(wù)可調(diào)度分析方法[20-21]的基礎(chǔ)上，提出一種應(yīng)用于片間互連的TT通信調(diào)度方法。本方法采用負(fù)載均衡的選徑方法，以盡量減小等待時(shí)間為目標(biāo)確定流量的發(fā)送時(shí)間偏移量，并利用遺傳算法優(yōu)化發(fā)送端口的調(diào)度表相位，獲得具有全局意義的時(shí)間觸發(fā)調(diào)度表。

1 片間綜合化互連模型

1.1 片間互連的拓?fù)浣Y(jié)構(gòu)

在電路板范圍內(nèi)，芯片之間通過(guò)開放式的介質(zhì)無(wú)關(guān)接口建立物理鏈路,進(jìn)行全雙工通信。芯片的物理鏈路數(shù)量和布局根據(jù)數(shù)據(jù)傳輸?shù)男枨蟠_定，在一般情況下是不對(duì)稱的。取代獨(dú)立的中心交換機(jī)的交換結(jié)構(gòu)也通常不對(duì)稱，分別就近嵌入于芯片端口內(nèi)的可編程結(jié)構(gòu)中。選定某一芯片作為片間互連的網(wǎng)關(guān)，通過(guò)連接板外交換機(jī)節(jié)點(diǎn)進(jìn)行跨電路板消息的端到端傳輸。

將一個(gè)芯片間互連結(jié)構(gòu)記為G=(V,E)，V={vi}表示各個(gè)芯片，E={ei}表示芯片間的雙向連接路徑。芯片之間的通信是全雙工的，相鄰芯片間的物理連接可以根據(jù)不同的方向標(biāo)記為不同的通信鏈路，用L={li}表示板上通信鏈路的集合。若vi、vj∈V為相鄰節(jié)點(diǎn)，則(vi,vj)∈L表示vi到vj的通信鏈路；(vj,vi)∈L表示vj到vi的通信鏈路。

對(duì)于給定芯片vs、vd∈V間的端到端通信，從vs到vd傳輸路徑可以表示為

p=((vs,vi),…,(vj,vd))

式中：vs為源節(jié)點(diǎn)；vd為目的節(jié)點(diǎn)；其他芯片為中轉(zhuǎn)節(jié)點(diǎn)，角標(biāo)i和j為芯片編號(hào)。此外，規(guī)定流量傳輸路徑不會(huì)構(gòu)成回環(huán)。

圖1為局部芯片互連拓?fù)涫纠?，選擇v6作為板上網(wǎng)關(guān)節(jié)點(diǎn)。圖中所示為傳輸路徑：e1和e2分別為v1、v2和v1、v5之間的雙向連接通信路徑；v5為中轉(zhuǎn)節(jié)點(diǎn)，包含鏈路l1=(v5,v4)的發(fā)送端口。

圖1 局部芯片互連拓?fù)銯ig.1 Topology of local chip interconnection

1.2 時(shí)間觸發(fā)流量片間通信模型

假設(shè)片間通信的TT流量集合為F=(f1,f2,…,fn),每條流量都由芯片產(chǎn)生或是由網(wǎng)關(guān)轉(zhuǎn)發(fā)進(jìn)入板內(nèi)，用4組元fi=〈Pi,Ti,ci,pi〉(1≤i≤n)表示，Pi為流量的優(yōu)先級(jí),本文中規(guī)定跨板流量具有最高優(yōu)先級(jí)，周期具有次高優(yōu)先級(jí)，周期越小優(yōu)先級(jí)越高；Ti和ci分別為周期和執(zhí)行時(shí)間;pi為傳輸路徑，包含了q(q≥1)段通信鏈路，源節(jié)點(diǎn)為vs,i，目的節(jié)點(diǎn)為vd,i，經(jīng)過(guò)的跳數(shù)為h=q+1。流量傳輸路徑可以由設(shè)計(jì)根據(jù)需求靜態(tài)離線確定，對(duì)于沒(méi)有確定路徑的流量，將在2.1節(jié)中說(shuō)明根據(jù)負(fù)載均衡原則確定路徑的方法。

芯片之間需要進(jìn)行時(shí)鐘同步，專用同步線是可選的近距離時(shí)鐘同步的簡(jiǎn)易方法；然而，考慮到抗摧毀能力和未來(lái)應(yīng)用遷移所需的開放性，利用片上的可編程資源實(shí)現(xiàn)壓縮主控器(Compress Master，CM)、同步主控器(Synchronization Master，SM)和同步客戶端(Synchronization Client，SC)，通過(guò)協(xié)議控制幀(Protocol Control Frame, PCF)實(shí)現(xiàn)各個(gè)芯片間的時(shí)鐘同步，形成符合SAE AS6802標(biāo)準(zhǔn)[23]的同步過(guò)程，使之不僅在本地電路板上實(shí)現(xiàn)同步，而且可以與滿足該標(biāo)準(zhǔn)的時(shí)間觸發(fā)網(wǎng)絡(luò)實(shí)現(xiàn)同步。目前，對(duì)于100 Mbps碼速率的TTE，分布式同步精度為1 μs。此外，TT流量通信過(guò)程有以下規(guī)則：

1) 各個(gè)芯片端口發(fā)送的TT流量均滿足嚴(yán)格周期性，即同一個(gè)TT流量的兩個(gè)連續(xù)消息之間的時(shí)間間隔是固定的，且等于周期。

2) 本調(diào)度方法中規(guī)定選定作為網(wǎng)關(guān)的片上系統(tǒng)不作為消息傳輸路徑中的中轉(zhuǎn)節(jié)點(diǎn)中繼轉(zhuǎn)發(fā)消息。

3) 跨板流量具有最高的優(yōu)先級(jí)，在所有等待調(diào)度的TT流量中優(yōu)先被安排。

1.3 嚴(yán)格周期任務(wù)的可調(diào)度性

如果將時(shí)間觸發(fā)流量的傳輸服務(wù)作為任務(wù)，傳輸延遲作為任務(wù)的“執(zhí)行”時(shí)間，則也可借鑒多處理器任務(wù)集合可調(diào)度性的判定方法。在下面的討論中，令“任務(wù)”與TT流量的含義相同，而消息作為流量的實(shí)例，相當(dāng)于任務(wù)的“作業(yè)”。

此外，用函數(shù)LLC(S)表示一個(gè)非空集合S中連續(xù)整數(shù)的最長(zhǎng)長(zhǎng)度，函數(shù)SLC(S,l)表示一個(gè)非空集合S中長(zhǎng)度大于l的連續(xù)整數(shù)中的最小整數(shù)[20]，函數(shù)LC(S)表示一個(gè)非空集合S中各段連續(xù)整數(shù)的長(zhǎng)度。

1) 利用原任務(wù)的特征任務(wù)，采用取模運(yùn)算求出Tr上被任務(wù)τi占用的時(shí)間ITU(i,r)。

2) 求出特征任務(wù)在可調(diào)度時(shí)的所有空余時(shí)間。

3) 計(jì)算特征任務(wù)可用空余時(shí)間的最大長(zhǎng)度，判斷任務(wù)的可調(diào)度性。

定理1[20-21]任務(wù)τr=〈cr,Tr〉與集合T中所有任務(wù)是可調(diào)度的，當(dāng)且僅當(dāng)：

cr≤LLC(QT(r))

(1)

式中：LLC(QT(r))為空余時(shí)間QT(r)的最長(zhǎng)長(zhǎng)度。

2 TT流量調(diào)度方法

片間互連的TT流量調(diào)度方法在1.3節(jié)嚴(yán)格周期任務(wù)可調(diào)度性判定方法的基礎(chǔ)上，調(diào)度得到由分布于各端口的循環(huán)調(diào)度表組成的全局時(shí)間觸發(fā)調(diào)度表。該方法主要有以下3個(gè)步驟：

1) 利用基于特征任務(wù)的可調(diào)度性分析，計(jì)算端口負(fù)載率，根據(jù)負(fù)載均衡原則確定流量傳輸路徑。

2) 以等待時(shí)間局部最優(yōu)為目標(biāo)，依據(jù)優(yōu)先級(jí)排序以增量化方式初步確定流量發(fā)送時(shí)間偏移量，獲得各端口的循環(huán)調(diào)度表。

3) 利用遺傳算法調(diào)整各端口調(diào)度表相位，更新流量在各端口發(fā)送時(shí)間偏移量，得到全局優(yōu)化意義的時(shí)間觸發(fā)調(diào)度表。

2.1 流量傳輸路徑的選擇

對(duì)于TT流量跳數(shù)相同的可能端到端路徑，以負(fù)載均衡為目標(biāo)選擇流量傳輸路徑。為了提高路徑選擇算法的效率，采用廣度優(yōu)先，在不產(chǎn)生回環(huán)路徑的前提下，逐級(jí)搜索可能經(jīng)過(guò)的通信鏈路，判定TT流量在通信鏈路發(fā)送端口的可調(diào)度性。若存在無(wú)法調(diào)度的端口，則通過(guò)“剪枝”，剔除包含該端口所在傳輸路徑。通過(guò)累加計(jì)算可行端到端路徑的流量負(fù)載率，選擇負(fù)載率最小的路徑為流量的傳輸路徑。

2.1.1 TT流量可調(diào)度性判定算法

參考1.3節(jié)嚴(yán)格周期任務(wù)的可調(diào)度性判定多次和定理1[20-21]，算法1用于判定TT流量在通信鏈路li發(fā)送端口的可調(diào)度性，其計(jì)算的時(shí)間復(fù)雜度為O(NTmax)，Tmax為流量集合里的最大周期。

算法1 TT流量可調(diào)度性判定算法 輸入:TT流量集合Fli={fli1,fli2,…,flini}和待判定流量fr=。輸出:流量fr是否能被調(diào)度,若能調(diào)度則輸出集合QFlir()和OFlir()。1 br←0,QFlir()←0,Tr-1[],OFlir()←?;2forj=1tonido3 Ej←∪ekj k∈0,LCMTr,Tj()Tj-1[];4 ITUj,r()←x|x=ekj()modTr(),?ekj∈Ej{};5end6 QFlir()←QFli(r)ITUj,r();7ifcr≤LLCQFli(r)()then8 br←1;9 OFlir()←SLCQFli(r),cr();10end11 returnbr,QFli(r)andOFlir();

(2)

(3)

2.1.2 TT流量通信路徑選擇算法

采用廣度優(yōu)先算法，搜索得到待安排路徑流量fr=〈Pr,Tr,cr,pr〉可能的k條端到端傳輸路徑集合Rr=(p1,p2…,pk)，以及所有可能路徑中包含的q段物理鏈路li(1≤i≤q)。

算法2用于選擇TT流量的通信路徑，在算法1的基礎(chǔ)上先判定鏈路的可調(diào)度性，在剔除包含不可調(diào)度的鏈路的路徑后，選擇負(fù)載率最小的可行端到端路徑為流量的傳輸路徑，其計(jì)算的時(shí)間復(fù)雜度為O(N2)。算法2的偽代碼如下。

算法2 TT流量通信路徑選擇算法 輸入:TT流量集合Fli=fli1,fli2,…,flini{},待安排流量fr=和路徑集合Rr=p1,p2,…,pk{}。 輸出:流量fr選擇的通信路徑pr。1 pr←[],Uli←0,Upj←0,Upr=A,k1=k;2fori=1toqdo3 調(diào)用算法1判定fr在鏈路li的可調(diào)度性;4 ifbr=1then5 Uli←1-∑LlimTr;6 end7 else8 Uli←A;9 end10forj=1tok1do11 ifli∈pjthen12 ifUli=Athen13 deletepj;14 k1←k1-1;15 end16 else17 Upj←Upj+Uli;18 end19 end20 end21end22forj=1tok1do23 ifUpj

其中：A為預(yù)先根據(jù)可能負(fù)載率設(shè)定的較大常數(shù)；Uli為鏈路li發(fā)送端口的負(fù)載率，即

(4)

2.2 發(fā)送時(shí)間偏移量的確定

2.2.1 發(fā)送時(shí)間偏移量的初步確定

在片間的傳輸過(guò)程中，對(duì)流量傳輸?shù)亩说蕉搜舆t影響最大的是流量在中轉(zhuǎn)節(jié)點(diǎn)等待發(fā)送的緩存時(shí)間，記流量fr在傳輸路徑pr的等待時(shí)間為wtr(pr)，流量fr在中轉(zhuǎn)節(jié)點(diǎn)vi(li=(vi,vj))等待時(shí)間為wtr(li)，表示流量fr在到達(dá)vi后等待發(fā)送的時(shí)間。對(duì)于包含q段通信鏈路的路徑pr，wtr(pr)由wtr(li)累加得到，即

wtr(pr)=

wtr(l2)+wtr(l3)+…+wtr(lq)

(5)

對(duì)于靜態(tài)調(diào)度的流量，在發(fā)送節(jié)點(diǎn)端口的發(fā)送時(shí)間偏移量為

(6)

在中轉(zhuǎn)節(jié)點(diǎn)端口的發(fā)送時(shí)間偏移量為

(7)

圖3給出了例1根據(jù)算法1計(jì)算得到的結(jié)果，其中圖3(a)給出了vs,1發(fā)送端口可用的空余時(shí)間；圖3(b)為中轉(zhuǎn)節(jié)點(diǎn)v2發(fā)送端口可用的空余時(shí)間。

由此得到，fr中的消息在路徑pr的最小可行等待時(shí)間wtr(pr)=wtr(l2)=2。

圖2 消息傳輸路徑Fig.2 Message transfer path

圖3 消息等待時(shí)間計(jì)算過(guò)程Fig.3 Calculation process for message waiting time

2.2.2 等待時(shí)間的優(yōu)化

發(fā)送端口的循環(huán)調(diào)度表決定了該輸出物理鏈路上TT流量的嚴(yán)格周期性，而且各個(gè)循環(huán)調(diào)度表之間的相對(duì)相位影響了消息的等待時(shí)間。為了縮短最壞情況下的等待時(shí)間，采用遺傳算法[24-25]調(diào)整芯片各發(fā)送端口的調(diào)度表相位，得到各端口近似最優(yōu)的一組相位值。

給定相位值后，各流量在發(fā)送端口的偏移量依次循環(huán)移位更新，得到全局優(yōu)化意義的時(shí)間觸發(fā)調(diào)度表，此時(shí)最壞情況下的最大等待時(shí)間最短。

當(dāng)一代相位確定后，代入式(8)進(jìn)行各端口流量fr=〈Pr,Tr,cr,pr〉的發(fā)送時(shí)間偏移量的更新

(8)

偏移量更新后，采用式(8)計(jì)算等待時(shí)間，進(jìn)而得到其中的最大等待時(shí)間wtmax。從優(yōu)化目標(biāo)可知，wtmax越大，遺傳算法中基因保留在子代的可能性越小，因此設(shè)置適應(yīng)度函數(shù)為

(9)

式中：Cmax為預(yù)先根據(jù)可能結(jié)果設(shè)定的較大常數(shù)。

根據(jù)父代個(gè)體所得的適應(yīng)度值降序的排列，利用選擇算子和交叉算子生成子代，經(jīng)過(guò)多代遺傳后適應(yīng)度函數(shù)收斂，從而得到近似的最優(yōu)值。

3 案例研究

3.1 片間綜合化互連模型仿真

設(shè)基于芯片間消息實(shí)際傳輸速率為100 Mbit/s，以太網(wǎng)幀的幀長(zhǎng)范圍為64～1 518字節(jié)，則每一幀傳輸?shù)膱?zhí)行時(shí)間范圍為5.12～121.44 μs，TT流量的周期通常為1～128 ms?？紤]到仿真主要是為了驗(yàn)證該調(diào)度方法的有效性，需要在逼真度和計(jì)算復(fù)雜度之間取得權(quán)衡，因此將消息的執(zhí)行時(shí)間和周期以μs為單位進(jìn)行上取整為cr∈[6,122]，且cr∈N；在工程中，取整后增加的冗余量可作為消息的保護(hù)間隔。為了在仿真中使各流量的周期存在一定的公約數(shù)關(guān)系且具有多樣性，使Ti=2n×3m×1 000，其中0≤n≤7，0≤m≤2，且Ti∈[1 000,128 000]。

仿真規(guī)模對(duì)應(yīng)于3×3網(wǎng)格式的實(shí)驗(yàn)原型，該原型可配置為對(duì)稱互連結(jié)構(gòu)及非對(duì)稱互連結(jié)構(gòu)，分別如圖4(a)和圖4(b)所示。

為了進(jìn)行對(duì)比，其對(duì)照組利用SMT工具求解各端口調(diào)度表[16-18]，值得說(shuō)明的是，現(xiàn)有SMT工具僅面向端系統(tǒng)主機(jī)之間的互連，計(jì)算中將“端系統(tǒng)”等效為芯片的發(fā)送端口，“交換機(jī)”等效于芯片內(nèi)部的交換結(jié)構(gòu)，但規(guī)定連接于同一“交換機(jī)”的“端系統(tǒng)”間不產(chǎn)生外部通信流量。

類似于文獻(xiàn)[16]，SMT的單跳延遲下界設(shè)置為122 μs(最長(zhǎng)幀執(zhí)行時(shí)間)，不可判定情況下的停機(jī)時(shí)間為1.5 h，但為了允許中轉(zhuǎn)節(jié)點(diǎn)緩沖等待，將單跳延遲上界設(shè)為最長(zhǎng)幀的4倍(文獻(xiàn)[16]中的最大選項(xiàng))。

針對(duì)對(duì)稱與不對(duì)稱的互連結(jié)構(gòu)，調(diào)度規(guī)模如表1所示，分別采用SMT和本文提出的調(diào)度方法得到各組流量中的最大等待時(shí)間。其中，對(duì)稱和非對(duì)稱結(jié)構(gòu)中的最大等待時(shí)間分別記為wtmax,S和wtmax,A，以μs為單位，“--”表示SMT不可判定超時(shí)。

由仿真結(jié)果可以看出，在兩種結(jié)構(gòu)中，當(dāng)規(guī)模較小時(shí)，兩種方法調(diào)度得到的等待時(shí)間相近；而流量規(guī)模較大時(shí)，利用SMT進(jìn)行調(diào)度的傳輸?shù)却龝r(shí)間較小于本文調(diào)度方法得到的等待時(shí)間，但本文調(diào)度方法的可調(diào)度流量規(guī)模相較于SMT至少增加30%。

圖4 對(duì)稱和非對(duì)稱互連拓?fù)浣Y(jié)構(gòu)Fig.4 Topology structure of symmetrical and asymmetrical interconnection

表1 可調(diào)度流量規(guī)模Table 1 Scheduled message size

流量規(guī)模SMT本文方法wtmax,S/μswtmax,A/μswtmax,S/μswtmax,A/μs1001085133378489420018672039601224830016592437152238794001856--236059735002133--373396296002273--3638不可調(diào)度700----3800不可調(diào)度800----5294不可調(diào)度

此外，與SMT相比，本調(diào)度方法可以明確得到不可調(diào)度的結(jié)論，且導(dǎo)致不可調(diào)度的流量明確，便于根據(jù)實(shí)際調(diào)度情況及時(shí)調(diào)整。

對(duì)照組采用Yices SMT求解器，核心算法為優(yōu)化后的同余閉包算法[26],其時(shí)間復(fù)雜度為O(N3lgN)，然而，當(dāng)它具體應(yīng)用于TT調(diào)度問(wèn)題時(shí)，會(huì)出現(xiàn)非線性的離散數(shù)學(xué)約束，即使僅搜索可行解，也被認(rèn)為是NP問(wèn)題[18]。對(duì)于本文提出的調(diào)度方法，依次執(zhí)行算法1和算法2即可得到可行解，整體時(shí)間復(fù)雜度為O(N2)。在對(duì)稱與非對(duì)稱拓?fù)浣Y(jié)構(gòu)中，SMT與本文提出的調(diào)度方法對(duì)流量進(jìn)行調(diào)度規(guī)劃的運(yùn)行時(shí)間如圖5所示，本方法對(duì)流量進(jìn)行調(diào)度規(guī)劃的時(shí)間遠(yuǎn)小于SMT，并且在對(duì)稱與非對(duì)稱結(jié)構(gòu)中，流量規(guī)模的增加并不會(huì)導(dǎo)致調(diào)度規(guī)劃的時(shí)間明顯增長(zhǎng)。

圖5 運(yùn)行時(shí)間對(duì)比Fig.5 Comparison of execution time

3.2 等待時(shí)間仿真結(jié)果對(duì)比

利用20組600條TT流量，對(duì)比本文提出的逐跳計(jì)算流量的發(fā)送時(shí)間偏移量方法(方法1)和文獻(xiàn)[20]中既有的基于特征任務(wù)的調(diào)度方法(方法2)對(duì)等待時(shí)間的影響。

以流量傳輸?shù)却龝r(shí)間占周期的比例作為歸一化的傳輸延遲度量，圖6為分別為采用兩種方法調(diào)度2～4跳流量的平均傳輸延遲；其中10組仿真結(jié)果中，每組流量中的最大等待時(shí)間wtmax及對(duì)應(yīng)的歸一化傳輸延遲見表2。

在不經(jīng)過(guò)遺傳算法優(yōu)化前方法1得到的傳輸延遲不超過(guò)0.01，流量等待時(shí)間沒(méi)有隨著傳輸跳數(shù)的增加而明顯增加，而方法2得到的傳輸延遲至少為1.99，傳輸路徑每增加1跳，等待時(shí)間顯著增加。本方法與既有的基于特征任務(wù)的調(diào)度方法相比，傳輸延遲縮短到后者的2%以下，得到每條流量的局部最優(yōu)等待時(shí)間。

圖6 等待時(shí)間歸一化均值Fig.6 Normalized average of message waiting time

表2 最大等待時(shí)間Table 2 Maximum waiting time

流量組別方法1方法2wtmax/μswtmaxTi跳數(shù)wtmax/μswtmaxTi跳數(shù)126110.01942868732.994244490.03532868552.994328940.05422869902.994431420.03332559432.004527650.02231917052.004626690.02122551421.993736400.03732559182.004831970.03332872182.994929320.02032569112.0041030330.02432558442.004

3.3 遺傳算法優(yōu)化實(shí)驗(yàn)

針對(duì)3.1節(jié)非對(duì)稱結(jié)構(gòu)中調(diào)度的一組500條TT流量，利用方法1調(diào)度得到的最大等待時(shí)間為11 173 μs，利用方法2調(diào)度得到的最大等待時(shí)間為25 8133 μs。采用遺傳算法優(yōu)化兩種方法調(diào)度得到的最大等待時(shí)間，其優(yōu)化結(jié)果如圖7所示。

方法1得到的最大等待時(shí)間經(jīng)過(guò)遺傳算法優(yōu)化后為9 645 μs，優(yōu)化了13.7%，方法2得到的最大等待時(shí)間經(jīng)過(guò)1 672代的遺傳迭代優(yōu)化后，盡管該方法調(diào)度流量中的最大等待時(shí)間在優(yōu)化后減小了35.8%，仍然遠(yuǎn)大于方法1得到的最大等待時(shí)間，進(jìn)一步驗(yàn)證了本文方法能夠縮短流量傳輸?shù)却龝r(shí)間這一優(yōu)勢(shì)。

圖7 方法1和方法2最大等待時(shí)間優(yōu)化過(guò)程Fig.7 Optimization process of maximum waiting time for Methods 1 and 2

4 結(jié) 論

1) 本文建立了可以用于片間、片上系統(tǒng)和模塊聯(lián)合工作的片間綜合化互連結(jié)構(gòu)模型，提出了適用于該結(jié)構(gòu)的一種TT通信調(diào)度方法，其將縮短等待時(shí)間作為優(yōu)化目標(biāo)，規(guī)劃流量傳輸路徑，選擇并調(diào)整流量發(fā)送時(shí)間偏移量，獲得具有全局最優(yōu)意義的時(shí)間觸發(fā)調(diào)度表，并通過(guò)了案例仿真進(jìn)行驗(yàn)證。

2) 本方法能夠在有限時(shí)間內(nèi)得到是否可調(diào)度的判定結(jié)論；通過(guò)案例研究，對(duì)于可調(diào)度的情況，本方法的可調(diào)度流量規(guī)模比SMT方法至少增加了30%；即使不可調(diào)度，本方法能夠明確指出導(dǎo)致不可調(diào)度的流量，便于快速設(shè)計(jì)調(diào)整。

3) 案例研究結(jié)果表明，以流量傳輸?shù)却龝r(shí)間占周期的比例作為歸一化的傳輸延遲度量，本方法得到的傳輸延遲小于0.01，與既有的基于特征任務(wù)的調(diào)度方法相比，縮短到后者傳輸延遲的2%以下。

[1] 熊華鋼, 王中華. 先進(jìn)航空電子綜合技術(shù)[M]. 北京： 國(guó)防工業(yè)出版社, 2009： 2-13.

XIONG H G, WANG Z H. Advanced avionics integration techniques[M]. Beijing: National Defense Industry Press, 2009： 2-13 (in Chinese)

[2] 王國(guó)慶, 谷青范, 王淼, 等. 新一代綜合化航空電子系統(tǒng)構(gòu)架技術(shù)研究[J]. 航空學(xué)報(bào), 2014, 35(6): 1473-1486.

WANG G Q, GU Q F, WANG M, et al. Research on the architecture technology for new generation integrated avionics system[J]. Acta Aeronautica et Aastronautica Sinica, 2014, 35(6): 1473-1486 (in Chinese).

[3] WOLFIG R, JAKOVLJEVIC M. Distributed IMA and DO-297: Architectural, communication and certification attributes[C]∥Proceedings Digital Avionics Systems Conference. Piscataway, NJ: IEEE Press, 2008:1.E.4-1-1.E.4-10.

[4] 蒲小勃. 現(xiàn)代航空電子系統(tǒng)與綜合[M]. 北京： 航空工業(yè)出版社, 2013: 70-86.

PU X B. Modern avionics system and integration [M]. Beijing: Aviation Industry Press, 2013:70-86 (in Chinese).

[5] DARPA M T O. Another big shrink: Tiling chiplets into next-generation microsystems[EB/OL]. (2016-07-19)[2017-07-05].http:∥www.darpa.mil/news-events/2016-07-19.

[6] E2V. E2V and Adeneo partner to create the world’s smallest, multicore computer for aerospace applications[EB/OL]. (2016-07-18)[2017-07-05].https:∥www.e2v.com/news/e2v-and-adeneo-partner-to-create-the-worlds-smallest-multicore-computer-for-aerospace-applications/.

[7] 林闖, 賈子驍, 孟坤. 自適應(yīng)的未來(lái)網(wǎng)絡(luò)體系架構(gòu)[J]. 計(jì)算機(jī)學(xué)報(bào), 2012, 35(6): 1077-1093.

LIN C, JIA Z X, MENG K. Research on adaptive future internet architecture[J]. Chinese Journal of Computer,2012, 35(6): 1077-1093 (in Chinese).

[8] HIERGEIST S, HOLZAPFEL F. Fault-tolerant FCC Architecture for future UAV systems based on COTS SoC[C]∥Proceedings Architecture of Computing Systems. Berlin: Springer International Publishing, 2016: 1-5.

[9] SCHECKEL T. Serial RapidlO: Benefiting system interconnects[C]∥Proceedings SOC Conference. Piscataway,NJ: IEEE Press, 2005: 317-318.

[10] LEENS F. An introduction to I 2 C and SPI protocols[J]. IEEE Instrumentation & Measurement Magazine, 2009, 12(1): 8-13.

[11] DURRIEU G, FOHLER G, GALA G, et al. DREAMS about reconfiguration and adaptation in avionics[C]∥Proceedings Embedded Real Time Software and Systems. Toulouse: European Congress Press. 2016: 48-57.

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

[13] OBERMAISSER R, EL SALLOUM C, HUBER B, et al. The time-triggered system-on-a-chip architecture[C]∥Proceedings IEEE International Symposium on Industrial Electronics. Piscataway,NJ: IEEE Press, 2008:1941-1947.

[14] WASICEK A, EI-SALLOUM C, KOPETZ H. A system-on-a-chip platform for mixed-criticality applications[C]∥Proceedings IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing. Piscataway, NJ: IEEE Press, 2010: 210-216.

[15] SCHOEBERL M. A time-triggered network-on-chip[C]∥Proceedings International Conference on Field Programmable Logic and Applications. Piscataway,NJ: IEEE Press, 2007: 377-382.

[16] STEINER W. An evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks[C]∥Pro-ceedings Real-Time Systems Symposium. Piscataway, NJ: IEEE Press, 2011: 375-384.

[17] POZO PéREZ F M, RODRIGUEZ NAVAS G, HANSSON H, et al. Schedule synthesis for next generation time-triggered networks[C]∥IEEE 20th Conference on Emerging Technologies & Factory Automation (ETFA).Piscataway, NJ: IEEE Press, 2015: 1-8.

[18] CRACIUNAS S S, OLIVER R S. SMT-based task- and network-level static schedule generation for time-triggered networked systems[C]∥Proceedings International Conference on Real-Time Networks and Systems. Versailles: RTNS Press, 2014: 45-54.

[19] HU M, LUO J, WANG Y, et al. Scheduling periodic task graphs for safety-critical time-triggered avionic systems[J]. IEEE Transactions on Aerospace & Electronic Systems, 2015, 51(3): 2294-2304.

[20] CHEN J, DU C, XIE F, et al. Schedulability analysis of non-preemptive strictly periodic tasks in multi-core real-time systems[J]. Real-Time Systems, 2016, 52(3):239-271.

[21] 陳進(jìn)朝, 杜承烈. 單處理器平臺(tái)下的嚴(yán)格周期任務(wù)可調(diào)度性判定[J]. 計(jì)算機(jī)工程, 2016, 42(5): 288-291.

CHEN J C, DU C L. Schedulability test for strictly periodic tasks in uniprocessor systems[J]. Computer Engineering, 2016, 42(5): 288-291 (in Chinese).

[22] TTE-COM. TTE-COM A653 for VxWorks 653 2.4 [EB/OL]. (2016-10-25)[2017-07-05]. Vienna, Austria:TTTech Computertechnik AG, 2016.https:∥www.tttech.com/products/aerospace/development-test-vv/middleware/tte-com-a653-for-vxworks-653/.

[23] SAE. Time-triggered Ethernet: AS6802[S]. Warrendale, PA: SAE International, 2011.

[24] DING S, YIN X, XU H, et al. A hybrid GA-based scheduling method for static segment in FlexRay systems[C]∥Proceedings Control and Decision Conference. Piscataway, NJ: IEEE Press, 2010: 1548-1552.

[25] 代真， 何鋒， 張宇靜， 等．AFDX虛擬鏈路路徑實(shí)時(shí)尋優(yōu)算法[J]． 航空學(xué)報(bào)， 2015, 36(6): 1924-1932.

DAI Z, HE F, ZHANG Y J, et al. Real-time path optimization algorithm of AFDX virtual link[J]. Acta Aeronautica et Astronautica Sinica, 2015, 36(6):1924-1932 (in Chinese).

[26] DUTERTRE B. Yices 2.2[C]∥Proceedings International Conference on Computer Aided Verification. Berlin: Springer International Publishing, 2014: 737-744.