基于復(fù)雜度的嵌入式軟件功耗模型
關(guān)鍵詞：算法復(fù)雜度 嵌入式系統(tǒng) 軟件功耗模型
1 嵌入式軟件功耗
嵌入式系統(tǒng)的功耗主要來(lái)自微處理器的功耗與外圍部件的功耗。雖然能量的水泵最終發(fā)生在底層硬件，但是微處理器的功耗很大程度上取決于其所執(zhí)行的軟件。因此，對(duì)嵌入式系統(tǒng)的功耗分析越來(lái)越多地轉(zhuǎn)移到軟件的角度上來(lái)，將能量的消耗過(guò)程視作軟件執(zhí)行過(guò)程。
目前的嵌入式軟件功耗分析大多數(shù)都是基于指令級(jí)功耗模型的分析方法。在這種模型中，嵌入式軟件程序的功耗由單條指令的基本功耗開(kāi)銷(xiāo)、連續(xù)執(zhí)行不同類(lèi)型的指令造成的功耗開(kāi)銷(xiāo)以及額外的功耗開(kāi)銷(xiāo)（如流水線斷流、Cache不命中）等構(gòu)成。雖然這種底層的嵌入式軟件功耗的分析方法的準(zhǔn)確性較高，但是其分析過(guò)程需要在特定微處理器平臺(tái)上將程序翻譯成匯編指令，然后通過(guò)逐條指令功耗分析和綜合因素考慮，最后才能估算出該程序在某種微處理器上執(zhí)行的系統(tǒng)功能，需要相當(dāng)長(zhǎng)的分析時(shí)間。
2 基于復(fù)雜度的嵌入式軟件功耗模型
針對(duì)指令級(jí)功耗模型的瓶頸，本文介紹一種基于復(fù)雜度的嵌入式軟件功耗模型，利用現(xiàn)有條件能快速估算出某函數(shù)的功耗情況。
在嵌入式軟件應(yīng)用中大量使用的多媒體計(jì)算和其它數(shù)據(jù)密集型計(jì)算中，經(jīng)常用到諸如查找、排序、矩陣運(yùn)算等算法。由于這些算法的平均復(fù)雜度都是已知的，因此復(fù)雜度成為這些嵌入式軟件程序的一個(gè)重要特征，同樣也能夠成為分析和估測(cè)嵌入式軟件功耗的一種重要依據(jù)?；趶?fù)雜度的嵌入式軟件功耗模型以具體函數(shù)所使用的算法的復(fù)雜度為建模的參數(shù)，選取該函數(shù)的典型輸入，并利用現(xiàn)有指令級(jí)模型分析方法獲得該函數(shù)在這些典型輸入情況下的功耗，利用回歸算法出該函數(shù)軟件功耗模型的系數(shù)，從而獲得完事的該函數(shù)軟件功耗模型，并可以用于快速估算該函數(shù)在任何輸入情況下的軟件功耗。
在某函數(shù)的算法復(fù)雜度是已知的或較容易獲得的情況下，假設(shè)該函數(shù)的執(zhí)行所需功耗與其復(fù)雜度有關(guān)，則可以使用一個(gè)線性公式來(lái)描述該函數(shù)的軟件功耗：
其中Pj為模型的參數(shù)與函數(shù)的算法復(fù)雜度與函數(shù)的輸入相關(guān)；cj為相應(yīng)的系數(shù)；p是參數(shù)個(gè)數(shù)。
構(gòu)建模型的第一步是決定描述功耗模型的參數(shù)Pj。參數(shù)的選擇與具體的函數(shù)所使用的算法密度相關(guān)。幾種比較常見(jiàn)的算法的功耗模型可以表1中的線性公式來(lái)描述。
表1 基于復(fù)雜度的軟件功耗模型
| 算 法 | 平均復(fù)雜度 | 軟件功耗宏模型 |
| 數(shù)組求和 | O(n) | c1+c2N |
| 插入排序 | O(n2) | c1+c2N+c3N2 |
| 快速排序 | O（nlog2n） | c1+c2N+c3Nlog2N |
參數(shù)確定之后，必須找到相應(yīng)的系數(shù)cj，這是整個(gè)算法中最重要的步驟。一旦獲得系數(shù)cj后，就可以利用這些系統(tǒng)估算出該函數(shù)在任何輸入情況下的功耗。
要算出系數(shù)，首先要確定該函數(shù)的典型輸入集合S={I1,I2,…，In}，S中的每個(gè)Ii都與該函數(shù)一組模型參數(shù)Pj相對(duì)應(yīng)。n個(gè)Ii對(duì)應(yīng)形成一個(gè)該函數(shù)的模型參數(shù)矩陣。
通過(guò)底層指令級(jí)模型分析得到該函數(shù)在每組參數(shù)Ii情況下的功耗。
其中然后通過(guò)矩陣運(yùn)算即可回歸出參數(shù)向量C。
3 基于復(fù)雜度的插入排序函數(shù)軟件功耗建模
以下將以Integrator/CM7TDMI評(píng)估板的ARM7TDMI微處理器為基礎(chǔ)，對(duì)插入排序函數(shù)來(lái)構(gòu)建基于復(fù)雜度的嵌入式軟件功耗模型。
假設(shè)某運(yùn)行在ARM7TDMI處理器上的函數(shù)，對(duì)一長(zhǎng)度為n的整形數(shù)組a[n]使用簡(jiǎn)單插入排序算法進(jìn)行排序。算法的C語(yǔ)言代碼與其經(jīng)過(guò)ARMCC編譯器編譯后的匯編代碼如下：
void ins_sort(int a[],int n){
int x,i,j;
for(i=1;i<n;i++)
for(j=0;j<i;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 基于復(fù)雜度的功耗模型
簡(jiǎn)單插入排序算法平均復(fù)雜度為O（n2）。該函數(shù)的軟件功耗模型可用如下線性公式描述：
其中，n為數(shù)組的長(zhǎng)度，E為在輸入數(shù)組長(zhǎng)度的n的情況下函數(shù)的功耗。
3．2 獲得系數(shù)cj
在這一步驟中，主要以Integrator/CM7TDMI評(píng)估板的三段流水線、不設(shè)cache的ARM7TDMI處理器的指令級(jí)功耗模型為基礎(chǔ)，分析該插入排序函數(shù)分別在輸入數(shù)組長(zhǎng)度n=10、20、40情況下的功耗情況，并通過(guò)回歸法獲得系數(shù)cj。
在該指令級(jí)功耗模型中，指令執(zhí)行的功耗主要來(lái)自?xún)蓚€(gè)部分：執(zhí)行單條指令引起的功耗（base cost）與連續(xù)執(zhí)行不同類(lèi)型的指令導(dǎo)致處理器狀態(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ù)類(lèi)型不同指令的功耗
| 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ù)的指令級(jí)功耗分析情況（表5）。
表5 簡(jiǎn)單插入排序指令級(jí)功耗分析
| 指 令 | 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 |
至此，可以得出完整的簡(jiǎn)單插入排序函數(shù)的基于復(fù)雜度的嵌入式軟件功耗模型
E=93.51-5.38n+10.67 2
3.3 基于復(fù)雜度的嵌入式軟件功耗模型的估算功耗
當(dāng)輸入數(shù)組長(zhǎng)度為n=80的情況下，通過(guò)該模型可快速估算出插入排序函數(shù)的功耗
E=93.51-5.38×80+10.67×1600=67924.85(nJ)
與指令級(jí)功耗模型的估測(cè)值誤差小于1%（表6），而利用基于復(fù)雜度的功耗模型估測(cè)該函數(shù)執(zhí)行所需的功耗的速度而大大提高。
表6 各種數(shù)組長(zhǎng)度下簡(jiǎn)單插入排序指令級(jí)功耗
| 數(shù)組長(zhǎng)度 | 指令級(jí)功耗模型估測(cè) | 基于復(fù)雜度的功耗模型估測(cè) | 誤 差 |
| n=10 | 1106.338 | - | - |
| n=20 | 4252.333 | - | - |
| n=40 | 16943.823 | - | - |
| n=80 | 67604.803 | 67924.85 | 0.4% |
4 總結(jié)
本文介紹了一種基于復(fù)雜度的嵌入式軟件功耗模型，以對(duì)象函數(shù)的算法平均復(fù)雜度的建模參數(shù)，利用現(xiàn)有底層指令級(jí)功耗模型對(duì)函數(shù)進(jìn)行分析，回歸出必需的系數(shù)，得到該函數(shù)完整的基于復(fù)雜度的嵌入式軟件功耗模型，從而可快速估算出該函數(shù)在不同輸入情況下的軟件功耗。這種分析方法的缺點(diǎn)在于只適用于算法復(fù)雜度明顯的一些函數(shù)，從而較容易構(gòu)建基于復(fù)雜度的模型。另外在建模過(guò)程中，仍然需要指令級(jí)功耗模型的分析法的協(xié)助。
下載文檔
