基于復(fù)雜度的嵌入式軟件功耗模型

　　摘要：系統(tǒng)功耗是嵌入式系統(tǒng)的一個(gè)重要方向，功耗很大程度上取決于執(zhí)行的軟件。傳統(tǒng)的底層指令級(jí)模型功耗分析方法雖然能比較準(zhǔn)確地估算出嵌入式系統(tǒng)的功耗，但是這種方法所需要的時(shí)間過長。本文介紹一種高層嵌入式軟件功耗分析估測方法，以對(duì)象函數(shù)所使用的算法的復(fù)雜度來對(duì)該函數(shù)構(gòu)建功耗模型，從而根據(jù)此功耗模型能快速估算出該函數(shù)在各種輸入情形下的功耗情況。
　　關(guān)鍵詞：算法復(fù)雜度嵌入式系統(tǒng)軟件功耗模型
　　
　　1嵌入式軟件功耗
　　
　　嵌入式系統(tǒng)的功耗主要來自微處理器的功耗與外圍部件的功耗。雖然能量的水泵最終發(fā)生在底層硬件，但是微處理器的功耗很大程度上取決于其所執(zhí)行的軟件。因此，對(duì)嵌入式系統(tǒng)的功耗分析越來越多地轉(zhuǎn)移到軟件的角度上來，將能量的消耗過程視作軟件執(zhí)行過程。
　　
　　目前的嵌入式軟件功耗分析大多數(shù)都是基于指令級(jí)功耗模型的分析方法。在這種模型中，嵌入式軟件程序的功耗由單條指令的基本功耗開銷、連續(xù)執(zhí)行不同類型的指令造成的功耗開銷以及額外的功耗開銷（如流水線斷流、Cache不命中）等構(gòu)成。雖然這種底層的嵌入式軟件功耗的分析方法的準(zhǔn)確性較高，但是其分析過程需要在特定微處理器平臺(tái)上將程序翻譯成匯編指令，然后通過逐條指令功耗分析和綜合因素考慮，最后才能估算出該程序在某種微處理器上執(zhí)行的系統(tǒng)功能，需要相當(dāng)長的分析時(shí)間。
　　
　　2基于復(fù)雜度的嵌入式軟件功耗模型
　　
　　針對(duì)指令級(jí)功耗模型的瓶頸，本文介紹一種基于復(fù)雜度的嵌入式軟件功耗模型，利用現(xiàn)有條件能快速估算出某函數(shù)的功耗情況。
　　
　　在嵌入式軟件應(yīng)用中大量使用的多媒體計(jì)算和其它數(shù)據(jù)密集型計(jì)算中，經(jīng)常用到諸如查找、排序、矩陣運(yùn)算等算法。由于這些算法的平均復(fù)雜度都是已知的，因此復(fù)雜度成為這些嵌入式軟件程序的一個(gè)重要特征，同樣也能夠成為分析和估測嵌入式軟件功耗的一種重要依據(jù)。基于復(fù)雜度的嵌入式軟件功耗模型以具體函數(shù)所使用的算法的復(fù)雜度為建模的參數(shù)，選取該函數(shù)的典型輸入，并利用現(xiàn)有指令級(jí)模型分析方法獲得該函數(shù)在這些典型輸入情況下的功耗，利用回歸算法出該函數(shù)軟件功耗模型的系數(shù)，從而獲得完事的該函數(shù)軟件功耗模型，并可以用于快速估算該函數(shù)在任何輸入情況下的軟件功耗。
　　
　　在某函數(shù)的算法復(fù)雜度是已知的或較容易獲得的情況下，假設(shè)該函數(shù)的執(zhí)行所需功耗與其復(fù)雜度有關(guān)，則可以使用一個(gè)線性公式來描述該函數(shù)的軟件功耗：
　　
　　
　　
　　其中Pj為模型的參數(shù)與函數(shù)的算法復(fù)雜度與函數(shù)的輸入相關(guān)；cj為相應(yīng)的系數(shù)；p是參數(shù)個(gè)數(shù)。
　　
　　構(gòu)建模型的第一步是決定描述功耗模型的參數(shù)Pj。參數(shù)的選擇與具體的函數(shù)所使用的算法密度相關(guān)。幾種比較常見的算法的功耗模型可以表1中的線性公式來描述。
　　
　　表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ù)矩陣。
　　
　　
　　
　　通過底層指令級(jí)模型分析得到該函數(shù)在每組參數(shù)Ii情況下的功耗。
　　
　　
　　
　　其中然后通過矩陣運(yùn)算即可回歸出參數(shù)向量C。
　　
　　
　　
　　3基于復(fù)雜度的插入排序函數(shù)軟件功耗建模
　　
　　以下將以Integrator/CM7TDMI評(píng)估板的ARM7TDMI微處理器為基礎(chǔ)，對(duì)插入排序函數(shù)來構(gòu)建基于復(fù)雜度的嵌入式軟件功耗模型。
　　
　　假設(shè)某運(yùn)行在ARM7TDMI處理器上的函數(shù)，對(duì)一長度為n的整形數(shù)組a[n]使用簡單插入排序算法進(jìn)行排序。算法的C語言代碼與其經(jīng)過ARMCC編譯器編譯后的匯編代碼如下：
　　
　　voidins_sort(inta[],intn){
　　
　　intx,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_sortPROC
　　
　　STRlr,[sp,#-4]!
　　
　　MOVr3,#1
　　
　　B|L1.56|
　　
　　|L1.12|MOVr2,#0
　　
　　B|L1.44|
　　
　　|L1.20|LDRr12,[r0,r3,LSL#2]
　　
　　LDRlr,[r0,r2,LSL#2]
　　
　　CMPr12,lr
　　
　　STRLTr12,[r0,r2,LSL#2]
　　
　　STRLlr,[r0,r3,LSL#2]
　　
　　ADDr2,r2,#1
　　
　　|L1.44|CMPr2,r3
　　
　　BLT|L1.20|
　　
　　ADDr3,r3,#1
　　
　　|L1.56|CMPr3,r1
　　
　　BLT|L1.12|
　　
　　LDRpc,|sp|,#4
　　
　　3.1基于復(fù)雜度的功耗模型
　　
　　簡單插入排序算法平均復(fù)雜度為O（n2）。該函數(shù)的軟件功耗模型可用如下線性公式描述：
　　
　　
　　
　　其中，n為數(shù)組的長度，E為在輸入數(shù)組長度的n的情況下函數(shù)的功耗。
　　
　　3．2獲得系數(shù)cj
　　
　　在這一步驟中，主要以Integrator/CM7TDMI評(píng)估板的三段流水線、不設(shè)cache的ARM7TDMI處理器的指令級(jí)功耗模型為基礎(chǔ)，分析該插入排序函數(shù)分別在輸入數(shù)組長度n=10、20、40情況下的功耗情況，并通過回歸法獲得系數(shù)cj。
　　
　　在該指令級(jí)功耗模型中，指令執(zhí)行的功耗主要來自兩個(gè)部分：執(zhí)行單條指令引起的功耗（basecost）與連續(xù)執(zhí)行不同類型的指令導(dǎo)致處理器狀態(tài)改變所引起的額外功耗（inter-instructioncost）。其公式如下：
　　
　　
　　
　　其中，Ei為執(zhí)行第I條指令的基本指令功耗（表2），Oij為連續(xù)執(zhí)行第I條和第I指令引起的額外功耗（表3），ε為流水線斷流引起的功耗（表4）。
　　
　　表2Integrator/CM7TDMIARM7TDMI基本指令功耗
　　
　　InstructionE/nJInstructionE/nJADDR2,R0,R10.710KDRR2,[R1,R3]2.774ANDR2,R0,R10.856STRR2,[R1,R3]1.961ORRR2,R0,R10.907MULR2,R0,R12.768ORRSR2,R0,R10.967MLAR2,R0,R1,R03.748MOVR2,R10.935CMPR0,R10.751MOVR0,R00.903SWPR2,R0,[R1]3.917ADDR2,R0,R1,ASRR32.137MRSR2,CPSR0.977Blable3.095MSRCPSR_f,R21.143
　　表3執(zhí)行連接兩條源操作數(shù)類型不同指令的功耗
　　
　　Instr1/Instr2SHIFT_REGSHIFT_IMMREGIMMSHIFT_REG-0.332-0.215-0.232-0.159SHIFT_IMM-0.269-0.177-0.165-0.103REG-9.02E-02-5.98E-02-0.186-0.200IMM-0.141-5.35E-02-9.08E-02-7.53E-02
　　表4流水線斷流引起的功耗
　　
　　InstructiontypeEnergycost/nJAny2.04
　　根據(jù)以上表中的數(shù)據(jù)結(jié)合該函數(shù)匯編指令，得出該插入排序函數(shù)的指令級(jí)功耗分析情況（表5）。
　　
　　表5簡單插入排序指令級(jí)功耗分析
　　
　　指令BasecostIntercostStallcostMOVr3,#10.930--B|L1,56|3.100-0.0752.04MOVr2,#00.930-0.032-B|L1,44|3.100-0.0752.04LDRr12,[r0,r3,LSL#2]3.270-0.032-LDRlr,[r0,r2,LSL#2]3.270-0.177-CMPr12,lr0.830-0.1652.04STRITr12,[r0,r2,LSL#2]2.480-0.060-STRLTlr,[r0,r3,LSL#2]2.480-0.177-CMPr2,r2,#11.590-0.103-CMPr2,r30.830-0.0912.04BLT|L1.20|3.100-0.0602.04ADDr3,r3,#11.590-0.075-CMPr3,r10.830-0.0912.04BLT|L1.12|3.100-0.2002.04
　　
　　
　　至此，可以得出完整的簡單插入排序函數(shù)的基于復(fù)雜度的嵌入式軟件功耗模型
　　
　　E=93.51-5.38n+10.672
　　
　　3.3基于復(fù)雜度的嵌入式軟件功耗模型的估算功耗
　　
　　當(dāng)輸入數(shù)組長度為n=80的情況下，通過該模型可快速估算出插入排序函數(shù)的功耗
　　
　　E=93.51-5.38×80+10.67×1600=67924.85(nJ)
　　
　　與指令級(jí)功耗模型的估測值誤差小于1%（表6），而利用基于復(fù)雜度的功耗模型估測該函數(shù)執(zhí)行所需的功耗的速度而大大提高。
　　
　　表6各種數(shù)組長度下簡單插入排序指令級(jí)功耗
　　
　　數(shù)組長度指令級(jí)功耗模型估測基于復(fù)雜度的功耗模型估測誤差n=101106.338--n=204252.333--n=4016943.823--n=8067604.80367924.850.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ù)雜度的模型。另外在建模過程中，仍然需要指令級(jí)功耗模型的分析法的協(xié)助。
　　
　　
　　
　　

【基于復(fù)雜度的嵌入式軟件功耗模型】相關(guān)文章：

基于模塊化設(shè)計(jì)的嵌入式軟件測試方法08-06

基于嵌入式Linux的BACnet控制器軟件設(shè)計(jì)08-06

嵌入式Linux下基于MiniGUI的信息終端軟件開發(fā)08-06

嵌入式系統(tǒng)面向低功耗的協(xié)同設(shè)計(jì)08-06

基于MSP430的極低功耗系統(tǒng)設(shè)計(jì)08-06

CIMS環(huán)境下基于特征的產(chǎn)品模型08-06

基于DSP的Bluetooth嵌入式系統(tǒng)應(yīng)用08-06

基于Web的嵌入式設(shè)備管理08-06

基于橢圓曲線的嵌入式文件加密08-06