楊 瑞

（內(nèi)蒙古集寧師范學(xué)院 內(nèi)蒙古 012000）

0 引言

目前，嵌入式系統(tǒng)在信息家電、智能控制、均是電子等領(lǐng)域的應(yīng)用廣泛。截止到2009年底，全世界的嵌入式設(shè)備量已有40億臺(tái)之多，并且嵌入式設(shè)備的數(shù)量呈快速增長(zhǎng)趨勢(shì)，而嵌入式設(shè)備每年耗電量在1000億千瓦時(shí)之上。而在目前倡導(dǎo)“低碳經(jīng)濟(jì)”的大背景中，嵌入式系統(tǒng)能耗成為了熱門(mén)重點(diǎn)關(guān)注的一個(gè)問(wèn)題，而能耗也成為了前途是系統(tǒng)設(shè)計(jì)的重要考量因素。本文將從嵌入式軟件系統(tǒng)算法級(jí)能耗優(yōu)化出發(fā)，通過(guò)對(duì)算法時(shí)間和空間復(fù)雜度的分析，提出了一種基于算法級(jí)能耗的估算模型，并采用神經(jīng)網(wǎng)絡(luò)算法和遺傳算法對(duì)問(wèn)題進(jìn)行求解，并參數(shù)了算法級(jí)能耗分析的應(yīng)用和局限，最后對(duì)其進(jìn)行模擬評(píng)估驗(yàn)證。

1 嵌入式軟件算法及能耗的建模方法

優(yōu)化嵌入式系統(tǒng)可以從軟件的不同層次來(lái)實(shí)現(xiàn)其能耗的分析優(yōu)化。針對(duì)該系統(tǒng)的硬件層要實(shí)現(xiàn)能耗的優(yōu)化要從其硬件層的為處理器、RTL和集成電路等入手。而軟件層在進(jìn)行能耗優(yōu)化時(shí)要根據(jù)設(shè)計(jì)模式從底向上進(jìn)行源程序、算法和軟件體系結(jié)構(gòu)3各級(jí)別著手來(lái)實(shí)現(xiàn)軟件功耗優(yōu)化。而大部分嵌入式系統(tǒng)是由軟件驅(qū)動(dòng)硬件而產(chǎn)生的，因此嵌入式軟件成為了系統(tǒng)能耗級(jí)優(yōu)化的重點(diǎn)。

目前，嵌入式軟件層級(jí)能耗的優(yōu)化大多數(shù)是以源程序分析為主，在對(duì)其進(jìn)行能耗優(yōu)化時(shí)通常從表達(dá)式、指令、數(shù)據(jù)表示、寄存器以及循環(huán)結(jié)構(gòu)幾個(gè)角度進(jìn)行考慮，而對(duì)于算法級(jí)能耗的優(yōu)化分析較少，而通過(guò)算法選擇和對(duì)嵌入式軟件能耗模型的分析，能夠有效的提高軟件能耗的估算效率，同時(shí)優(yōu)化嵌入式軟件的設(shè)計(jì)方案。

軟件算法是針對(duì)特定問(wèn)題的求解方法，算法分析是對(duì)算法運(yùn)行所需要時(shí)間和空間的估算，而算法的復(fù)雜程度會(huì)隨所需資源的增多了增高。以往的嵌入式軟件開(kāi)發(fā)人員在設(shè)計(jì)軟件時(shí)通常只考慮到算法所需時(shí)間和儲(chǔ)存空間，但是隨著能耗問(wèn)題的日益嚴(yán)重，在進(jìn)行軟件設(shè)計(jì)時(shí)，算法級(jí)能耗也成為其設(shè)計(jì)中的一個(gè)重要指標(biāo)。因此通過(guò)對(duì)算法及能耗的分析和比較，對(duì)能耗來(lái)源因素進(jìn)行分析，進(jìn)而構(gòu)建有效的算法級(jí)能耗模型。

2 嵌入式軟件算法級(jí)能耗建模

（1）嵌入式軟件指令級(jí)能耗模型。程序指令驅(qū)動(dòng)計(jì)算機(jī)系統(tǒng)功能部件的運(yùn)行，軟件算法則選擇性控制程序指令的執(zhí)行，因此在構(gòu)建算法級(jí)能耗建模時(shí)應(yīng)當(dāng)首先考慮程序指令級(jí)能模型的建立。Tiwari最早提出了指令級(jí)能耗模型概念，其概念的思想是指對(duì)每條指令中能夠包含對(duì)處理器多個(gè)部件的特定量化操作，并在此基礎(chǔ)上構(gòu)建軟件和硬件能耗之間的關(guān)系，兩者之間的關(guān)系式如下所示：

E=Σi(Bi×Ti)+Σi,j(Si,j×Fi,j)+ΣKEK

備注：Bi：i指令的基本能耗開(kāi)銷；

Ti：i指令的執(zhí)行頻度；

Si,j：軟件程序指令對(duì)（i，j）引起電路狀態(tài)轉(zhuǎn)換的能耗開(kāi)銷；

Fi,j：軟件程序指令對(duì)（i，j）狀態(tài)轉(zhuǎn)換程序中出現(xiàn)的頻度；

EK：其他能耗開(kāi)銷。

通過(guò)對(duì)上述指令級(jí)能耗模型的分析，說(shuō)明了軟件程序能耗主要是由于軟件程序指令驅(qū)動(dòng)相關(guān)功能部件的次數(shù)和能耗的開(kāi)銷，并且軟件的執(zhí)行頻度是由軟件的算法決定，其中軟件系統(tǒng)指令的執(zhí)行次數(shù)和耗損時(shí)間以及存儲(chǔ)空間的大小都是由算法的優(yōu)劣決定的。因此，通過(guò)嵌入式系統(tǒng)算法的優(yōu)化選擇能夠減少指令執(zhí)行的數(shù)量和次數(shù)，縮短其時(shí)間的耗用和空間的占有，依此來(lái)縮短軟件的運(yùn)行中所耗用的能耗。

（2）嵌入式軟件算法級(jí)能耗模型。精確算法級(jí)能耗模型的建立需要從軟件算法執(zhí)行次數(shù)、時(shí)間復(fù)雜度和空間復(fù)雜度三個(gè)方面來(lái)對(duì)對(duì)其算法的能耗進(jìn)行估算。第一，軟件算法執(zhí)行次數(shù)。嵌入式軟件程序員在設(shè)計(jì)算法時(shí)通常定義確定以及有限的操作，這樣的設(shè)計(jì)方法能夠方便系統(tǒng)通過(guò)一條或是多條指令的操作構(gòu)成軟件算法的執(zhí)行。因此軟件的算法執(zhí)行會(huì)產(chǎn)生相應(yīng)的能耗，而在此過(guò)程中算法執(zhí)行指令的次數(shù)則決定了軟件的能耗大小，所以選用好的算法能夠減少軟件執(zhí)行指令的操作次數(shù)，從而減少軟件的能耗，實(shí)現(xiàn)軟件的能耗優(yōu)化。

例如，對(duì)于一個(gè)含有n（n＞500）個(gè)元素已排數(shù)組，對(duì)此我們采用順序查找法和二分查找法對(duì)這些元素進(jìn)行查找。其中采用順序查找算法進(jìn)行查找時(shí)，在查找成功的情況下平均比較次數(shù)約為該數(shù)組長(zhǎng)度的一般，當(dāng)查找失敗時(shí)需要進(jìn)行n+1次比較后在確定查找結(jié)果；當(dāng)采用二分查找算法時(shí)，在對(duì)其進(jìn)行判定時(shí)可根據(jù)判定樹(shù)通過(guò)求其平均來(lái)查找長(zhǎng)度lg(n+ 1)-1，即使在最差的情況下其查找成功和失敗的比較次數(shù)也不會(huì)超過(guò)該判定書(shū)的深度。因此，采用二分查找法對(duì)含有含有n（n＞500）個(gè)元素已排數(shù)組進(jìn)行實(shí)現(xiàn)查找時(shí)，能夠在很大程度上提升查找效率，減少算法級(jí)的運(yùn)算次數(shù)，并依此來(lái)降低軟件能耗。

第二，嵌入式軟件算法級(jí)能耗算法的復(fù)雜度。算法復(fù)雜度主要包含有時(shí)間復(fù)雜度和空間復(fù)雜的。其中時(shí)間復(fù)雜度iT作為一個(gè)重要指標(biāo)來(lái)分析和判斷一個(gè)算法的好壞以及算法級(jí)對(duì)能耗的影響。時(shí)間復(fù)雜度主要是用來(lái)度量算法執(zhí)行時(shí)間的長(zhǎng)短，其中算法所耗費(fèi)的時(shí)間和算法語(yǔ)句的執(zhí)行次數(shù)成正比關(guān)系，由此可得算法中語(yǔ)句所耗費(fèi)的時(shí)間決定了程序指令所執(zhí)行的次數(shù)，進(jìn)而影響到嵌入式軟件的能耗量。因此在對(duì)軟件算法復(fù)雜度中時(shí)間復(fù)雜度的優(yōu)化主要控制好算法執(zhí)行時(shí)間的長(zhǎng)短來(lái)進(jìn)行優(yōu)化，針對(duì)其優(yōu)化目前還沒(méi)有準(zhǔn)確有效的度量方法，因此在對(duì)其進(jìn)行度量時(shí)只能在具體的算法操作中通過(guò)操作數(shù)的最大頻度對(duì)其進(jìn)行估算。

算法空間復(fù)雜度iS是指算法所需儲(chǔ)存空間的大小，算法空間復(fù)雜的大小則是用來(lái)分析軟件能耗的友誼重要指標(biāo)。在計(jì)算機(jī)軟件算法中一個(gè)算法在其運(yùn)行期間所需要申請(qǐng)使用的空間總量對(duì)軟件的能耗也會(huì)產(chǎn)生一定的影響。在嵌入式軟件算法中對(duì)于較好的算法會(huì)選擇合適的數(shù)據(jù)結(jié)構(gòu)，依此來(lái)減少其空間內(nèi)存，進(jìn)而減少軟件的能耗量。

（3）嵌入式軟件算法級(jí)能耗模型的實(shí)現(xiàn)。嵌入式軟件算法級(jí)能耗模型要建立在指令級(jí)功能模型的基礎(chǔ)上，再通過(guò)分析算法級(jí)能和算法的復(fù)雜度構(gòu)建實(shí)用性算法級(jí)能耗模型。因此在計(jì)算某算法的總能耗時(shí)其軟件算法級(jí)能模型公式如下所示：

EA={Σi(Bi×Ni)+Ti+Si}×L+Ej

備注：Bi：軟件指令i的基本能耗；

Ni：軟件指令i的執(zhí)行次數(shù)；

L：軟件運(yùn)行的時(shí)間；

Ej：軟件算法中級(jí)中其他能耗。

從上式中我們可以看出在計(jì)算軟件算法級(jí)能耗時(shí)，軟件算法復(fù)雜度和算法操作過(guò)程所產(chǎn)的能耗起著關(guān)鍵作用。

3 嵌入式算法級(jí)能耗模型的評(píng)估驗(yàn)證

在開(kāi)發(fā)嵌入式軟件系統(tǒng)的過(guò)程中，通過(guò)建立軟件算法模型除了能夠確定算法能耗的主要來(lái)源之外還能夠提高計(jì)算機(jī)軟件算法級(jí)能耗的優(yōu)化效率。通過(guò)對(duì)嵌入式軟件愛(ài)你算法級(jí)能耗問(wèn)題的研究，在幫助軟件開(kāi)發(fā)員在進(jìn)行系統(tǒng)軟件開(kāi)發(fā)時(shí)選擇低能耗算法的同時(shí)還對(duì)軟件系統(tǒng)的后期優(yōu)化起到一定的指導(dǎo)意義。

下面為了驗(yàn)證嵌入式軟件算法級(jí)能耗模型的有效性，我們通過(guò)試驗(yàn)對(duì)其進(jìn)行驗(yàn)證。第一組實(shí)驗(yàn)我們以旅行商問(wèn)題為例選用兩種不同的算法對(duì)嵌入式軟件算法級(jí)能耗模型進(jìn)行驗(yàn)證。這里選用的兩種算法分別是貪心法和動(dòng)態(tài)規(guī)劃法。采用貪心法來(lái)計(jì)算旅行商問(wèn)題時(shí)，其算法復(fù)雜度B（n2），而采用動(dòng)態(tài)規(guī)劃法時(shí)期算法復(fù)雜度B（ 2n），之后結(jié)合上述我們所說(shuō)的軟件算法級(jí)能耗模型對(duì)兩種算法的軟件指令運(yùn)行次數(shù)進(jìn)行估算，其估算結(jié)果如表 1所示，之后使用功耗仿真器對(duì)這兩種算法進(jìn)行實(shí)際測(cè)量，最后對(duì)比兩種算法級(jí)能耗的結(jié)果，通過(guò)比較得出兩種算法的誤差值約為 10%，兩者比較的結(jié)果值如表2所示。

表1 兩中算法估算旅行商問(wèn)題的能耗結(jié)果表

表2 兩組算法的能耗測(cè)試結(jié)果與估算結(jié)果的比較

第二組實(shí)驗(yàn)我們是針對(duì)旅行商問(wèn)題中能夠n值較大時(shí)，采用神經(jīng)網(wǎng)絡(luò)算法和遺傳算法；來(lái)求解此問(wèn)題。采用神經(jīng)網(wǎng)絡(luò)來(lái)求解此問(wèn)題時(shí)，首先要建立一個(gè)由N×N（（N代表城市數(shù)）神經(jīng)元的神經(jīng)網(wǎng)絡(luò)，此問(wèn)題的計(jì)算迭代次數(shù)是1000，并給該網(wǎng)絡(luò)設(shè)置一組初始權(quán)值，之后通過(guò)多次迭代計(jì)算該變此神經(jīng)元的狀態(tài)和網(wǎng)絡(luò)能量，當(dāng)此神經(jīng)元中的網(wǎng)絡(luò)能量不再降低時(shí)，此時(shí)神經(jīng)元中輸出的矩陣即為此問(wèn)題的求解。而采用遺傳算法來(lái)求解此問(wèn)題時(shí)，需要在網(wǎng)絡(luò)搜索空間中隨機(jī)和參數(shù)初始種群，并計(jì)算出其中的個(gè)體數(shù)目函數(shù)，之后通過(guò)優(yōu)化求得適合的適應(yīng)度值，再通過(guò)變異和交叉操作得到下一代個(gè)體，當(dāng)其達(dá)到最大迭代次數(shù)（500次）時(shí)將其中最好的個(gè)體輸出，之后將整個(gè)算法終止。，同時(shí)采用功耗仿真器對(duì)兩種算法進(jìn)行能耗測(cè)試。。通過(guò)比較發(fā)現(xiàn)兩者之間的誤差值約為15%。因此對(duì)于能耗較大的算法，軟件算法級(jí)能還有待優(yōu)化。

綜上所述，嵌入式軟件程序的能耗與軟件算法中執(zhí)行次數(shù)、算法復(fù)雜度、算法運(yùn)行時(shí)間有著密切的聯(lián)系。

4 結(jié)束語(yǔ)

本文通過(guò)建立和分析嵌入式軟件算法級(jí)能耗模型，得出影響軟件級(jí)算法能耗問(wèn)題的主要因素是軟件算法中執(zhí)行次數(shù)、算法復(fù)雜度、算法運(yùn)行時(shí)間。之后又通過(guò)實(shí)例采用不同的方法對(duì)建立模型的估算結(jié)果進(jìn)行了評(píng)估和驗(yàn)證，得出其影響因素即為軟件算法中執(zhí)行次數(shù)、算法復(fù)雜度、算法運(yùn)行時(shí)間，同時(shí)還結(jié)合其誤差值驗(yàn)證了能耗模型的有效性。在以后的工作中需要提出更有效的軟件算法級(jí)能耗問(wèn)題分析方法。

[1]郭真林，桑楠，江維等.基于LabVIEW的嵌入式軟件能耗測(cè)量方法[J].計(jì)算機(jī)工程，2013，39（1）：85-88.

[2]王愛(ài)峰，李曦，雷靈等.算法級(jí)能耗分析方法研究[J].計(jì)算機(jī)工程與應(yīng)用，2006，42（29）：100-102.

[3]劉嘯濱，郭兵，沈艷，王繼禾，伍元?jiǎng)?嵌入式軟件算法級(jí)功耗BP網(wǎng)絡(luò)模型研究[J].2011，40（06）.

[4]張法，Antonio Fernandez Anta，王林，侯晨穎，劉志勇.網(wǎng)絡(luò)能耗系統(tǒng)模型及能效算法[J].計(jì)算機(jī)學(xué)報(bào).2012（03）