徐 嘉,周 晴,杜家昊,王一華
(1.中國科學院國家空間科學中心 復雜航天系統(tǒng)電子信息技術重點實驗室,北京 101499;2.中國科學院大學 計算機與控制學院,北京 101408)
隨著航天事業(yè)的迅速發(fā)展,復雜的需求提升了航天嵌入式軟件(aerospace embedded software,AES)的規(guī)模[1],其開發(fā)成本和維護難度也越來越高,在需求階段更易于降低開發(fā)成本及風險[2]。AES與外部接口數據交互復雜[3],兩者之間的聯(lián)系以及AES內部節(jié)點通訊關系均可用數據流來簡化表示。傳統(tǒng)的數據流圖(data flow diagram,DFD)能描述軟件節(jié)點之間的數據交互關系[4],但無法描述AES中具有時序特性的數據流?;趥鹘y(tǒng)數據流圖提出的同步數據流圖(synchronous data flow graph,SDFG)定義了組件間通信的周期時序特性的概念[5],通常是用于評估DSP(digital signal processing)應用程序[6],不適用于AES時序需求建模。為滿足AES的頻度需求,本文考慮在DFD中融入時序特征及事件驅動等元素。MARTE[7]是嵌入式軟件領域中對時間等非功能屬性定義詳盡的一個UML(unified modeling language)[8]擴展文件,在建模過程中通常將MARTE與UML相結合來描述需求中的時序模式[9,10],也有將MARTE、SysML(systems modeling language)[11]與pCCSL(p clock constraint specification language)相融合來描述實時嵌入式軟件的硬件和軟件的需求建模過程[12,13],上述融合的模型大都將狀態(tài)圖或塊圖與時序特性相結合,無法在需求階段分析并改善AES中的數據流時序偏離問題[14]。
針對DFD中不具備時序特性的問題,本文提出了一個基于MARTE的數據流時序模型,彌補了傳統(tǒng)模型無法對AES中具有時序屬性的數據流建模的問題;為檢測并優(yōu)化需求中時序定義不準確的問題,提出了處理點緩存計算算法、時序偏離概率檢測算法和時序序列分析算法。
DFD是一種結構化分析方法,它用圖形的形式來描述數據驅動的系統(tǒng)中數據流動和處理的過程,包括數據源點、數據流、處理點和數據存儲四大組件[15]。數據源點是與系統(tǒng)交互數據的單元;數據流是描述節(jié)點間數據傳輸的單元;處理點是在系統(tǒng)中對傳遞來的數據進行加工的單元;數據存儲是系統(tǒng)中數據停留或者將其保存的單元。數據流圖是需求分析階段對于結構化開發(fā)描述的一種功能模型。
MARTE是一個用于實時嵌入式系統(tǒng)建模和分析的UML概要文件,根據建模和分析實時和嵌入式系統(tǒng)(real time/embedded system)所需的UML擴展來定義概念,定義了基于模型的實時和嵌入式系統(tǒng)描述的基礎。MARTE包括基礎包、設計模型包、分析模型包和附加包,提供了關鍵資源,用于說明實時嵌入式軟件的非功能性需求,例如,時間方面和約束條件等[16]。
MARTE中的時間模型描述實時嵌入式系統(tǒng)中的時間以及時間相關概念的機制,包含邏輯時間(logical time)和物理時間(chronometric time)兩個部分,以描述實時和嵌入式系統(tǒng)中諸如延遲、時間段和時鐘的概念。根據系統(tǒng)設計的精確度要求,行為時序性有3種不同程度的表示方式:因果/瞬時(causal/temporal)、時鐘/同步(clocked/ synchronou s)、物理/實時(physiceal/real time)。
1.3.1 DFT-MARTE模型時序定義
本文將數據流與MARTE中的4種到達模式相結合,提出了DFT-MARTE模型。其中到達模式包括突發(fā)模式、偶發(fā)模式、不規(guī)則模式和周期模式,詳細參數信息見表1。突發(fā)模式屬于非周期性模式,包括最小到達間隔、最大到達間隔、最小數據間隔、最大數據間隔和突發(fā)量的參數,是一種在某個時間段內突發(fā)一定數據量的時序模式,可模擬物理/實時中非周期數據的情況;偶發(fā)模式屬于非周期模式,包括最小到達間隔、最大到達間隔及抖動的參數,是一種在某個時間段內產生一個數據的時序模式,可模擬因果/瞬時的情況;不規(guī)則模式屬于非周期模式,是一個完全確定的到達模式,包括階段和時間間隔的參數,是在確定的時間間隔點產生數據流的時序模式,可模擬時鐘/同步的情況;周期模式包括周期、抖動、相位、數據量的參數,是一種周期性產生數據流的時序模式,可模擬物理/實時中周期數據的情況。
表1 到達模式
1.3.2 DFT-MARTE模型時序結構
為描述AES中數據流的時序特性,本文擴展了數據流圖的元模型。數據流圖包括數據源點(data source point)、數據流(data flow)、處理點(processing point)和數據存儲(data storage)這4個組件,其元模型如圖1所示。數據流圖是一種重要的結構設計方法,可以清晰描述系統(tǒng)整體的數據交互關系。但在描述AES的數據交互過程中,由于其中大多數據包含時序信息,簡單的數據交互圖已然無法描述AES中數據的特點,并且不利于需求中時序屬性的相關檢查,故提出一種基于MARTE的數據流時序模型,即DFT-MARTE模型。
圖1 傳統(tǒng)數據流圖的元模型
DFT-MARTE模型的元模型是基于MARTE中的到達模式重新定義數據流圖,在傳統(tǒng)數據流圖的元模型基礎上添加了時序元素(time element)、緩存窗口(cache window)和隨機數據發(fā)射器(random data transmitter)模塊,其元模型如圖2所示。其中時序元素依據MARTE中的到達模式和數據流圖特點改寫并添加部分定義;緩存窗口是為了保證當處理速率與輸入流總體流速不匹配時,能根據預設閾值進行調節(jié):當緩存窗口中的數據大于最大閾值時,暫停所有輸入流,保證兩次握手期間所有的數據均可在緩存窗口內存儲,即不溢出;為保證模型的完整性,考慮到嵌入式軟件中存在隨機事件觸發(fā)輸入數據流的場景,故而在本模型中加入隨機數據發(fā)射器模塊,該模塊可定義隨機事件。該模塊會按照定義的時序特征隨機發(fā)射數據流,保證模型正常運行,利于后續(xù)分析時序問題。
圖2 DFT-MARTE模型的元模型
DFT-MARTE模型中的緩存窗口模塊是由優(yōu)先隊列構成,數據模塊包括數據流基本信息和數據優(yōu)先級。緩存窗口模塊為處理點模塊的關聯(lián)模塊,其中優(yōu)先隊列是用來處理帶有優(yōu)先級的數據,即優(yōu)先級數據。數據模塊會對數據流的優(yōu)先級進行定義。
通常在航天嵌入式軟件需求中,會根據實時性要求不同數據包選擇不同優(yōu)先級。針對數據流可以設定不同的優(yōu)先級,在分析過程中優(yōu)先級不能改變。因此,本文按照通用需求對數據優(yōu)先級進行設計。
針對航天嵌入式軟件需求,設計如表2所示的4種優(yōu)先級。圖中優(yōu)先級隨著序號增大而降低,如:高精度時間廣播數據的優(yōu)先級最高,能夠打斷其它優(yōu)先級較低的數據處理過程。緩存窗口模塊中按照數據優(yōu)先級設計了4個優(yōu)先隊列,與4種數據優(yōu)先級一一對應。當數據到達處理點時,將其放入對應的優(yōu)先隊列中。在處理數據時,優(yōu)先彈出高優(yōu)先級對應的隊列中的數據。
表2 數據優(yōu)先級設計
DFT-MARTE模型可用圖形化的形式,清晰準確地描述AES需求中有時序特性的數據流之間的關系。DFT-MARTE模型融合了DFD和MARTE,不僅解決了DFD無法展現(xiàn)數據時序性的問題,而且覆蓋了行為時序中的因果/瞬時的情況,可模擬事件驅動的數據流,有利于進行后續(xù)的時序相關檢查。DFT-MARTE模型與其它相關模型的比較見表3。
表3 相關模型對比
本節(jié)介紹基于DFT-MARTE模型提出的3個算法,其一是針對處理節(jié)點存在數據溢出導致時序檢測無法正常執(zhí)行的問題[17],提出了一種處理點緩存計算算法,該算法動態(tài)改變處理點緩存容量來輔助后續(xù)算法的正常執(zhí)行。其二是為引導用戶改進需求中的時序屬性,提出一種時序偏離概率檢測算法可計算輸出流針對定義時序的偏移概率,在需求階段可檢測出時序問題。其三是針對時序偏離概率檢測算法無法直觀地幫助需求人員改進需求的問題,提出一種基于梯度下降算法[18]的時序序列分析算法,最終可給出建議的周期模式參數。
處理點緩存計算算法是在處理具有時序特性的處理點時,根據處理點對應輸入流的時序特性和設定的最大、最小閾值來推算所需緩存窗口容量。本算法是輔助時序檢測與分析算法,使其正常執(zhí)行。算法1為處理點緩存計算算法的代碼。
算法1:處理點緩存計算算法
輸入:Inputflows輸入流數組,n數組容量,maxThres-hold最大閾值
minThreshold最小閾值,dealSpeed處理速率
輸出:capacity緩存窗口容量
描述:用于計算處理點緩存容量
(1)functioncacheWindowCapacity(Inputflows, n, thres-hold)
(2) capacity, capacity1, capacity2←0 //初始化緩存容量
(3) minlength←Inputflows[0].length
(4)fori=0→n-1do//遍歷所有輸入流數組
(5) //按式(1)先進行累加
(6) capacity1←capacity1+Inputflows[i].length
*getMaxDataFlowSpeed(Inputflows[i])
(7) //求出最短數據流長度, 為計算式(2) 作準備
(8) minlength←MIN(minlength, Inputflows[i].length)
(9)endfor
(10) //完成式(1), 得到按照最大閾值計算所需的緩存容量
(11) capacity1←capacity1/(1-maxThreshold)
(12) //完成式(2), 得到按照最小閾值計算所需的緩存容量
(13) capacity2←2* minlength*dealSpeed / minThreshold
(14) //按照式(3),取上述兩個變量最大值作為結果值
(15) capacity←MAX(capacity1, capacity2)
(16)returncapacity;
(17)endfunction
輸入: Inputflow輸入流
輸出: speed該輸入流的最大流速
描述: 用于計算輸入流的最大流速
(1)functiongetMaxDataFlowSpeed(Inputflows)
(2) speed←0 //初始化速率
(3) //如果輸入流時序為突發(fā)模式
(4)ifInputflow.patternType is burstthen
(5) //獲取當前突發(fā)模式下數據流時序參數信息
(6) pattern←getBurstPattern(Inputflow.patter-nId)
(7) //取最小到達間隔的反比為最大速率
(8) speed←1/pattern.minInterarrival
(9)endif
(10) //如果輸入流當前時序特性為偶發(fā)模式
(11)ifInputflow.patternType is sporadicthen
(12) pattern←getSporadicPattern(Inputflow.patter-nId)
(13) speed←1/pattern.minInterarrival
(14)endif
(15) //如果輸入流當前時序特性為不規(guī)則模式
(16)ifInputflow.patternType is irregularthen
(17) pattern←getIrregularPattern(Inputflow.patter-nId)
(18) //不規(guī)則模式的最小到達間隔需要遍歷時間間隔
(19) interarrival←Inputflow.interarrivals[1]-Inputflow.interarrivals[0]
(20)fori=2→Inputflow.interarrivals.length-1 do
(21) interarrival←MIN(speed,Inputflow.interarrivals[i]-Inputflow.interarrivals[i-1])
(22)endfor
(23) speed←1/ interarrival
(24)endif
(25) //如果輸入流當前時序特性為周期模式
(26)ifInputflow.patternType is periodic then
(27) pattern←getPeriodicPattern(Inputflow.patter-nId)
(28) speed←1/(pattern.period-pattern.jitter)
(29)endif
(30)returnspeed;
(31)endfunction
算法1的核心思想是當處理點緩存中的數據量與總窗口容量之比達到最大閾值時,暫停所有輸入流,需要保證剩余緩存空間仍可存儲暫停過程中到達的最大數據量;當緩存窗口內數據量與總窗口容量之比低至最小閾值時,處理點需要重啟輸入流,需要保證緩存中剩余數據可滿足重啟和數據傳輸過程中處理點的處理速率。具體過程如圖3所示。
圖3 處理點緩存計算
處理點緩存容量需要滿足最大、最小閾值兩種情況下的約束條件,因此,得出以下3個公式。其中,式(1)是計算在已知最大閾值時所需的緩存容量,其中inputflowk.length表示數據流傳輸時間,maxSpeed表示數據流傳輸的最大速率,maxThreshold為設定的最大閾值
(1)
式(2)是計算在已知最小閾值時所需的緩存容量,其中dealSpeed是處理點的處理速率,minThreshold為最小閾值
(2)
式(3)為處理點的緩存容量需要同時大于等于式(1)、式(2)的結果,因此,最終計算結果在兩者之間取最大值
(3)
由于只有外部接口向處理點的輸入流具有確定的時序特性,其余輸入流的時序特性是動態(tài)變化的。因此,在時序偏離檢測過程中,處理點的緩存計算是按照固定周期進行,處理點緩存空間也隨之動態(tài)變化。
由于AES需求中與外部實體交互的數據流具有時序特性,故本算法通過利用多線程并發(fā)模擬輸入流的時序特性,模擬得到輸出流的時序特性,并將計算結果與期望時序特性進行對比,得出輸出數據流的時序偏移概率。由于AES需求中存在優(yōu)先級搶占現(xiàn)象,本算法按照表2的優(yōu)先級設計,給每個處理點緩存增添了4個優(yōu)先隊列來處理優(yōu)先級數據。
若將DFT-MARTE模型簡化如圖4所示。節(jié)點1、2為抽象的數據源節(jié)點,節(jié)點3為處理點,節(jié)點4為外部存儲節(jié)點。在DFT-MARTE模型中,每個節(jié)點均具有時序序列α, 時序序列為一個有固定大小的滑動窗口,記錄數據到達時間點的序列,數據源節(jié)點和外部存儲節(jié)點具有時序特點γ, 時序特點為表1中介紹的4種到達模式,數據流均有相位δ, 相位表示數據在數據流上傳輸消耗的時間。
圖4 DFT-MARTE模型簡化
時序偏離概率檢測算法在圖4中是計算節(jié)點4的模擬得到的時序序列α4與其時序特點γ4的匹配程度。具體流程為:節(jié)點1、2按照γ1、γ2模擬時序序列產生α1、α2, 即:α1、α2分別服從γ1、γ2;α3為α1、α2、δi、δii的疊加;α4為α3、δiii的疊加;最終計算α4與其時序特點γ4的匹配程度。由于此種疊加不是數學意義上的加法,是兩種時序序列均到達時產生的新的時序序列,本算法采用多線程并發(fā)模擬DFT-MARTE模型中的動態(tài)時序關系。本算法的組成部分如圖5所示。
圖5 時序偏離概率檢測算法結構
其中,多線程包括主線程、數據源線程、數據流線程和處理點線程。主線程負責創(chuàng)建線程、建立管道、時鐘管理和線程管理。
創(chuàng)建線程是將模型中外部實體、數據流、處理點和隨機事件觸發(fā)器模塊分別進行線程創(chuàng)建,其中具有輸出流的外部實體和隨機事件觸發(fā)器模塊需要創(chuàng)建數據源線程,其余模塊與各自線程一一對應;建立管道是使線程間可以通信,數據源線程至少有一個輸出管道,數據流線程僅有一個輸入和輸出管道,處理點線程至少有一個輸入管道和一個輸出管道;時鐘管理是管理全局時間,更新全局時間必須保證線程間的同步,可利用循環(huán)屏障,使除主線程外所有線程在單位時間內執(zhí)行完各自任務后相互等待,當所有線程均到達某個屏障點時,主線程方可遞增全局時間并使其它線程進行后續(xù)操作;線程管理是主線程監(jiān)控全局結果集,若全局結果集覆蓋所有連接外部實體的輸出流,則改變全局終止變量以終止其它線程。
數據源線程是根據每個輸出流的時序特性將數據寫入該輸出流對應的管道中,其運行流程如圖6所示。其中,在每個單位時間內,無論是否滿足其時序特性,至少需要向輸出管道內寫入結束數據,以表示線程在當前時間對某個數據流完成相關時序判斷。本算法中向輸出管道寫入數據均以5個字節(jié)為單位。
圖6 數據源線程泳道
處理點線程的具體運行流程如圖7所示。處理點線程在收到全局終止信號前,在每個單位時間內,執(zhí)行以下3個任務:
圖7 處理點線程泳道
(1)將處理點的所有輸入管道放入隊列,依次彈出隊首的管道。若管道內無數據,則將其放入隊列尾端;有數據則以5個字節(jié)為單位循環(huán)讀取管道中的數據,并按照數據優(yōu)先級將其放入對應的優(yōu)先隊列中;
(2)按照優(yōu)先隊列次序和處理速率依次彈出數據,找到彈出數據關聯(lián)的后置數據流集合,循環(huán)遍歷后置數據流集合,將數據寫入對應輸出管道內。
(3)抵達屏障,等待其它線程完成任務。
數據流線程的具體運行流程如圖8所示。數據流線程在收到全局終止信號前,在每個單位時間內,執(zhí)行以下3個任務:
圖8 數據流線程泳道
(1)循環(huán)讀取輸入管道內數據,直至讀到結束數據時,停止讀取。
(2)首先判斷線程中讀到的數據是否滿足數據流的前置約束,若不滿足,則向輸出管道內寫入結束數據,然后進行任務(3);否則需判斷該數據流的目標節(jié)點是否為處理點。若是,則向輸出管道內寫入數據流id和結束數據;否則按照預期時序特性計算時序偏離概率,當偏離概率連續(xù)5次波動小于閾值,則將其寫入全局結果集。
(3)抵達屏障,等待其它線程完成任務。
當所有線程均抵達屏障時,主線程更新全局時鐘,并判斷當前是否滿足線程終止條件,即全局結果集中覆蓋所有連接外部實體的輸出流,若滿足,則調整全局終止變量為true;否則進入下一個單位時間,讓其余線程繼續(xù)循環(huán)。
由于系統(tǒng)面向外部實體的數據流的時序特性多為周期性,本算法最終給出周期模式的建議參數。本算法基于梯度下降算法將模型數據流中緩存區(qū)域的數據到達時序序列作為訓練數據,對其進行擬合,在使所有訓練數據滿足周期模式下的同時,使抖動盡可能地縮小,最終給出建議的周期和抖動參數。
本文將時序序列中的到達的次序和時間分別作為訓練數據中的x和y值 (x≥0且y≥0), 訓練數據約束如圖9所示。為保證所有的訓練數據均落在圖中點狀區(qū)域內,可得到約束條件如式(4)所示
圖9 訓練數據約束
(4)
為滿足式(4),可推出式(5)
(y1-y)(y-y2)≥0?(Tx+b-y)(y-Tx+b)≥0?
[b-(y-Tx)][b+(y-Tx)]≥0?b2≥(y-Tx)2
(5)
當抖動很大時,滿足約束條件的周期就會在一個范圍內,則得到的周期具有不確定性。為使最終建議的周期值T更精確,需要得到最小的抖動值b。 如式(5)所示,可通過優(yōu)化 (y-Tx)2從而優(yōu)化抖動值b, 因此,設計損失函數如式(6)所示
(6)
根據式(5)可知,抖動值b僅存在一個極值點。因此,基于梯度下降算法思想,將學習率設置為0.01,利用式(7)不斷更新周期值T, 從而找到抖動值b的極值點
(7)
當損失函數收斂后,得到周期值T, 并按照式(8)計算出最小值b, 最終將得到的周期值T和抖動值b作為參考建議提供給需求人員
(8)
為優(yōu)化航天嵌入式軟件需求,本文基于DFT-MARTE模型和時序偏離概率檢測算法開發(fā)出一款DFT-MARTE模型構建及檢測工具(TimingFlow),TimingFlow界面包括功能區(qū)、模型元素區(qū)、畫布區(qū)、數據特性區(qū)和工具區(qū),工具界面如圖10所示。
圖10 TimingFlow界面
TimingFlow可構建的DFT-MARTE模型,利于需求人員描述需求中時序特性數據的交互關系。
處理點屬性的處理速率為默認值時,即該處理點可以處理所有到達的數據,設定的最大閾值和最小閾值是為了計算處理點緩存,以保證偏離概率檢測的正常進行;數據流屬性中定義了相關時序特性和數據優(yōu)先級信息;隨機事件發(fā)射器屬性關聯(lián)了隨機事件與數據流,TimingFlow對DFT-MARTE模型中模塊屬性具體定義如圖11所示。
圖11 模塊特性
為驗證本模型可以滿足航天領域嵌入式軟件需求,以某載荷控制器管理軟件需求來驗證本文提出的DFT-MARTE模型及時序分析算法。需求中包括5個外部接口、27個數據流和6個功能模塊,提取如軟件接收環(huán)繞器平臺的數據注入包并向平臺發(fā)送遙測參數等需求,利用TimingFlow構建DFT-MARTE模型,如圖12所示。
圖12 DFT-MARTE模型示例
從載荷控制器管理軟件需求中提取到系統(tǒng)與外部接口之間的數據流的時序特性見表4和表5。表中數據流ID與圖12中的數據流編號一一對應,時序模式覆蓋了周期模式、突發(fā)模式、偶發(fā)模式和不規(guī)則模式,其中周期模式比較常用。表5為系統(tǒng)向外部接口發(fā)送的數據流的時序特性,屬于需求中的預期時序特性,此部分容易出現(xiàn)時序定義不準確的問題,是后續(xù)實驗主要檢查對象。
表4 外部輸入流時序特性
表5 外部輸出流預期時序特性
在需求中,健康管理功能模塊在處理數據時有50 ms的延遲,其余模塊的處理速率均為默認值。計算處理點緩存是讓處理點進行動態(tài)地改變緩存容量,后續(xù)時序檢測和分析的正常執(zhí)行可驗證處理點緩存計算算法的作用。利用本工具進行時序偏離檢測后,得到相關偏移率實驗結果為表6第二列,其中有3個數據流的實驗結果與預期時序特征偏移率較大,有3個數據流偏移概率均為個位數,甚至有兩個數據流偏移概率為0。其中偏移概率越低表明需求中時序描述越準確。上述實驗結果表明,需求中仍存在時序問題,后續(xù)時序序列分析可從除數據流1和26以外的數據流進行優(yōu)化。
表6 時序偏離概率檢測結果
以對數據流10的時序序列進行優(yōu)化為例介紹時序序列分析過程,將流向數據處理FPGA接口的輸出數據流的模擬時序序列作為訓練數據,利用本文提出的基于梯度下降的時序序列分析算法進行擬合,擬合結果如圖13和圖14所示。
圖13 時序序列擬合結果
圖14 時序序列數據分布和回歸結果
由圖13可知最終得到建議周期T為103.052 299,抖動b為6.385 254,數據流10預期周期為100 ms,抖動為5 ms,實驗結果建議周期為103 ms,抖動為6 ms。因為需求中大多數周期數據周期和抖動數值量級差別很大,所以圖14中擬合的上下兩條函數看似重合,圖中橫坐標表示當前已到達數據量,縱坐標代表數據到達的系統(tǒng)時間戳。
將其余數據流均按照上述示例得到推薦的周期模式的具體參數后,又利用時序偏離檢測算法進行檢測,具體檢測結果可見表6。時序序列分析算法可有效幫助需求人員改進需求中的時序特性。改進前后對比如圖15所示。
圖15 時序偏離檢測結果對比
本文提出了一個基于MARTE的數據流時序模型,它用于對AES的需求數據進行時序建模及分析驗證;主要創(chuàng)新性工作如下:
(1)提出一個處理點緩存計算算法,避免時序沖突,輔助時序檢測分析的正常執(zhí)行;
(2)提出一個時序偏離概率檢測算法,可以檢測數據流的時序特征與預期值的差異概率,有利于需求編寫人員改進需求;
(3)提出一個時序序列分析算法,可直觀地向需求人員提供數據流的時序特性修改意見;
本文提出的模型可描述AES中具有時序特性的數據流關系,并通過本文提出的算法可檢測出需求中的時序問題并進行優(yōu)化,利于軟件開發(fā)和維護。由案例分析可知,本文提出的算法可有效引導需求開發(fā)人員優(yōu)化時序特性。