基于復雜度的嵌入式軟件功耗模型

摘要：系統(tǒng)功耗是嵌入式系統(tǒng)的一個重要方向，功耗很大程度上取決于執(zhí)行的軟件。傳統(tǒng)的底層指令級模型功耗分析方法雖然能比較準確地估算出嵌入式系統(tǒng)的功耗，但是這種方法所需要的時間過長。本文介紹一種高層嵌入式軟件功耗分析估測方法，以對象函數(shù)所使用的算法的復雜度來對該函數(shù)構(gòu)建功耗模型，從而根據(jù)此功耗模型能快速估算出該函數(shù)在各種輸入情形下的功耗情況。

關(guān)鍵詞：算法復雜度 嵌入式系統(tǒng) 軟件功耗模型

1 嵌入式軟件功耗

嵌入式系統(tǒng)的功耗主要來自微處理器的功耗與外圍部件的功耗。雖然能量的水泵最終發(fā)生在底層硬件，但是微處理器的功耗很大程度上取決于其所執(zhí)行的軟件。因此，對嵌入式系統(tǒng)的功耗分析越來越多地轉(zhuǎn)移到軟件的角度上來，將能量的消耗過程視作軟件執(zhí)行過程。

目前的嵌入式軟件功耗分析大多數(shù)都是基于指令級功耗模型的分析方法。在這種模型中，嵌入式軟件程序的功耗由單條指令的基本功耗開銷、連續(xù)執(zhí)行不同類型的指令造成的功耗開銷以及額外的功耗開銷（如流水線斷流、Cache不命中）等構(gòu)成。雖然這種底層的嵌入式軟件功耗的分析方法的準確性較高，但是其分析過程需要在特定微處理器平臺上將程序翻譯成匯編指令，然后通過逐條指令功耗分析和綜合因素考慮，最后才能估算出該程序在某種微處理器上執(zhí)行的系統(tǒng)功能，需要相當長的分析時間。

2 基于復雜度的嵌入式軟件功耗模型

針對指令級功耗模型的瓶頸，本文介紹一種基于復雜度的嵌入式軟件功耗模型，利用現(xiàn)有條件能快速估算出某函數(shù)的功耗情況。

在嵌入式軟件應用中大量使用的多媒體計算和其它數(shù)據(jù)密集型計算中，經(jīng)常用到諸如查找、排序、矩陣運算等算法。由于這些算法的平均復雜度都是已知的，因此復雜度成為這些嵌入式軟件程序的一個重要特征，同樣也能夠成為分析和估測嵌入式軟件功耗的一種重要依據(jù)?；趶碗s度的嵌入式軟件功耗模型以具體函數(shù)所使用的算法的復雜度為建模的參數(shù)，選取該函數(shù)的典型輸入，并利用現(xiàn)有指令級模型分析方法獲得該函數(shù)在這些典型輸入情況下的功耗，利用回歸算法出該函數(shù)軟件功耗模型的系數(shù)，從而獲得完事的該函數(shù)軟件功耗模型，并可以用于快速估算該函數(shù)在任何輸入情況下的軟件功耗。

在某函數(shù)的算法復雜度是已知的或較容易獲得的情況下，假設該函數(shù)的執(zhí)行所需功耗與其復雜度有關(guān)，則可以使用一個線性公式來描述該函數(shù)的軟件功耗：

其中Pj為模型的參數(shù)與函數(shù)的算法復雜度與函數(shù)的輸入相關(guān)；cj為相應的系數(shù)；p是參數(shù)個數(shù)。

構(gòu)建模型的第一步是決定描述功耗模型的參數(shù)Pj。參數(shù)的選擇與具體的函數(shù)所使用的算法密度相關(guān)。幾種比較常見的算法的功耗模型可以表1中的線性公式來描述。

表1 基于復雜度的軟件功耗模型

算 法	平均復雜度	軟件功耗宏模型
數(shù)組求和	O(n)	c1+c2N
插入排序	O(n2)	c1+c2N+c3N2
快速排序	O（nlog2n）	c1+c2N+c3Nlog2N

參數(shù)確定之后，必須找到相應的系數(shù)cj，這是整個算法中最重要的步驟。一旦獲得系數(shù)cj后，就可以利用這些系統(tǒng)估算出該函數(shù)在任何輸入情況下的功耗。

要算出系數(shù)，首先要確定該函數(shù)的典型輸入集合S={I1,I2,…，In}，S中的每個Ii都與該函數(shù)一組模型參數(shù)Pj相對應。n個Ii對應形成一個該函數(shù)的模型參數(shù)矩陣。

通過底層指令級模型分析得到該函數(shù)在每組參數(shù)Ii情況下的功耗。

其中然后通過矩陣運算即可回歸出參數(shù)向量C。

3 基于復雜度的插入排序函數(shù)軟件功耗建模

以下將以Integrator/CM7TDMI評估板的ARM7TDMI微處理器為基礎，對插入排序函數(shù)來構(gòu)建基于復雜度的嵌入式軟件功耗模型。

假設某運行在ARM7TDMI處理器上的函數(shù)，對一長度為n的整形數(shù)組a[n]使用簡單插入排序算法進行排序。算法的C語言代碼與其經(jīng)過ARMCC編譯器編譯后的匯編代碼如下：

void ins_sort(int a[],int n){

int x,i,j;

for(i=1;in;i++)

for(j=0;ji;j++){

if(a[i]a[j]){

x=a[j];

a[j]=a[i];

a[i]=x;

}

}

}

ins_sort PROC

STR lr,[sp,#-4]!

MOV r3,#1

B |L1.56|

|L1.12| MOV r2,#0

B |L1.44|

|L1.20| LDR r12,[r0,r3,LSL #2]

LDR lr,[r0,r2,LSL #2]

CMP r12,lr

STRLT r12,[r0,r2,LSL #2]

STRL lr,[r0,r3,LSL #2]

ADD r2,r2,#1

|L1.44| CMP r2,r3

BLT |L1.20|

ADD r3,r3,#1

|L1.56| CMP r3,r1

BLT |L1.12|

LDR pc,|sp|,#4

3.1 基于復雜度的功耗模型

簡單插入排序算法平均復雜度為O（n2）。該函數(shù)的軟件功耗模型可用如下線性公式描述：

其中，n為數(shù)組的長度，E為在輸入數(shù)組長度的n的情況下函數(shù)的功耗。

3．2 獲得系數(shù)cj

在這一步驟中，主要以Integrator/CM7TDMI評估板的三段流水線、不設cache的ARM7TDMI處理器的指令級功耗模型為基礎，分析該插入排序函數(shù)分別在輸入數(shù)組長度n=10、20、40情況下的功耗情況，并通過回歸法獲得系數(shù)cj。

在該指令級功耗模型中，指令執(zhí)行的功耗主要來自兩個部分：執(zhí)行單條指令引起的功耗（base cost）與連續(xù)執(zhí)行不同類型的指令導致處理器狀態(tài)改變所引起的額外功耗（inter-instruction cost）。其公式如下：

其中，Ei為執(zhí)行第I條指令的基本指令功耗（表2），Oij為連續(xù)執(zhí)行第I條和第I指令引起的額外功耗（表3），ε為流水線斷流引起的功耗（表4）。

表2 Integrator/CM7TDMI ARM7TDMI基本指令功耗

Instruction	E/nJ	Instruction	E/nJ
ADD R2,R0,R1	0.710	KDR R2,[R1,R3]	2.774
AND R2,R0,R1	0.856	STR R2,[R1,R3]	1.961
ORR R2,R0,R1	0.907	MUL R2,R0,R1	2.768
ORRS R2,R0,R1	0.967	MLA R2,R0,R1,R0	3.748
MOV R2,R1	0.935	CMP R0,R1	0.751
MOV R0,R0	0.903	SWP R2,R0,[R1]	3.917
ADD R2,R0,R1,ASR R3	2.137	MRS R2,CPSR	0.977
B lable	3.095	MSR CPSR_f,R2	1.143

表3 執(zhí)行連接兩條源操作數(shù)類型不同指令的功耗

Instr1/Instr2	SHIFT_REG	SHIFT_IMM	REG	IMM
SHIFT_REG	-0.332	-0.215	-0.232	-0.159
SHIFT_IMM	-0.269	-0.177	-0.165	-0.103
REG	-9.02E-02	-5.98E-02	-0.186	-0.200
IMM	-0.141	-5.35E-02	-9.08E-02	-7.53E-02

表4 流水線斷流引起的功耗

Instruction type	Energy cost/nJ
Any	2.04

根據(jù)以上表中的數(shù)據(jù)結(jié)合該函數(shù)匯編指令，得出該插入排序函數(shù)的指令級功耗分析情況（表5）。

表5 簡單插入排序指令級功耗分析

指 令	Base cost	Inter cost	Stall cost
MOV r3,#1	0.930	-	-
B |L1,56|	3.100	-0.075	2.04
MOV r2,#0	0.930	-0.032	-
B |L1,44|	3.100	-0.075	2.04
LDR r12,[r0,r3,LSL #2]	3.270	-0.032	-
LDR lr,[r0,r2,LSL #2]	3.270	-0.177	-
CMP r12,lr	0.830	-0.165	2.04
STRIT r12,[r0,r2,LSL #2]	2.480	-0.060	-
STRLT lr,[r0,r3,LSL #2]	2.480	-0.177	-
CMP r2,r2,#1	1.590	-0.103	-
CMP r2,r3	0.830	-0.091	2.04
BLT |L1.20|	3.100	-0.060	2.04
ADD r3,r3,#1	1.590	-0.075	-
CMP r3,r1	0.830	-0.091	2.04
BLT |L1.12|	3.100	-0.200	2.04

至此，可以得出完整的簡單插入排序函數(shù)的基于復雜度的嵌入式軟件功耗模型

E=93.51-5.38n+10.67 2

3.3 基于復雜度的嵌入式軟件功耗模型的估算功耗

當輸入數(shù)組長度為n=80的情況下，通過該模型可快速估算出插入排序函數(shù)的功耗

E=93.51-5.3880+10.671600=67924.85(nJ)

與指令級功耗模型的估測值誤差小于1%（表6），而利用基于復雜度的功耗模型估測該函數(shù)執(zhí)行所需的功耗的速度而大大提高。

表6 各種數(shù)組長度下簡單插入排序指令級功耗

數(shù)組長度	指令級功耗模型估測	基于復雜度的功耗模型估測	誤 差
n=10	1106.338	-	-
n=20	4252.333	-	-
n=40	16943.823	-	-
n=80	67604.803	67924.85	0.4%

4 總結(jié)

本文介紹了一種基于復雜度的嵌入式軟件功耗模型，以對象函數(shù)的算法平均復雜度的建模參數(shù)，利用現(xiàn)有底層指令級功耗模型對函數(shù)進行分析，回歸出必需的系數(shù)，得到該函數(shù)完整的基于復雜度的嵌入式軟件功耗模型，從而可快速估算出該函數(shù)在不同輸入情況下的軟件功耗。這種分析方法的缺點在于只適用于算法復雜度明顯的一些函數(shù)，從而較容易構(gòu)建基于復雜度的模型。另外在建模過程中，仍然需要指令級功耗模型的分析法的協(xié)助。