王子豪 禹春竹 王 寶 韓翔宇

北京航天自動(dòng)控制研究所，北京100854

隨著航天領(lǐng)域的不斷發(fā)展，航天嵌入式軟件的規(guī)模、復(fù)雜度日益增長(zhǎng)，安全性、可靠性等方面的需求也不斷提高，這對(duì)傳統(tǒng)嵌入式軟件開發(fā)方法提出了很大的挑戰(zhàn)。作為一種解決方案，基于模型驅(qū)動(dòng)的軟件開發(fā)方法得到了一定的應(yīng)用與發(fā)展，相較于傳統(tǒng)的軟件開發(fā)方法，基于模型驅(qū)動(dòng)的軟件開發(fā)方法具有開發(fā)效率高、成本低等優(yōu)點(diǎn)，同時(shí)形式化建模以及模型驗(yàn)證技術(shù)可以提升軟件的安全性、可靠性，能更好地滿足嵌入式軟件開發(fā)的需求。

基于模型驅(qū)動(dòng)的軟件開發(fā)方法中的一項(xiàng)重要內(nèi)容是代碼自動(dòng)生成技術(shù)。目前，SCADE，UML和Simulink等建模工具均支持代碼自動(dòng)生成，但相對(duì)于其他工具，SCADE自動(dòng)生成的代碼滿足DO-178B標(biāo)準(zhǔn)，與模型具有一致性，可直接與項(xiàng)目其他部分代碼進(jìn)行集成[1]，具有很大優(yōu)勢(shì)，故本文選擇SCADE作為建模工具。

SCADE建模工具對(duì)控制系統(tǒng)等邏輯控制軟件的設(shè)計(jì)、實(shí)現(xiàn)方法較為完善，已有很多成功、完善的案例[2-3]。但對(duì)于圖像處理算法這類具有數(shù)據(jù)量大、迭代計(jì)算次數(shù)多等特點(diǎn)的建模對(duì)象，SCADE是否能夠建立出執(zhí)行效率滿足需求的算法模型，是值得關(guān)注的問(wèn)題。本文對(duì)基于SCADE的圖像處理算法的實(shí)現(xiàn)進(jìn)行了探索，建立了圖像處理經(jīng)典算法Sobel算法的模型，對(duì)模型優(yōu)化方法進(jìn)行了總結(jié)，并針對(duì)算法模型的執(zhí)行效率進(jìn)行了優(yōu)化，得到了具有較高執(zhí)行效率的算法模型。

1 簡(jiǎn)介

1.1 建模工具簡(jiǎn)介

SCADE(全稱為Safety Critical Application Development Environment)是由法國(guó)ESTEREL技術(shù)公司開發(fā)的高安全性應(yīng)用開發(fā)環(huán)境，其針對(duì)高安全性系統(tǒng)及軟件開發(fā)提出了一套完整的基于模型驅(qū)動(dòng)的嵌入式開發(fā)解決方案[4]。利用該開發(fā)環(huán)境可有效地節(jié)約開發(fā)、測(cè)試時(shí)間，同時(shí)可更好地滿足軟件安全性需求。

SCADE模型設(shè)計(jì)工具SCADE Suite的核心是形式化同步語(yǔ)言Lustre語(yǔ)言，在用戶建立圖形化模型之后，系統(tǒng)將圖形化模型轉(zhuǎn)換為形式化語(yǔ)言，進(jìn)而利用KCG代碼生成器自動(dòng)生成可執(zhí)行的C代碼。生成的C代碼可保證與模型具有一致性，通過(guò)SCADE自身仿真工具進(jìn)行模型仿真，結(jié)果符合預(yù)期，則生成的代碼可集成至項(xiàng)目中。

1.2 實(shí)現(xiàn)算法簡(jiǎn)介

圖像邊緣檢測(cè)是圖像處理領(lǐng)域中的一個(gè)經(jīng)典問(wèn)題，其目的是檢測(cè)出目標(biāo)圖像中的邊緣信息，即檢測(cè)出目標(biāo)圖像中局部變化最為明顯的部分。目前已有很多成熟的邊緣檢測(cè)算法，如差分邊緣檢測(cè)、Reborts算法、Sobel算法等[5]，其中Sobel算法因其簡(jiǎn)單且高效等優(yōu)點(diǎn)，在航天領(lǐng)域的圖像信息處理等軟件中有著極為重要的應(yīng)用；而且Sobel算法具備圖像處理算法的典型特點(diǎn)，所以本文選取Sobel算法作為研究對(duì)象。

Sobel算法的核心是2個(gè)Sobel算子，可記為x方向梯度算子和y方向梯度算子，分別用來(lái)檢測(cè)目標(biāo)圖像的水平邊緣和垂直邊緣，具體表示如下：

將目標(biāo)圖像與Sx和Sy算子進(jìn)行卷積運(yùn)算，即可得到邊緣信息圖像。邊緣信息圖像位于邊界行列的點(diǎn)均賦為0，其他點(diǎn)的計(jì)算公式為：

其中，S(x,y)為圖像中一點(diǎn)灰度值；(x,y)為該點(diǎn)坐標(biāo)，Sx(x,y)及Sy(x,y)分別為該點(diǎn)與x，y方向梯度算子卷積結(jié)果。

目前成熟的Sobel算法(由于水平邊緣檢測(cè)與垂直邊緣檢測(cè)算法實(shí)現(xiàn)上具有相似性， 所以本文后續(xù)對(duì)Sobel算法的討論與建模均以水平邊緣檢測(cè)為例)程序的流程圖如圖1所示。

2 基于SCADE的Sobel算法

2.1 模型的建立

根據(jù)傳統(tǒng)Sobel算法實(shí)現(xiàn)思路，利用SCADE工具進(jìn)行建模，模型的實(shí)現(xiàn)共分為3層。

頂層模型如圖2所示。

圖1 Sobel算法流程圖

圖2 算法實(shí)現(xiàn)的頂層模型

本層模型利用全0數(shù)組作為FOLD迭代器中累加器的輸入，對(duì)累加器進(jìn)行初始化，將原始圖像srcImage作為迭代器輸入，經(jīng)過(guò)(Height-1)次迭代計(jì)算輸出結(jié)果圖像，其中迭代器內(nèi)部實(shí)現(xiàn)如圖3所示。

圖3 算法實(shí)現(xiàn)的中層模型

本層利用if-else塊實(shí)現(xiàn)以下功能：當(dāng)進(jìn)行第一次迭代時(shí)，模型執(zhí)行if節(jié)點(diǎn)中的操作，利用累加器中的全0數(shù)組對(duì)結(jié)果圖像進(jìn)行初始化；當(dāng)進(jìn)行第二次及以后的迭代時(shí)，模型將執(zhí)行else節(jié)點(diǎn)中的操作，再次利用全0數(shù)組作為第二層中FOLD迭代器累加器的輸入，并將原始圖像srcImage以及當(dāng)前迭代次數(shù)(行索引)作為迭代器輸入，經(jīng)過(guò)(Width-1)次迭代計(jì)算輸出結(jié)果圖像，該層迭代器內(nèi)部實(shí)現(xiàn)如圖4所示。

本層首先通過(guò)計(jì)算迭代次數(shù)，確定本次迭代的目標(biāo)點(diǎn)索引，并將索引存儲(chǔ)為局部變量icur，然后利用if-else塊實(shí)現(xiàn)以下功能：當(dāng)進(jìn)行第1次迭代時(shí)，模型執(zhí)行if節(jié)點(diǎn)中的操作，對(duì)結(jié)果圖像全賦為0；當(dāng)進(jìn)行第2次及以后的迭代時(shí)，模型將執(zhí)行else節(jié)點(diǎn)中的操作，根據(jù)水平邊緣檢測(cè)公式對(duì)目標(biāo)點(diǎn)進(jìn)行計(jì)算，并將結(jié)果賦予結(jié)果圖像數(shù)組對(duì)應(yīng)索引的元素。

通過(guò)進(jìn)行模型仿真，模型計(jì)算結(jié)果符合預(yù)期，模型建立正確。但通過(guò)SCADE性能分析工具分析發(fā)現(xiàn)模型執(zhí)行效率較低，迭代器部分的時(shí)間開銷很大，故考慮對(duì)模型進(jìn)行優(yōu)化。

圖4 算法實(shí)現(xiàn)的底層模型

2.2 優(yōu)化方案

2.2.1 合理選擇迭代器

SCADE提供了2類迭代器，用來(lái)對(duì)數(shù)組進(jìn)行迭代計(jì)算和處理，分別稱為FOLD迭代器和MAP迭代器。

FOLD迭代器：

圖5為一個(gè)迭代次數(shù)為N的FOLD迭代器，其中a和Output分別作為迭代器的輸入和輸出，Input1, Input2,……InputM均為長(zhǎng)度為N的數(shù)組(元素?cái)?shù)據(jù)類型與a和Output相同)，作為迭代器的輸入，Operator可看作迭代計(jì)算函數(shù)。該FOLD迭代器生成代碼的格式為：

for (idx = 0; idx

kcg_copy(&acc,Output);

Operator(

idx,

&acc,

Input1,

…

InputM,

output);

MAP迭代器：

圖5 fold迭代器示意圖

圖6為一個(gè)迭代次數(shù)為N的MAP迭代器，其中Input1, Input2, …… ，InputM均為長(zhǎng)度為N的數(shù)組，作為迭代器的輸入，Output同樣為長(zhǎng)度為N的數(shù)組，作為迭代器的輸出，Operator可看作迭代計(jì)算函數(shù)。該MAP迭代器生成代碼的格式為：

for (idx = 0; idx

(*output)[idx] = Operator(

idx,

Input1[idx],

…

InputM[idx]);

}

圖6 MAP迭代器示意圖

對(duì)比2種迭代器生成的代碼可以看出，F(xiàn)OLD迭代器在每次循環(huán)的開始，都會(huì)利用拷貝函數(shù)，將上次循環(huán)計(jì)算出的結(jié)果拷貝到累加器中，如果進(jìn)行迭代計(jì)算的數(shù)據(jù)量很大，則拷貝的過(guò)程會(huì)對(duì)程序的執(zhí)行造成很大的開銷。所以，在數(shù)據(jù)量較大且迭代計(jì)算次數(shù)多的情況下，除非無(wú)法利用MAP迭代器建立滿足需求的模型，否則在模型設(shè)計(jì)中應(yīng)當(dāng)盡量規(guī)避FOLD迭代器的使用，即盡可能通過(guò)重新設(shè)計(jì)算法流程，使用MAP迭代器對(duì)FOLD迭代器進(jìn)行替換，達(dá)到減少迭代處理的時(shí)間開銷的目的。

2.2.2 工具方面的優(yōu)化

除了模型設(shè)計(jì)上的優(yōu)化，還可以利用KCG代碼生成器內(nèi)置的一些程序執(zhí)行效率的優(yōu)化功能來(lái)對(duì)模型進(jìn)行小幅優(yōu)化，此處列舉2項(xiàng)對(duì)本次算法優(yōu)化有效的優(yōu)化功能:

在KCG設(shè)置中可以將某一模塊設(shè)置為“Expand”，即內(nèi)聯(lián)模塊，這樣在代碼生成過(guò)程中該模塊將以內(nèi)聯(lián)函數(shù)的方式生成，從而在代碼執(zhí)行時(shí)，可以有效地節(jié)省調(diào)用函數(shù)帶來(lái)的額外時(shí)間開銷。與選取函數(shù)作為內(nèi)聯(lián)函數(shù)的標(biāo)準(zhǔn)相同，建模時(shí)應(yīng)當(dāng)選取調(diào)用次數(shù)多，且內(nèi)部實(shí)現(xiàn)簡(jiǎn)單的模塊作為內(nèi)聯(lián)模塊。

另外，在KCG設(shè)置中可以將局部變量設(shè)置為static形式，即將其定義在靜態(tài)存儲(chǔ)區(qū)，這樣所有局部變量會(huì)在程序初始化時(shí)被分配定義，從而在程序執(zhí)行時(shí)能夠節(jié)省變量分配時(shí)間，達(dá)到執(zhí)行時(shí)間優(yōu)化的目的。

2.3 優(yōu)化后的算法模型

根據(jù)上文分析、總結(jié)的優(yōu)化方法，利用map迭代器實(shí)現(xiàn)Sobel算法，頂層模型如圖7所示。

圖7 優(yōu)化后的頂層模型

根據(jù)map迭代器的實(shí)現(xiàn)特性，將算法拆分為兩部分實(shí)現(xiàn)，即先迭代處理每一行元素，實(shí)現(xiàn)初始矩陣列與列之間的計(jì)算；隨后對(duì)處理后的矩陣進(jìn)行轉(zhuǎn)置，再對(duì)每一列元素進(jìn)行迭代處理，實(shí)現(xiàn)初始矩陣行與行之間的計(jì)算，最后經(jīng)過(guò)轉(zhuǎn)置得到最終輸出圖像矩陣。2部分內(nèi)容的實(shí)現(xiàn)邏輯相似，故本文只介紹第一部分內(nèi)容。圖8為該層迭代器(Row_Deliver)內(nèi)部模型。

圖8 優(yōu)化后的中層模型

將上層模型傳入的原始圖像矩陣的行作為map迭代器的輸入，對(duì)其進(jìn)行迭代計(jì)算，迭代器內(nèi)部具體計(jì)算邏輯、方法如圖9所示。

圖9 優(yōu)化后的底層模型

本層利用if-else塊實(shí)現(xiàn)以下功能：如果是行內(nèi)首尾元素，則輸出為0；否則計(jì)算當(dāng)前索引對(duì)應(yīng)元素的前一位元素和后一位元素之差，將差值賦給結(jié)果數(shù)組的該索引元素。

通過(guò)進(jìn)行模型仿真，模型計(jì)算結(jié)果符合預(yù)期，模型建立正確。

3 實(shí)驗(yàn)

將優(yōu)化前后的模型分別生成代碼，導(dǎo)入現(xiàn)有工程，配置接口，與手寫成熟代碼進(jìn)行執(zhí)行時(shí)間對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)平臺(tái)為聯(lián)想ThinkCentre M4500t，配置Intel(R) Core(TM) i7-4790 CPU,主頻3.60GHz，內(nèi)存3.41GB。搭載操作系統(tǒng)為Windows XP Professional，使用集成開發(fā)環(huán)境Visual Studio 2010。

2種模型生成代碼執(zhí)行結(jié)果與手寫成熟代碼均相同，代碼執(zhí)行時(shí)間的對(duì)比如表1所示。

表1 代碼執(zhí)行時(shí)間對(duì)比

通過(guò)表1可以看出，對(duì)模型進(jìn)行優(yōu)化之后，代碼的執(zhí)行時(shí)間提升了2個(gè)數(shù)量級(jí)，有效縮短了與手寫成熟代碼之間的差距。也說(shuō)明SCADE針對(duì)Sobel此類運(yùn)算數(shù)據(jù)多、迭代計(jì)算次數(shù)多的算法，可以建立出正確、具有可靠性的模型，并且可以通過(guò)模型設(shè)計(jì)思路的優(yōu)化，建立執(zhí)行效率較高的模型。

4 結(jié)論

根據(jù)傳統(tǒng)Sobel算法的實(shí)現(xiàn)流程設(shè)計(jì)了基于SCADE的Sobel算法模型，針對(duì)模型時(shí)間開銷過(guò)大的問(wèn)題，對(duì)模型進(jìn)行了分析，總結(jié)了優(yōu)化方法；通過(guò)重新設(shè)計(jì)模型(使用MAP迭代器以減少迭代計(jì)算開銷)以及使用KCG代碼生成器內(nèi)置優(yōu)化功能對(duì)模型進(jìn)行了優(yōu)化，使其生成代碼執(zhí)行效率提升了2個(gè)數(shù)量級(jí)，具備了進(jìn)行工程化的基礎(chǔ)。

受到工具本身的制約，利用SCADE對(duì)數(shù)據(jù)量大、迭代計(jì)算次數(shù)多的算法進(jìn)行建模，在迭代過(guò)程中不可避免會(huì)造成一定的開銷，使得程序執(zhí)行效率低于人工編寫的成熟代碼。所以在設(shè)計(jì)模型時(shí)，要結(jié)合工具能力而不是完全依靠傳統(tǒng)編碼思想進(jìn)行設(shè)計(jì)，盡可能地提高程序執(zhí)行效率。