SpaceWire-D的調(diào)度表生成方法

姜宏，楊孟飛，劉波，* ，劉鴻瑾，龔健

1.北京控制工程研究所，北京 100190

2.中國空間技術(shù)研究院，北京 100094

隨著國內(nèi)外航天技術(shù)的快速發(fā)展，航天電子系統(tǒng)的復(fù)雜度不斷增大，對數(shù)據(jù)總線、網(wǎng)絡(luò)的傳輸速率和實(shí)時性提出了更高的要求。傳統(tǒng)的1553B［1］、TTCAN 等航天總線，雖然具有較好的時間確定性，但是傳輸速率低;而 SpaceWire［2］、以太網(wǎng)、FC等網(wǎng)絡(luò)技術(shù)，雖然傳輸速率高，但是實(shí)時性較差。SpaceWire-D［3］是由英國鄧迪大學(xué)(Dundee University)的ESA空間技術(shù)中心(Space Technology Centre)設(shè)計(jì)的，是針對標(biāo)準(zhǔn)SpaceWire的時間確定性擴(kuò)展協(xié)議。SpaceWire-D使用標(biāo)準(zhǔn)SpaceWire的遠(yuǎn)程存儲器訪問協(xié)議(Remote Memory Access Protocol，RMAP)提供基本的通信機(jī)制。為了確保數(shù)據(jù)傳輸?shù)臅r間確定性，網(wǎng)絡(luò)帶寬被劃分為一系列的時間槽(time slots)，然后網(wǎng)絡(luò)通信的所有發(fā)起者(initiator)按照一定的調(diào)度表在規(guī)定的時間槽內(nèi)發(fā)送一組事務(wù)(transaction)。由于每個發(fā)起者都是獨(dú)占時間槽，不會與其他發(fā)起者產(chǎn)生競爭網(wǎng)絡(luò)資源的沖突，從而避免了資源競爭導(dǎo)致的不確定性傳輸時延，提高了實(shí)時性。

調(diào)度表生成的核心是調(diào)度［4-5］問題，目前主流的設(shè)計(jì)方法基于SMT(Satisfiability Modulo Theory，可滿足性模理論)求解器(SMT-Solver)。其中，TTTech公司的調(diào)度表生成技術(shù)［6］最為成熟。該公司采用內(nèi)嵌SRI(斯坦福國際研究所)開發(fā)的SMT求解器Yices［7］推出了商業(yè)化調(diào)度工具 TTE-Plan，可應(yīng)用于時間觸發(fā)以太網(wǎng)(TTEthernet)。德國慕尼黑大學(xué)的靜態(tài)調(diào)度方法基于Z3 SMT求解器［8］，用于時間觸發(fā)片上網(wǎng)絡(luò)(TTNoC)。澳大利亞IST的時間觸發(fā)調(diào)度方法［9］同樣基于Z3 SMT求解器，用于失效鏈路的交換網(wǎng)絡(luò)，但是流量模型較簡單，不能用于實(shí)際航天網(wǎng)絡(luò)系統(tǒng)。另外，還有一些不依賴于SMT求解器的方法［10-11］，但是這些方法針對的也是TTEthernet網(wǎng)絡(luò)，并且網(wǎng)絡(luò)和調(diào)度模型不夠明確。

綜上，SpaceWire-D是一種實(shí)時、可靠的航天網(wǎng)絡(luò)技術(shù)，但是現(xiàn)有文獻(xiàn)沒有針對高速SpaceWire-D調(diào)度表生成的有效方法，本文的研究工作根據(jù)高速SpaceWire-D網(wǎng)絡(luò)的特點(diǎn)將貪婪算法與SMT方法相結(jié)合，使得生成的調(diào)度表具有良好的分布均勻性且生成速度較快，彌補(bǔ)了現(xiàn)有方法的不足。

1 網(wǎng)絡(luò)模型

SpaceWire-D的底層基礎(chǔ)是 SpaceWire網(wǎng)絡(luò)。一個SpaceWire網(wǎng)絡(luò)系統(tǒng)通常由路由器、終端節(jié)點(diǎn)和鏈路構(gòu)成。高速SpaceWire網(wǎng)絡(luò)將標(biāo)準(zhǔn)SpaceWire的傳輸介質(zhì)變?yōu)楣饫w，并對路由器和節(jié)點(diǎn)的設(shè)計(jì)做了改進(jìn)，使網(wǎng)絡(luò)速率明顯高于傳統(tǒng) SpaceWire 的 200 Mbit/s［12］。本文采用高速SpaceWire網(wǎng)絡(luò)，最大數(shù)據(jù)傳輸率為1Gbit/s，并包含3個路由器和16個終端節(jié)點(diǎn)，如圖1所示。

圖1 高速SpaceWire網(wǎng)絡(luò)模型Fig.1 Network model of high-speed SpaceWire

圖1中的3個路由器用R1、R2和R3表示，16個終端節(jié)點(diǎn)用N1，N2，…，N16表示。節(jié)點(diǎn)和路由器之間通過全雙工鏈路連接，可同時進(jìn)行數(shù)據(jù)收發(fā)，鏈路由 L1，L1'，…，L18，L18'表示。SpaceWire路由器的各個端口通過Crossbar交換陣列進(jìn)行互聯(lián)。通常認(rèn)為Crossbar的內(nèi)部是無阻塞的，因此只要輸出端口不同就不會發(fā)生競爭沖突。

2 傳輸幀模型

在高速SpaceWire網(wǎng)絡(luò)系統(tǒng)中，由任意節(jié)點(diǎn)Vi(1≤i≤M，M為節(jié)點(diǎn)個數(shù))發(fā)起的到達(dá)任意節(jié)點(diǎn)Vj(1≤j≤M)的一個周期性傳輸幀F(xiàn)ij可被描述為一個四元組 M=( αij，βij，γij，δij)。其中，αij為傳輸?shù)闹芷?，βij為周期偏移值，γij為傳輸占用時間，δij為傳輸鏈路信息。

αij和βij用于描述幀的周期特性，都以時間槽T為單位。αij的取值通常為小周期的整數(shù)倍。βij的取值范圍是0～N－1，N為大周期包含的時間槽個數(shù)。小周期(基本周期)等于所有幀周期的最大公約數(shù)，大周期(矩陣周期)等于所有幀周期的最小公倍數(shù)［13］(如圖2所示)。

γij描述的是某個幀所占據(jù)的調(diào)度表的時間長度。該值有可能取得較大值，甚至?xí)^小周期，此時需要將長幀拆分成多個短幀。在圖2中，C幀的傳輸時間為6，大于小周期長度5，于是被拆分成C1、C2和C3。長幀的拆分使調(diào)度表的設(shè)計(jì)既具有較大的靈活性，同時也增加了難度，當(dāng)終端節(jié)點(diǎn)數(shù)量較多時很難由手工完成。

δij用于記錄從Vi到Vj經(jīng)過的所有鏈路組成的集合，例如:V1到V12經(jīng)過的鏈路集為{L1，L6，L12，L14'}。當(dāng)網(wǎng)絡(luò)系統(tǒng)中的兩個鏈路集的交為空集時，它們之間不存在公共鏈路，從而不會發(fā)生因競爭鏈路發(fā)送權(quán)而導(dǎo)致的沖突。反之，兩個鏈路集有公共鏈路，從而存在競爭沖突，此時稱這兩個鏈路集處于同一個競爭區(qū)域(Competition Area，CA)內(nèi)。

3 約束條件

由于SMT求解器在理論上已經(jīng)比較完善，并且在工程上也有了較好的應(yīng)用，因此本文基于SMT求解器開展研究工作。在調(diào)用SMT求解器前，需要先根據(jù)高速SpaceWire網(wǎng)絡(luò)的特點(diǎn)設(shè)定好關(guān)于自由變量βij的約束集。

3.1 調(diào)度周期約束

每個周期性傳輸幀F(xiàn)ij都有其傳輸周期αij。如果一個大周期包含多個Fij周期，即:(N/αij)=K，K＞1，則在調(diào)度表中會有多個Fij的周期偏移值，記為 βij1，βij2，…，βijK，表示Fij幀頭部開始傳輸時的時間槽。βij1，βij2，…，βijK應(yīng)符合如下的周期約束:

式(1)表明:Fij在調(diào)度表中應(yīng)按固定周期排列，相鄰兩個周期的偏移值之差應(yīng)恰好為αij。

3.2 順序約束

當(dāng)Fij為占用多個時間槽傳輸?shù)拈L幀時，要將Fij拆分為短幀(本文稱之為分片)處理，當(dāng)Fij只占用1個時間槽時則無需分片，因此下文按兩種情況討論順序約束。

3.2.1 不分片的情況

當(dāng)幀F(xiàn)ij在調(diào)度表中只出現(xiàn)一次時，顯然其起始位置應(yīng)不小于0，結(jié)束位置應(yīng)不大于N，即:

當(dāng)幀F(xiàn)ij在調(diào)度表中多次出現(xiàn)時，其多個周期偏移值滿足下式所示的約束條件:

3.2.2 分片的情況

(1)對分片先后順序的約束

Fij的各個分片具有固定的先后順序關(guān)系，若Fij在調(diào)度表中只出現(xiàn)1次，則可表示為如下的約束:

式中:(βij)s+1為幀F(xiàn)ij第s+1個分片在調(diào)度表的起始位置;(βij)s為幀F(xiàn)ij第s個分片在調(diào)度表的起始位置，1≤s＜S，S為Fij在一個周期內(nèi)的分片個數(shù);(γij)s為第s個分片占用的時間槽個數(shù)。

若幀F(xiàn)ij在調(diào)度表中多次出現(xiàn)，則應(yīng)滿足的約束條件為:

式中:(βrij)s+1為在調(diào)度表中，F(xiàn)ij第r次被調(diào)度時，第s+1個分片的起始位置;第r次被調(diào)度時，第s個分片的起始位置。

式(4)和(5)表明:Fij的兩個相鄰分片在調(diào)度表中的起始位置的距離不小于前一個分片占用的時間槽個數(shù)。

(2)對首分片和尾分片的約束

當(dāng)Fij在調(diào)度表中只出現(xiàn)1次時，該幀第一個分片(首分片)和最后一個分片(尾分片)的位置應(yīng)在如下約束規(guī)定的范圍內(nèi)。

當(dāng)Fij在一個大周期內(nèi)被調(diào)度K次時，該幀第一次被調(diào)度時的首分片和第K次被調(diào)度時的尾分片的位置應(yīng)符合下式規(guī)定。

式(6)和(7)表明:所有幀的所有分片的起始位置應(yīng)不小于0，且結(jié)束位置應(yīng)不大于N。

3．3 鏈路約束

Fij的鏈路信息δij有助于將整個網(wǎng)絡(luò)系統(tǒng)劃分為多個競爭區(qū)(CA)。當(dāng)根據(jù)鏈路信息發(fā)現(xiàn)多個幀處于相同的CA時，必須保證它們之間不會在同一時刻傳輸數(shù)據(jù)。根據(jù)這一原則，并結(jié)合Fij在一個大周期內(nèi)是否被分片，設(shè)定如下的鏈路約束。

(1)Fij不分片

當(dāng)幀F(xiàn)ij在調(diào)度表中只出現(xiàn)一次時，約束條件為:

式中:βuv為任意幀F(xiàn)uv在調(diào)度表中的偏移值;γuv為該幀占用時間槽的個數(shù)，這是Fuv被調(diào)度一次，且不分片的情況為任意幀F(xiàn)uv被調(diào)度多次時，第r次出現(xiàn)在調(diào)度表中的偏移值，γuv仍然是該幀的傳輸時間;為任意幀F(xiàn)uv被調(diào)度多次且分片，第s個分片第r次出現(xiàn)時所處的偏移位置，(γuv)s為第s個分片的傳輸時間。

當(dāng)任意幀F(xiàn)ij在調(diào)度表中多次出現(xiàn)時，約束條件為:

式(9)中的各變量含義同式(8)，只是為了區(qū)分，將βij和βuv的上標(biāo)分別寫成r1和r2。

(2)Fij被分片

當(dāng)幀F(xiàn)ij在調(diào)度表中只出現(xiàn)一次時，約束條件為:

當(dāng)幀F(xiàn)ij在調(diào)度表中多次出現(xiàn)時，約束條件如下:

式(10)和式(11)中各變量含義與式(8)和式(9)相同，上下標(biāo)的差異是為了變量的區(qū)分。

式(8)～式(11)表明:對于任意的兩個幀F(xiàn)ij和Fuv(δij≠δuv)，當(dāng)二者處于同一個 CA 中時，不論在調(diào)度表中出現(xiàn)幾次，也不論是否被分片，占用的時間槽都不能發(fā)生重疊，即調(diào)度區(qū)間的交集為空。

4 基于SMT的調(diào)度表生成方法

由上文可知，對任意幀進(jìn)行分片為調(diào)度表的生成帶來了較大的復(fù)雜性，而SMT求解器內(nèi)部并不能自主完成對長幀的分片，只能針對已分好片的各個幀及約束條件計(jì)算出可滿足性，當(dāng)可滿足時再給出每個幀或幀的分片在調(diào)度表中的偏移值，具體的分片方案需要由外部提供。

本文的調(diào)度表生成方法在處理分片問題時基于以下分片原則:同一個幀的各個分片應(yīng)均勻分布于調(diào)度表的大周期。上述原則使得網(wǎng)絡(luò)流量盡量均勻，傳輸過程更加平順，有利于降低數(shù)據(jù)傳輸過程中存儲區(qū)的數(shù)據(jù)存取壓力。為實(shí)現(xiàn)均勻分片，使生成的調(diào)度表在確保可調(diào)度的前提下的分布均勻性達(dá)到最優(yōu)，本文設(shè)計(jì)了基于貪婪(greedy)算法［14］的全局優(yōu)化方法。該算法的設(shè)計(jì)思想是:首先按分布最均勻的情況對各個幀進(jìn)行分片并設(shè)置約束，然后將約束條件作為參數(shù)輸入給SMT求解器進(jìn)行可滿足性檢查。若檢查的結(jié)果為可滿足，則SMT求解器輸出的模型即為所求最優(yōu)解，否則將分布均勻條件放松，重新分片并更新約束條件再輸送給SMT求解器。這一過程迭代執(zhí)行，直到得到最終的結(jié)果。

4.1 算法描述

具體實(shí)現(xiàn)算法如圖3所示，共分6個步驟:步驟1:預(yù)處理，根據(jù)鏈路信息劃分沖突域，計(jì)算小周期、大周期和時間槽長度，并確定各個幀的分片長度，然后轉(zhuǎn)入步驟2。

圖3 全局優(yōu)化算法Fig.3 Algorithm of global optimization

步驟2:按各個分片均勻分布的情況設(shè)置約束并調(diào)用SMT求解器，若計(jì)算結(jié)果為可滿足，則執(zhí)行步驟5，否則執(zhí)行步驟3。

步驟3:對于每個幀，從第1個小周期開始，依次移動1個、2個、…、δ(δ為某個幀的幀周期包含的小周期個數(shù))個分片到其他小周期，再設(shè)置約束并調(diào)用SMT求解器，檢查可滿足性，若可滿足則執(zhí)行步驟5，否則執(zhí)行步驟4。

步驟4:對于所有幀，當(dāng)幀周期的每個小周期都已嘗試過分片移動，但仍未找到可滿足的解，則執(zhí)行步驟6，若還有幀或幀的小周期未開展分片移動，則回到步驟3。

步驟5:返回的模型即為最優(yōu)解。

步驟6:未找到可滿足的解，當(dāng)前條件無法生成調(diào)度表。

4.2 算法說明

(1)SMT求解器的輸入和輸出

SMT求解器的輸入?yún)?shù)通常為一系列斷言式［15］組成的約束條件集合。根據(jù)這些約束條件，SMT求解器能夠做出可滿足性判定。如果可滿足，則輸出的模型即為使所有斷言式都成立的解。

對于調(diào)度表生成算法，如果輸出為可滿足(執(zhí)行到步驟5)，說明算法成功找到了一組關(guān)于所有幀和幀的分片在調(diào)度表中的偏移值;如果輸出為不可滿足(執(zhí)行到步驟6)，說明在同一個CA中的所有幀或幀的分片無法不重疊地出現(xiàn)在調(diào)度表中，即該CA中的幀的集合是不可調(diào)度的。

(2)設(shè)置時間槽大小

時間槽大小的一種較簡便計(jì)算方法是取所有幀傳輸時間的最大值(也被稱為光柵)［16］，但是這種設(shè)定方法不利于網(wǎng)絡(luò)流量的均勻分布。本文的方法是:

1)首先根據(jù)高速SpaceWire網(wǎng)絡(luò)的數(shù)據(jù)傳輸率，計(jì)算每個幀的傳輸時間并以微秒(μs)為單位向上取整，然后計(jì)算取整后的所有傳輸時間的最大公約數(shù)T1;

2)取T1與小周期長度的最大公約數(shù)，即為最終的時間槽大小T。

(3)分片準(zhǔn)則

本文根據(jù)幀的傳輸周期采取如下策略確定是否分片，及分片的長度:

1)若幀的調(diào)度周期等于小周期，則該幀不需要被分片;

2)不滿足1)的所有幀，分片長度都等于1個時間槽。

(4)劃分沖突域

根據(jù)鏈路信息劃分沖突域，比較各個幀的鏈路集合。如果兩個幀有相同的鏈路存在，則這兩個幀同處于一個CA，否則處于不同的CA。當(dāng)所有幀的鏈路信息都比較后，沖突域劃分完畢。

5 試驗(yàn)條件和結(jié)果

5．1 試驗(yàn)條件

本文采用斯坦福的開源SMT求解器Yices開展試驗(yàn)。試驗(yàn)的硬件平臺是聯(lián)想ThinkCentre PC機(jī)，處理器主頻2.66 GHz，內(nèi)存為2 Gbyte。軟件開發(fā)環(huán)境是Visual Studio 2010，采用C++語言實(shí)現(xiàn)算法。

試驗(yàn)條件根據(jù)高速SpaceWire網(wǎng)絡(luò)的1Gbit/s數(shù)據(jù)傳輸率和圖1所示的拓?fù)浣Y(jié)構(gòu)進(jìn)行了設(shè)置。

待調(diào)度的幀一共有16個，這些幀的信息如表1所示。

表1 各個幀的相關(guān)信息Table 1 Related information of all frames

續(xù)表1Table 1 Continued

5.2 試驗(yàn)結(jié)果

根據(jù)表1中各個幀的信息、圖1的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)以及1Gbit/s的數(shù)據(jù)傳輸率執(zhí)行本文算法，共試驗(yàn)了20次，每次的運(yùn)行時間見表2。

表2 算法的運(yùn)行時間Table 2 Running time of the algorithm

上述試驗(yàn)數(shù)據(jù)中，最大運(yùn)行時間為268 ms，最小運(yùn)行時間為 187 ms，平均運(yùn)行時間為201.65ms。

雖然多次運(yùn)行的時間有所差異，但是每次試驗(yàn)生成的調(diào)度表是一致的，具體見圖4。

圖4的結(jié)果共展示了4個沖突域的幀的調(diào)度情況。CA1包含幀A、B、C、D;CA2包含幀D、E、F、G;CA3 包含幀 H、I、J、K;CA4 包含幀 L、M、N、O、P。

在 CA1 中，C 幀被拆分為 Ca、Cb、Cc、Cd共 4個分片;D幀被拆分為 Da、Db、Dc共3個分片。CA1和CA2中都有D幀，這是因?yàn)镈幀與這兩個沖突域中的幀都存在鏈路競爭。在CA3和CA4中，I幀、K幀、N幀和P幀都被拆分為兩個分片。

圖4 調(diào)度表生成結(jié)果Fig.4 Generated schedule

觀察圖4可發(fā)現(xiàn)，全部16個幀和分片在調(diào)度表大周期的分布比較均勻，因此獲得了很好的效果。

6 結(jié)束語

針對高速SpaceWire-D提出了一種調(diào)度表生成方法。該方法基于SMT求解器并結(jié)合貪婪算法。貪婪算法是本文方法的主體，用于將幀的分片在各個小周期進(jìn)行調(diào)整，使各分片在調(diào)度表上盡量均勻分布。SMT求解器是本文方法的重要工具，在算法中設(shè)定了關(guān)于調(diào)度表的調(diào)度周期約束、順序約束和鏈路約束，并作為SMT求解器的輸入?yún)?shù)，然后調(diào)用求解器對輸入?yún)?shù)的可滿足性進(jìn)行判定，如果可滿足則返回的模型即為所求的調(diào)度表。此外，本文還提出了設(shè)置分片長度、確定時間槽大小以及劃分沖突域的策略，使整個方法可以完整實(shí)現(xiàn)。在試驗(yàn)部分，使用本文方法生成了一組幀的調(diào)度表，結(jié)果驗(yàn)證了該方法的有效性，適用于航天高速SpaceWire-D網(wǎng)絡(luò)。本文方法目前應(yīng)用范圍有限，后續(xù)需要針對更多應(yīng)用案例進(jìn)行驗(yàn)證，并且為應(yīng)對大規(guī)模的調(diào)度表生成問題，在未來的工作中還將改進(jìn)分片策略，以進(jìn)一步縮短算法的收斂時間。