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