基于DFT-MARTE模型的時(shí)序分析算法

徐 嘉，周 晴，杜家昊，王一華

(1.中國科學(xué)院國家空間科學(xué)中心 復(fù)雜航天系統(tǒng)電子信息技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 101499；2.中國科學(xué)院大學(xué) 計(jì)算機(jī)與控制學(xué)院，北京 101408)

0 引 言

隨著航天事業(yè)的迅速發(fā)展，復(fù)雜的需求提升了航天嵌入式軟件(aerospace embedded software，AES)的規(guī)模[1]，其開發(fā)成本和維護(hù)難度也越來越高，在需求階段更易于降低開發(fā)成本及風(fēng)險(xiǎn)[2]。AES與外部接口數(shù)據(jù)交互復(fù)雜[3]，兩者之間的聯(lián)系以及AES內(nèi)部節(jié)點(diǎn)通訊關(guān)系均可用數(shù)據(jù)流來簡化表示。傳統(tǒng)的數(shù)據(jù)流圖(data flow diagram，DFD)能描述軟件節(jié)點(diǎn)之間的數(shù)據(jù)交互關(guān)系[4]，但無法描述AES中具有時(shí)序特性的數(shù)據(jù)流。基于傳統(tǒng)數(shù)據(jù)流圖提出的同步數(shù)據(jù)流圖(synchronous data flow graph，SDFG)定義了組件間通信的周期時(shí)序特性的概念[5]，通常是用于評(píng)估DSP(digital signal processing)應(yīng)用程序[6]，不適用于AES時(shí)序需求建模。為滿足AES的頻度需求，本文考慮在DFD中融入時(shí)序特征及事件驅(qū)動(dòng)等元素。MARTE[7]是嵌入式軟件領(lǐng)域中對(duì)時(shí)間等非功能屬性定義詳盡的一個(gè)UML(unified modeling language)[8]擴(kuò)展文件，在建模過程中通常將MARTE與UML相結(jié)合來描述需求中的時(shí)序模式[9，10]，也有將MARTE、SysML(systems modeling language)[11]與pCCSL(p clock constraint specification language)相融合來描述實(shí)時(shí)嵌入式軟件的硬件和軟件的需求建模過程[12，13]，上述融合的模型大都將狀態(tài)圖或塊圖與時(shí)序特性相結(jié)合，無法在需求階段分析并改善AES中的數(shù)據(jù)流時(shí)序偏離問題[14]。

針對(duì)DFD中不具備時(shí)序特性的問題，本文提出了一個(gè)基于MARTE的數(shù)據(jù)流時(shí)序模型，彌補(bǔ)了傳統(tǒng)模型無法對(duì)AES中具有時(shí)序?qū)傩缘臄?shù)據(jù)流建模的問題；為檢測并優(yōu)化需求中時(shí)序定義不準(zhǔn)確的問題，提出了處理點(diǎn)緩存計(jì)算算法、時(shí)序偏離概率檢測算法和時(shí)序序列分析算法。

1 時(shí)序需求模型研究

1.1 DFD模型

DFD是一種結(jié)構(gòu)化分析方法，它用圖形的形式來描述數(shù)據(jù)驅(qū)動(dòng)的系統(tǒng)中數(shù)據(jù)流動(dòng)和處理的過程，包括數(shù)據(jù)源點(diǎn)、數(shù)據(jù)流、處理點(diǎn)和數(shù)據(jù)存儲(chǔ)四大組件[15]。數(shù)據(jù)源點(diǎn)是與系統(tǒng)交互數(shù)據(jù)的單元；數(shù)據(jù)流是描述節(jié)點(diǎn)間數(shù)據(jù)傳輸?shù)膯卧惶幚睃c(diǎn)是在系統(tǒng)中對(duì)傳遞來的數(shù)據(jù)進(jìn)行加工的單元；數(shù)據(jù)存儲(chǔ)是系統(tǒng)中數(shù)據(jù)停留或者將其保存的單元。數(shù)據(jù)流圖是需求分析階段對(duì)于結(jié)構(gòu)化開發(fā)描述的一種功能模型。

1.2 MARTE模型

MARTE是一個(gè)用于實(shí)時(shí)嵌入式系統(tǒng)建模和分析的UML概要文件，根據(jù)建模和分析實(shí)時(shí)和嵌入式系統(tǒng)(real time/embedded system)所需的UML擴(kuò)展來定義概念，定義了基于模型的實(shí)時(shí)和嵌入式系統(tǒng)描述的基礎(chǔ)。MARTE包括基礎(chǔ)包、設(shè)計(jì)模型包、分析模型包和附加包，提供了關(guān)鍵資源，用于說明實(shí)時(shí)嵌入式軟件的非功能性需求，例如，時(shí)間方面和約束條件等[16]。

MARTE中的時(shí)間模型描述實(shí)時(shí)嵌入式系統(tǒng)中的時(shí)間以及時(shí)間相關(guān)概念的機(jī)制，包含邏輯時(shí)間(logical time)和物理時(shí)間(chronometric time)兩個(gè)部分，以描述實(shí)時(shí)和嵌入式系統(tǒng)中諸如延遲、時(shí)間段和時(shí)鐘的概念。根據(jù)系統(tǒng)設(shè)計(jì)的精確度要求，行為時(shí)序性有3種不同程度的表示方式：因果/瞬時(shí)(causal/temporal)、時(shí)鐘/同步(clocked/ synchronou s)、物理/實(shí)時(shí)(physiceal/real time)。

1.3 DFT-MARTE模型

1.3.1 DFT-MARTE模型時(shí)序定義

本文將數(shù)據(jù)流與MARTE中的4種到達(dá)模式相結(jié)合，提出了DFT-MARTE模型。其中到達(dá)模式包括突發(fā)模式、偶發(fā)模式、不規(guī)則模式和周期模式，詳細(xì)參數(shù)信息見表1。突發(fā)模式屬于非周期性模式，包括最小到達(dá)間隔、最大到達(dá)間隔、最小數(shù)據(jù)間隔、最大數(shù)據(jù)間隔和突發(fā)量的參數(shù)，是一種在某個(gè)時(shí)間段內(nèi)突發(fā)一定數(shù)據(jù)量的時(shí)序模式，可模擬物理/實(shí)時(shí)中非周期數(shù)據(jù)的情況；偶發(fā)模式屬于非周期模式，包括最小到達(dá)間隔、最大到達(dá)間隔及抖動(dòng)的參數(shù)，是一種在某個(gè)時(shí)間段內(nèi)產(chǎn)生一個(gè)數(shù)據(jù)的時(shí)序模式，可模擬因果/瞬時(shí)的情況；不規(guī)則模式屬于非周期模式，是一個(gè)完全確定的到達(dá)模式，包括階段和時(shí)間間隔的參數(shù)，是在確定的時(shí)間間隔點(diǎn)產(chǎn)生數(shù)據(jù)流的時(shí)序模式，可模擬時(shí)鐘/同步的情況；周期模式包括周期、抖動(dòng)、相位、數(shù)據(jù)量的參數(shù)，是一種周期性產(chǎn)生數(shù)據(jù)流的時(shí)序模式，可模擬物理/實(shí)時(shí)中周期數(shù)據(jù)的情況。

表1 到達(dá)模式

1.3.2 DFT-MARTE模型時(shí)序結(jié)構(gòu)

為描述AES中數(shù)據(jù)流的時(shí)序特性，本文擴(kuò)展了數(shù)據(jù)流圖的元模型。數(shù)據(jù)流圖包括數(shù)據(jù)源點(diǎn)(data source point)、數(shù)據(jù)流(data flow)、處理點(diǎn)(processing point)和數(shù)據(jù)存儲(chǔ)(data storage)這4個(gè)組件，其元模型如圖1所示。數(shù)據(jù)流圖是一種重要的結(jié)構(gòu)設(shè)計(jì)方法，可以清晰描述系統(tǒng)整體的數(shù)據(jù)交互關(guān)系。但在描述AES的數(shù)據(jù)交互過程中，由于其中大多數(shù)據(jù)包含時(shí)序信息，簡單的數(shù)據(jù)交互圖已然無法描述AES中數(shù)據(jù)的特點(diǎn)，并且不利于需求中時(shí)序?qū)傩缘南嚓P(guān)檢查，故提出一種基于MARTE的數(shù)據(jù)流時(shí)序模型，即DFT-MARTE模型。

圖1 傳統(tǒng)數(shù)據(jù)流圖的元模型

DFT-MARTE模型的元模型是基于MARTE中的到達(dá)模式重新定義數(shù)據(jù)流圖，在傳統(tǒng)數(shù)據(jù)流圖的元模型基礎(chǔ)上添加了時(shí)序元素(time element)、緩存窗口(cache window)和隨機(jī)數(shù)據(jù)發(fā)射器(random data transmitter)模塊，其元模型如圖2所示。其中時(shí)序元素依據(jù)MARTE中的到達(dá)模式和數(shù)據(jù)流圖特點(diǎn)改寫并添加部分定義；緩存窗口是為了保證當(dāng)處理速率與輸入流總體流速不匹配時(shí)，能根據(jù)預(yù)設(shè)閾值進(jìn)行調(diào)節(jié)：當(dāng)緩存窗口中的數(shù)據(jù)大于最大閾值時(shí)，暫停所有輸入流，保證兩次握手期間所有的數(shù)據(jù)均可在緩存窗口內(nèi)存儲(chǔ)，即不溢出；為保證模型的完整性，考慮到嵌入式軟件中存在隨機(jī)事件觸發(fā)輸入數(shù)據(jù)流的場景，故而在本模型中加入隨機(jī)數(shù)據(jù)發(fā)射器模塊，該模塊可定義隨機(jī)事件。該模塊會(huì)按照定義的時(shí)序特征隨機(jī)發(fā)射數(shù)據(jù)流，保證模型正常運(yùn)行，利于后續(xù)分析時(shí)序問題。

圖2 DFT-MARTE模型的元模型

DFT-MARTE模型中的緩存窗口模塊是由優(yōu)先隊(duì)列構(gòu)成，數(shù)據(jù)模塊包括數(shù)據(jù)流基本信息和數(shù)據(jù)優(yōu)先級(jí)。緩存窗口模塊為處理點(diǎn)模塊的關(guān)聯(lián)模塊，其中優(yōu)先隊(duì)列是用來處理帶有優(yōu)先級(jí)的數(shù)據(jù)，即優(yōu)先級(jí)數(shù)據(jù)。數(shù)據(jù)模塊會(huì)對(duì)數(shù)據(jù)流的優(yōu)先級(jí)進(jìn)行定義。

通常在航天嵌入式軟件需求中，會(huì)根據(jù)實(shí)時(shí)性要求不同數(shù)據(jù)包選擇不同優(yōu)先級(jí)。針對(duì)數(shù)據(jù)流可以設(shè)定不同的優(yōu)先級(jí)，在分析過程中優(yōu)先級(jí)不能改變。因此，本文按照通用需求對(duì)數(shù)據(jù)優(yōu)先級(jí)進(jìn)行設(shè)計(jì)。

針對(duì)航天嵌入式軟件需求，設(shè)計(jì)如表2所示的4種優(yōu)先級(jí)。圖中優(yōu)先級(jí)隨著序號(hào)增大而降低，如：高精度時(shí)間廣播數(shù)據(jù)的優(yōu)先級(jí)最高，能夠打斷其它優(yōu)先級(jí)較低的數(shù)據(jù)處理過程。緩存窗口模塊中按照數(shù)據(jù)優(yōu)先級(jí)設(shè)計(jì)了4個(gè)優(yōu)先隊(duì)列，與4種數(shù)據(jù)優(yōu)先級(jí)一一對(duì)應(yīng)。當(dāng)數(shù)據(jù)到達(dá)處理點(diǎn)時(shí)，將其放入對(duì)應(yīng)的優(yōu)先隊(duì)列中。在處理數(shù)據(jù)時(shí)，優(yōu)先彈出高優(yōu)先級(jí)對(duì)應(yīng)的隊(duì)列中的數(shù)據(jù)。

表2 數(shù)據(jù)優(yōu)先級(jí)設(shè)計(jì)

DFT-MARTE模型可用圖形化的形式，清晰準(zhǔn)確地描述AES需求中有時(shí)序特性的數(shù)據(jù)流之間的關(guān)系。DFT-MARTE模型融合了DFD和MARTE，不僅解決了DFD無法展現(xiàn)數(shù)據(jù)時(shí)序性的問題，而且覆蓋了行為時(shí)序中的因果/瞬時(shí)的情況，可模擬事件驅(qū)動(dòng)的數(shù)據(jù)流，有利于進(jìn)行后續(xù)的時(shí)序相關(guān)檢查。DFT-MARTE模型與其它相關(guān)模型的比較見表3。

表3 相關(guān)模型對(duì)比

2 DFT-MARTE模型的時(shí)序分析算法研究

本節(jié)介紹基于DFT-MARTE模型提出的3個(gè)算法，其一是針對(duì)處理節(jié)點(diǎn)存在數(shù)據(jù)溢出導(dǎo)致時(shí)序檢測無法正常執(zhí)行的問題[17]，提出了一種處理點(diǎn)緩存計(jì)算算法，該算法動(dòng)態(tài)改變處理點(diǎn)緩存容量來輔助后續(xù)算法的正常執(zhí)行。其二是為引導(dǎo)用戶改進(jìn)需求中的時(shí)序?qū)傩裕岢鲆环N時(shí)序偏離概率檢測算法可計(jì)算輸出流針對(duì)定義時(shí)序的偏移概率，在需求階段可檢測出時(shí)序問題。其三是針對(duì)時(shí)序偏離概率檢測算法無法直觀地幫助需求人員改進(jìn)需求的問題，提出一種基于梯度下降算法[18]的時(shí)序序列分析算法，最終可給出建議的周期模式參數(shù)。

2.1 處理點(diǎn)緩存計(jì)算算法

處理點(diǎn)緩存計(jì)算算法是在處理具有時(shí)序特性的處理點(diǎn)時(shí)，根據(jù)處理點(diǎn)對(duì)應(yīng)輸入流的時(shí)序特性和設(shè)定的最大、最小閾值來推算所需緩存窗口容量。本算法是輔助時(shí)序檢測與分析算法，使其正常執(zhí)行。算法1為處理點(diǎn)緩存計(jì)算算法的代碼。

算法1：處理點(diǎn)緩存計(jì)算算法

輸入：Inputflows輸入流數(shù)組，n數(shù)組容量，maxThres-hold最大閾值

minThreshold最小閾值，dealSpeed處理速率

輸出：capacity緩存窗口容量

描述：用于計(jì)算處理點(diǎn)緩存容量

(1)functioncacheWindowCapacity(Inputflows, n, thres-hold)

(2) capacity, capacity1, capacity2←0 //初始化緩存容量

(3) minlength←Inputflows[0].length

(4)fori=0→n-1do//遍歷所有輸入流數(shù)組

(5) //按式(1)先進(jìn)行累加

(6) capacity1←capacity1+Inputflows[i].length

*getMaxDataFlowSpeed(Inputflows[i])

(7) //求出最短數(shù)據(jù)流長度, 為計(jì)算式(2) 作準(zhǔn)備

(8) minlength←MIN(minlength, Inputflows[i].length)

(9)endfor

(10) //完成式(1), 得到按照最大閾值計(jì)算所需的緩存容量

(11) capacity1←capacity1/(1-maxThreshold)

(12) //完成式(2), 得到按照最小閾值計(jì)算所需的緩存容量

(13) capacity2←2* minlength*dealSpeed / minThreshold

(14) //按照式(3),取上述兩個(gè)變量最大值作為結(jié)果值

(15) capacity←MAX(capacity1, capacity2)

(16)returncapacity;

(17)endfunction

輸入: Inputflow輸入流

輸出: speed該輸入流的最大流速

描述: 用于計(jì)算輸入流的最大流速

(1)functiongetMaxDataFlowSpeed(Inputflows)

(2) speed←0 //初始化速率

(3) //如果輸入流時(shí)序?yàn)橥话l(fā)模式

(4)ifInputflow.patternType is burstthen

(5) //獲取當(dāng)前突發(fā)模式下數(shù)據(jù)流時(shí)序參數(shù)信息

(6) pattern←getBurstPattern(Inputflow.patter-nId)

(7) //取最小到達(dá)間隔的反比為最大速率

(8) speed←1/pattern.minInterarrival

(9)endif

(10) //如果輸入流當(dāng)前時(shí)序特性為偶發(fā)模式

(11)ifInputflow.patternType is sporadicthen

(12) pattern←getSporadicPattern(Inputflow.patter-nId)

(13) speed←1/pattern.minInterarrival

(14)endif

(15) //如果輸入流當(dāng)前時(shí)序特性為不規(guī)則模式

(16)ifInputflow.patternType is irregularthen

(17) pattern←getIrregularPattern(Inputflow.patter-nId)

(18) //不規(guī)則模式的最小到達(dá)間隔需要遍歷時(shí)間間隔

(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) //如果輸入流當(dāng)前時(shí)序特性為周期模式

(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的核心思想是當(dāng)處理點(diǎn)緩存中的數(shù)據(jù)量與總窗口容量之比達(dá)到最大閾值時(shí)，暫停所有輸入流，需要保證剩余緩存空間仍可存儲(chǔ)暫停過程中到達(dá)的最大數(shù)據(jù)量；當(dāng)緩存窗口內(nèi)數(shù)據(jù)量與總窗口容量之比低至最小閾值時(shí)，處理點(diǎn)需要重啟輸入流，需要保證緩存中剩余數(shù)據(jù)可滿足重啟和數(shù)據(jù)傳輸過程中處理點(diǎn)的處理速率。具體過程如圖3所示。

圖3 處理點(diǎn)緩存計(jì)算

處理點(diǎn)緩存容量需要滿足最大、最小閾值兩種情況下的約束條件，因此，得出以下3個(gè)公式。其中，式(1)是計(jì)算在已知最大閾值時(shí)所需的緩存容量，其中inputflowk.length表示數(shù)據(jù)流傳輸時(shí)間，maxSpeed表示數(shù)據(jù)流傳輸?shù)淖畲笏俾剩琺axThreshold為設(shè)定的最大閾值

(1)

式(2)是計(jì)算在已知最小閾值時(shí)所需的緩存容量，其中dealSpeed是處理點(diǎn)的處理速率，minThreshold為最小閾值

(2)

式(3)為處理點(diǎn)的緩存容量需要同時(shí)大于等于式(1)、式(2)的結(jié)果，因此，最終計(jì)算結(jié)果在兩者之間取最大值

(3)

由于只有外部接口向處理點(diǎn)的輸入流具有確定的時(shí)序特性，其余輸入流的時(shí)序特性是動(dòng)態(tài)變化的。因此，在時(shí)序偏離檢測過程中，處理點(diǎn)的緩存計(jì)算是按照固定周期進(jìn)行，處理點(diǎn)緩存空間也隨之動(dòng)態(tài)變化。

2.2 時(shí)序偏離概率檢測算法

由于AES需求中與外部實(shí)體交互的數(shù)據(jù)流具有時(shí)序特性，故本算法通過利用多線程并發(fā)模擬輸入流的時(shí)序特性，模擬得到輸出流的時(shí)序特性，并將計(jì)算結(jié)果與期望時(shí)序特性進(jìn)行對(duì)比，得出輸出數(shù)據(jù)流的時(shí)序偏移概率。由于AES需求中存在優(yōu)先級(jí)搶占現(xiàn)象，本算法按照表2的優(yōu)先級(jí)設(shè)計(jì)，給每個(gè)處理點(diǎn)緩存增添了4個(gè)優(yōu)先隊(duì)列來處理優(yōu)先級(jí)數(shù)據(jù)。

若將DFT-MARTE模型簡化如圖4所示。節(jié)點(diǎn)1、2為抽象的數(shù)據(jù)源節(jié)點(diǎn)，節(jié)點(diǎn)3為處理點(diǎn)，節(jié)點(diǎn)4為外部存儲(chǔ)節(jié)點(diǎn)。在DFT-MARTE模型中，每個(gè)節(jié)點(diǎn)均具有時(shí)序序列α， 時(shí)序序列為一個(gè)有固定大小的滑動(dòng)窗口，記錄數(shù)據(jù)到達(dá)時(shí)間點(diǎn)的序列，數(shù)據(jù)源節(jié)點(diǎn)和外部存儲(chǔ)節(jié)點(diǎn)具有時(shí)序特點(diǎn)γ， 時(shí)序特點(diǎn)為表1中介紹的4種到達(dá)模式，數(shù)據(jù)流均有相位δ， 相位表示數(shù)據(jù)在數(shù)據(jù)流上傳輸消耗的時(shí)間。

圖4 DFT-MARTE模型簡化

時(shí)序偏離概率檢測算法在圖4中是計(jì)算節(jié)點(diǎn)4的模擬得到的時(shí)序序列α4與其時(shí)序特點(diǎn)γ4的匹配程度。具體流程為：節(jié)點(diǎn)1、2按照γ1、γ2模擬時(shí)序序列產(chǎn)生α1、α2， 即：α1、α2分別服從γ1、γ2；α3為α1、α2、δi、δii的疊加；α4為α3、δiii的疊加；最終計(jì)算α4與其時(shí)序特點(diǎn)γ4的匹配程度。由于此種疊加不是數(shù)學(xué)意義上的加法，是兩種時(shí)序序列均到達(dá)時(shí)產(chǎn)生的新的時(shí)序序列，本算法采用多線程并發(fā)模擬DFT-MARTE模型中的動(dòng)態(tài)時(shí)序關(guān)系。本算法的組成部分如圖5所示。

圖5 時(shí)序偏離概率檢測算法結(jié)構(gòu)

其中，多線程包括主線程、數(shù)據(jù)源線程、數(shù)據(jù)流線程和處理點(diǎn)線程。主線程負(fù)責(zé)創(chuàng)建線程、建立管道、時(shí)鐘管理和線程管理。

創(chuàng)建線程是將模型中外部實(shí)體、數(shù)據(jù)流、處理點(diǎn)和隨機(jī)事件觸發(fā)器模塊分別進(jìn)行線程創(chuàng)建，其中具有輸出流的外部實(shí)體和隨機(jī)事件觸發(fā)器模塊需要?jiǎng)?chuàng)建數(shù)據(jù)源線程，其余模塊與各自線程一一對(duì)應(yīng)；建立管道是使線程間可以通信，數(shù)據(jù)源線程至少有一個(gè)輸出管道，數(shù)據(jù)流線程僅有一個(gè)輸入和輸出管道，處理點(diǎn)線程至少有一個(gè)輸入管道和一個(gè)輸出管道；時(shí)鐘管理是管理全局時(shí)間，更新全局時(shí)間必須保證線程間的同步，可利用循環(huán)屏障，使除主線程外所有線程在單位時(shí)間內(nèi)執(zhí)行完各自任務(wù)后相互等待，當(dāng)所有線程均到達(dá)某個(gè)屏障點(diǎn)時(shí)，主線程方可遞增全局時(shí)間并使其它線程進(jìn)行后續(xù)操作；線程管理是主線程監(jiān)控全局結(jié)果集，若全局結(jié)果集覆蓋所有連接外部實(shí)體的輸出流，則改變?nèi)纸K止變量以終止其它線程。

數(shù)據(jù)源線程是根據(jù)每個(gè)輸出流的時(shí)序特性將數(shù)據(jù)寫入該輸出流對(duì)應(yīng)的管道中，其運(yùn)行流程如圖6所示。其中，在每個(gè)單位時(shí)間內(nèi)，無論是否滿足其時(shí)序特性，至少需要向輸出管道內(nèi)寫入結(jié)束數(shù)據(jù)，以表示線程在當(dāng)前時(shí)間對(duì)某個(gè)數(shù)據(jù)流完成相關(guān)時(shí)序判斷。本算法中向輸出管道寫入數(shù)據(jù)均以5個(gè)字節(jié)為單位。

圖6 數(shù)據(jù)源線程泳道

處理點(diǎn)線程的具體運(yùn)行流程如圖7所示。處理點(diǎn)線程在收到全局終止信號(hào)前，在每個(gè)單位時(shí)間內(nèi)，執(zhí)行以下3個(gè)任務(wù)：

圖7 處理點(diǎn)線程泳道

(1)將處理點(diǎn)的所有輸入管道放入隊(duì)列，依次彈出隊(duì)首的管道。若管道內(nèi)無數(shù)據(jù)，則將其放入隊(duì)列尾端；有數(shù)據(jù)則以5個(gè)字節(jié)為單位循環(huán)讀取管道中的數(shù)據(jù)，并按照數(shù)據(jù)優(yōu)先級(jí)將其放入對(duì)應(yīng)的優(yōu)先隊(duì)列中；

(2)按照優(yōu)先隊(duì)列次序和處理速率依次彈出數(shù)據(jù)，找到彈出數(shù)據(jù)關(guān)聯(lián)的后置數(shù)據(jù)流集合，循環(huán)遍歷后置數(shù)據(jù)流集合，將數(shù)據(jù)寫入對(duì)應(yīng)輸出管道內(nèi)。

(3)抵達(dá)屏障，等待其它線程完成任務(wù)。

數(shù)據(jù)流線程的具體運(yùn)行流程如圖8所示。數(shù)據(jù)流線程在收到全局終止信號(hào)前，在每個(gè)單位時(shí)間內(nèi)，執(zhí)行以下3個(gè)任務(wù)：

圖8 數(shù)據(jù)流線程泳道

(1)循環(huán)讀取輸入管道內(nèi)數(shù)據(jù)，直至讀到結(jié)束數(shù)據(jù)時(shí)，停止讀取。

(2)首先判斷線程中讀到的數(shù)據(jù)是否滿足數(shù)據(jù)流的前置約束，若不滿足，則向輸出管道內(nèi)寫入結(jié)束數(shù)據(jù)，然后進(jìn)行任務(wù)(3)；否則需判斷該數(shù)據(jù)流的目標(biāo)節(jié)點(diǎn)是否為處理點(diǎn)。若是，則向輸出管道內(nèi)寫入數(shù)據(jù)流id和結(jié)束數(shù)據(jù)；否則按照預(yù)期時(shí)序特性計(jì)算時(shí)序偏離概率，當(dāng)偏離概率連續(xù)5次波動(dòng)小于閾值，則將其寫入全局結(jié)果集。

(3)抵達(dá)屏障，等待其它線程完成任務(wù)。

當(dāng)所有線程均抵達(dá)屏障時(shí)，主線程更新全局時(shí)鐘，并判斷當(dāng)前是否滿足線程終止條件，即全局結(jié)果集中覆蓋所有連接外部實(shí)體的輸出流，若滿足，則調(diào)整全局終止變量為true；否則進(jìn)入下一個(gè)單位時(shí)間，讓其余線程繼續(xù)循環(huán)。

2.3 時(shí)序序列分析算法

由于系統(tǒng)面向外部實(shí)體的數(shù)據(jù)流的時(shí)序特性多為周期性，本算法最終給出周期模式的建議參數(shù)。本算法基于梯度下降算法將模型數(shù)據(jù)流中緩存區(qū)域的數(shù)據(jù)到達(dá)時(shí)序序列作為訓(xùn)練數(shù)據(jù)，對(duì)其進(jìn)行擬合，在使所有訓(xùn)練數(shù)據(jù)滿足周期模式下的同時(shí)，使抖動(dòng)盡可能地縮小，最終給出建議的周期和抖動(dòng)參數(shù)。

本文將時(shí)序序列中的到達(dá)的次序和時(shí)間分別作為訓(xùn)練數(shù)據(jù)中的x和y值 (x≥0且y≥0)， 訓(xùn)練數(shù)據(jù)約束如圖9所示。為保證所有的訓(xùn)練數(shù)據(jù)均落在圖中點(diǎn)狀區(qū)域內(nèi)，可得到約束條件如式(4)所示

圖9 訓(xùn)練數(shù)據(jù)約束

(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)

當(dāng)抖動(dòng)很大時(shí)，滿足約束條件的周期就會(huì)在一個(gè)范圍內(nèi)，則得到的周期具有不確定性。為使最終建議的周期值T更精確，需要得到最小的抖動(dòng)值b。 如式(5)所示，可通過優(yōu)化 (y-Tx)2從而優(yōu)化抖動(dòng)值b， 因此，設(shè)計(jì)損失函數(shù)如式(6)所示

(6)

根據(jù)式(5)可知，抖動(dòng)值b僅存在一個(gè)極值點(diǎn)。因此，基于梯度下降算法思想，將學(xué)習(xí)率設(shè)置為0.01，利用式(7)不斷更新周期值T， 從而找到抖動(dòng)值b的極值點(diǎn)

(7)

當(dāng)損失函數(shù)收斂后，得到周期值T， 并按照式(8)計(jì)算出最小值b， 最終將得到的周期值T和抖動(dòng)值b作為參考建議提供給需求人員

(8)

3 案例分析

為優(yōu)化航天嵌入式軟件需求，本文基于DFT-MARTE模型和時(shí)序偏離概率檢測算法開發(fā)出一款DFT-MARTE模型構(gòu)建及檢測工具(TimingFlow)，TimingFlow界面包括功能區(qū)、模型元素區(qū)、畫布區(qū)、數(shù)據(jù)特性區(qū)和工具區(qū)，工具界面如圖10所示。

圖10 TimingFlow界面

TimingFlow可構(gòu)建的DFT-MARTE模型，利于需求人員描述需求中時(shí)序特性數(shù)據(jù)的交互關(guān)系。

處理點(diǎn)屬性的處理速率為默認(rèn)值時(shí)，即該處理點(diǎn)可以處理所有到達(dá)的數(shù)據(jù)，設(shè)定的最大閾值和最小閾值是為了計(jì)算處理點(diǎn)緩存，以保證偏離概率檢測的正常進(jìn)行；數(shù)據(jù)流屬性中定義了相關(guān)時(shí)序特性和數(shù)據(jù)優(yōu)先級(jí)信息；隨機(jī)事件發(fā)射器屬性關(guān)聯(lián)了隨機(jī)事件與數(shù)據(jù)流，TimingFlow對(duì)DFT-MARTE模型中模塊屬性具體定義如圖11所示。

圖11 模塊特性

為驗(yàn)證本模型可以滿足航天領(lǐng)域嵌入式軟件需求，以某載荷控制器管理軟件需求來驗(yàn)證本文提出的DFT-MARTE模型及時(shí)序分析算法。需求中包括5個(gè)外部接口、27個(gè)數(shù)據(jù)流和6個(gè)功能模塊，提取如軟件接收環(huán)繞器平臺(tái)的數(shù)據(jù)注入包并向平臺(tái)發(fā)送遙測參數(shù)等需求，利用TimingFlow構(gòu)建DFT-MARTE模型，如圖12所示。

圖12 DFT-MARTE模型示例

從載荷控制器管理軟件需求中提取到系統(tǒng)與外部接口之間的數(shù)據(jù)流的時(shí)序特性見表4和表5。表中數(shù)據(jù)流ID與圖12中的數(shù)據(jù)流編號(hào)一一對(duì)應(yīng)，時(shí)序模式覆蓋了周期模式、突發(fā)模式、偶發(fā)模式和不規(guī)則模式，其中周期模式比較常用。表5為系統(tǒng)向外部接口發(fā)送的數(shù)據(jù)流的時(shí)序特性，屬于需求中的預(yù)期時(shí)序特性，此部分容易出現(xiàn)時(shí)序定義不準(zhǔn)確的問題，是后續(xù)實(shí)驗(yàn)主要檢查對(duì)象。

表4 外部輸入流時(shí)序特性

表5 外部輸出流預(yù)期時(shí)序特性

在需求中，健康管理功能模塊在處理數(shù)據(jù)時(shí)有50 ms的延遲，其余模塊的處理速率均為默認(rèn)值。計(jì)算處理點(diǎn)緩存是讓處理點(diǎn)進(jìn)行動(dòng)態(tài)地改變緩存容量，后續(xù)時(shí)序檢測和分析的正常執(zhí)行可驗(yàn)證處理點(diǎn)緩存計(jì)算算法的作用。利用本工具進(jìn)行時(shí)序偏離檢測后，得到相關(guān)偏移率實(shí)驗(yàn)結(jié)果為表6第二列，其中有3個(gè)數(shù)據(jù)流的實(shí)驗(yàn)結(jié)果與預(yù)期時(shí)序特征偏移率較大，有3個(gè)數(shù)據(jù)流偏移概率均為個(gè)位數(shù)，甚至有兩個(gè)數(shù)據(jù)流偏移概率為0。其中偏移概率越低表明需求中時(shí)序描述越準(zhǔn)確。上述實(shí)驗(yàn)結(jié)果表明，需求中仍存在時(shí)序問題，后續(xù)時(shí)序序列分析可從除數(shù)據(jù)流1和26以外的數(shù)據(jù)流進(jìn)行優(yōu)化。

表6 時(shí)序偏離概率檢測結(jié)果

以對(duì)數(shù)據(jù)流10的時(shí)序序列進(jìn)行優(yōu)化為例介紹時(shí)序序列分析過程，將流向數(shù)據(jù)處理FPGA接口的輸出數(shù)據(jù)流的模擬時(shí)序序列作為訓(xùn)練數(shù)據(jù)，利用本文提出的基于梯度下降的時(shí)序序列分析算法進(jìn)行擬合，擬合結(jié)果如圖13和圖14所示。

圖13 時(shí)序序列擬合結(jié)果

圖14 時(shí)序序列數(shù)據(jù)分布和回歸結(jié)果

由圖13可知最終得到建議周期T為103.052 299，抖動(dòng)b為6.385 254，數(shù)據(jù)流10預(yù)期周期為100 ms，抖動(dòng)為5 ms，實(shí)驗(yàn)結(jié)果建議周期為103 ms，抖動(dòng)為6 ms。因?yàn)樾枨笾写蠖鄶?shù)周期數(shù)據(jù)周期和抖動(dòng)數(shù)值量級(jí)差別很大，所以圖14中擬合的上下兩條函數(shù)看似重合，圖中橫坐標(biāo)表示當(dāng)前已到達(dá)數(shù)據(jù)量，縱坐標(biāo)代表數(shù)據(jù)到達(dá)的系統(tǒng)時(shí)間戳。

將其余數(shù)據(jù)流均按照上述示例得到推薦的周期模式的具體參數(shù)后，又利用時(shí)序偏離檢測算法進(jìn)行檢測，具體檢測結(jié)果可見表6。時(shí)序序列分析算法可有效幫助需求人員改進(jìn)需求中的時(shí)序特性。改進(jìn)前后對(duì)比如圖15所示。

圖15 時(shí)序偏離檢測結(jié)果對(duì)比

4 結(jié)束語

本文提出了一個(gè)基于MARTE的數(shù)據(jù)流時(shí)序模型，它用于對(duì)AES的需求數(shù)據(jù)進(jìn)行時(shí)序建模及分析驗(yàn)證；主要?jiǎng)?chuàng)新性工作如下：

(1)提出一個(gè)處理點(diǎn)緩存計(jì)算算法，避免時(shí)序沖突，輔助時(shí)序檢測分析的正常執(zhí)行；

(2)提出一個(gè)時(shí)序偏離概率檢測算法，可以檢測數(shù)據(jù)流的時(shí)序特征與預(yù)期值的差異概率，有利于需求編寫人員改進(jìn)需求；

(3)提出一個(gè)時(shí)序序列分析算法，可直觀地向需求人員提供數(shù)據(jù)流的時(shí)序特性修改意見；

本文提出的模型可描述AES中具有時(shí)序特性的數(shù)據(jù)流關(guān)系，并通過本文提出的算法可檢測出需求中的時(shí)序問題并進(jìn)行優(yōu)化，利于軟件開發(fā)和維護(hù)。由案例分析可知，本文提出的算法可有效引導(dǎo)需求開發(fā)人員優(yōu)化時(shí)序特性。