基于嵌入式軟件算法級能耗問題研究

楊 瑞

（內蒙古集寧師范學院 內蒙古 012000）

0 引言

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

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

優化嵌入式系統可以從軟件的不同層次來實現其能耗的分析優化。針對該系統的硬件層要實現能耗的優化要從其硬件層的為處理器、RTL和集成電路等入手。而軟件層在進行能耗優化時要根據設計模式從底向上進行源程序、算法和軟件體系結構3各級別著手來實現軟件功耗優化。而大部分嵌入式系統是由軟件驅動硬件而產生的，因此嵌入式軟件成為了系統能耗級優化的重點。

目前，嵌入式軟件層級能耗的優化大多數是以源程序分析為主，在對其進行能耗優化時通常從表達式、指令、數據表示、寄存器以及循環結構幾個角度進行考慮，而對于算法級能耗的優化分析較少，而通過算法選擇和對嵌入式軟件能耗模型的分析，能夠有效的提高軟件能耗的估算效率，同時優化嵌入式軟件的設計方案。

軟件算法是針對特定問題的求解方法，算法分析是對算法運行所需要時間和空間的估算，而算法的復雜程度會隨所需資源的增多了增高。以往的嵌入式軟件開發人員在設計軟件時通常只考慮到算法所需時間和儲存空間，但是隨著能耗問題的日益嚴重，在進行軟件設計時，算法級能耗也成為其設計中的一個重要指標。因此通過對算法及能耗的分析和比較，對能耗來源因素進行分析，進而構建有效的算法級能耗模型。

2 嵌入式軟件算法級能耗建模

（1）嵌入式軟件指令級能耗模型。程序指令驅動計算機系統功能部件的運行，軟件算法則選擇性控制程序指令的執行，因此在構建算法級能耗建模時應當首先考慮程序指令級能模型的建立。Tiwari最早提出了指令級能耗模型概念，其概念的思想是指對每條指令中能夠包含對處理器多個部件的特定量化操作，并在此基礎上構建軟件和硬件能耗之間的關系，兩者之間的關系式如下所示：

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

備注：Bi：i指令的基本能耗開銷；

Ti：i指令的執行頻度；

Si,j：軟件程序指令對（i，j）引起電路狀態轉換的能耗開銷；

Fi,j：軟件程序指令對（i，j）狀態轉換程序中出現的頻度；

EK：其他能耗開銷。

通過對上述指令級能耗模型的分析，說明了軟件程序能耗主要是由于軟件程序指令驅動相關功能部件的次數和能耗的開銷，并且軟件的執行頻度是由軟件的算法決定，其中軟件系統指令的執行次數和耗損時間以及存儲空間的大小都是由算法的優劣決定的。因此，通過嵌入式系統算法的優化選擇能夠減少指令執行的數量和次數，縮短其時間的耗用和空間的占有，依此來縮短軟件的運行中所耗用的能耗。

（2）嵌入式軟件算法級能耗模型。精確算法級能耗模型的建立需要從軟件算法執行次數、時間復雜度和空間復雜度三個方面來對對其算法的能耗進行估算。第一，軟件算法執行次數。嵌入式軟件程序員在設計算法時通常定義確定以及有限的操作，這樣的設計方法能夠方便系統通過一條或是多條指令的操作構成軟件算法的執行。因此軟件的算法執行會產生相應的能耗，而在此過程中算法執行指令的次數則決定了軟件的能耗大小，所以選用好的算法能夠減少軟件執行指令的操作次數，從而減少軟件的能耗，實現軟件的能耗優化。

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

第二，嵌入式軟件算法級能耗算法的復雜度。算法復雜度主要包含有時間復雜度和空間復雜的。其中時間復雜度iT作為一個重要指標來分析和判斷一個算法的好壞以及算法級對能耗的影響。時間復雜度主要是用來度量算法執行時間的長短，其中算法所耗費的時間和算法語句的執行次數成正比關系，由此可得算法中語句所耗費的時間決定了程序指令所執行的次數，進而影響到嵌入式軟件的能耗量。因此在對軟件算法復雜度中時間復雜度的優化主要控制好算法執行時間的長短來進行優化，針對其優化目前還沒有準確有效的度量方法，因此在對其進行度量時只能在具體的算法操作中通過操作數的最大頻度對其進行估算。

算法空間復雜度iS是指算法所需儲存空間的大小，算法空間復雜的大小則是用來分析軟件能耗的友誼重要指標。在計算機軟件算法中一個算法在其運行期間所需要申請使用的空間總量對軟件的能耗也會產生一定的影響。在嵌入式軟件算法中對于較好的算法會選擇合適的數據結構，依此來減少其空間內存，進而減少軟件的能耗量。

（3）嵌入式軟件算法級能耗模型的實現。嵌入式軟件算法級能耗模型要建立在指令級功能模型的基礎上，再通過分析算法級能和算法的復雜度構建實用性算法級能耗模型。因此在計算某算法的總能耗時其軟件算法級能模型公式如下所示：

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

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

Ni：軟件指令i的執行次數；

L：軟件運行的時間；

Ej：軟件算法中級中其他能耗。

從上式中我們可以看出在計算軟件算法級能耗時，軟件算法復雜度和算法操作過程所產的能耗起著關鍵作用。

3 嵌入式算法級能耗模型的評估驗證

在開發嵌入式軟件系統的過程中，通過建立軟件算法模型除了能夠確定算法能耗的主要來源之外還能夠提高計算機軟件算法級能耗的優化效率。通過對嵌入式軟件愛你算法級能耗問題的研究，在幫助軟件開發員在進行系統軟件開發時選擇低能耗算法的同時還對軟件系統的后期優化起到一定的指導意義。

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

表1 兩中算法估算旅行商問題的能耗結果表

表2 兩組算法的能耗測試結果與估算結果的比較

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

綜上所述，嵌入式軟件程序的能耗與軟件算法中執行次數、算法復雜度、算法運行時間有著密切的聯系。

4 結束語

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

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

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

[3]劉嘯濱，郭兵，沈艷，王繼禾，伍元勝.嵌入式軟件算法級功耗BP網絡模型研究[J].2011，40（06）.

[4]張法，Antonio Fernandez Anta，王林，侯晨穎，劉志勇.網絡能耗系統模型及能效算法[J].計算機學報.2012（03）