新聞中心

EEPW首頁 > 嵌入式系統(tǒng) > 設(shè)計應(yīng)用 > 基于ARM的除法運算優(yōu)化策略

基于ARM的除法運算優(yōu)化策略

作者: 時間:2007-02-06 來源:網(wǎng)絡(luò) 收藏
與傳統(tǒng)的48位單片機相比,的性能和處理能力是遙遙領(lǐng)先的。但與之相應(yīng),的系統(tǒng)設(shè)計復(fù)雜度和難度,較之傳統(tǒng)的設(shè)計方法也大大提升了,同時也大大拓展了針對芯片特性進(jìn)行的空間,例如針對指令流水線的、針對寄存器分配進(jìn)行的等。


ARM
在硬件上不支持指令,編譯器是通過調(diào)用C庫函數(shù)來實現(xiàn)的,有許多不同類型的程序來適應(yīng)不同的除數(shù)和被除數(shù)。但直接利用C庫函數(shù)中的標(biāo)準(zhǔn)整數(shù)除法程序,根據(jù)執(zhí)行情況和輸入操作數(shù)的范圍,要花費20100個周期,消耗較多的軟件運行時間。在實時嵌入式應(yīng)用中,對時間參數(shù)較為敏感,故可以考慮如何優(yōu)化避免除法消耗過多的CPU運行時間。


除法和模
(/和%)執(zhí)行起來比較慢,所以應(yīng)盡量避免使用。但是,除數(shù)是常數(shù)的除法和用同一個除數(shù)的重復(fù)除法,執(zhí)行效率會比較高。在ARM中,可以利用單條MUL指令實現(xiàn)乘法操作。本文將闡述如何用乘法運算代替除法運算,以及如何使除法的次數(shù)最少化。

 

1 避免除法運算

在非嵌入式領(lǐng)域,因為CPU運算速度快、存儲器容量大,除法操作通常都是不加考慮直接使用的。但在嵌入式領(lǐng)域,首先需要考慮的是這些除法操作是否是必須的。以對環(huán)形緩沖區(qū)操作為例,經(jīng)常要用到除法,其實完全可以避免這些除法運算。


假定有一個buffer_size大小的環(huán)形緩沖區(qū),如圖1所示,0ffset指定目前所在的位置。通過increment字節(jié)來增加offset的值,一般是這樣寫的:

0ffset=(Offset+increment)buffer_size


效率更高的寫法是:

offset+=increment;

if(offset>=buffer_size){

offset=buffer_size;

}


第一種寫法要花費50個周期,而第二種因為沒有除法運算,只須花費3個周期。這里假定incrementbuff_er_size,在實際應(yīng)用中這點應(yīng)該是保證的。


如果不能避免除法運算,那么就應(yīng)盡量使除數(shù)和被除數(shù)是無符號的整數(shù)。有符號的除法程序執(zhí)行起來更加慢,因為它們先要取得除數(shù)和被除數(shù)的絕對值,再調(diào)用無符號除法運算,最后再確定結(jié)果的符號。

 

2 充分利用商和余數(shù)

許多C語言庫中的除法函數(shù)返回商和余數(shù)。換句話說,每一個除法運算,余數(shù)是可以無償?shù)玫降?,反之亦然。例如,要在屏幕緩沖區(qū)找到偏移量為offset的屏幕位置(x,y),可以這樣寫:

typeclef struct{

int x;

int y;

}point;

point getxy_v1(unsigned int offset,unslgned int bytes_per_line){

point p;

py=offsetlt)ytes_per_line;

px=offset - py* bytcs_per_line;

return p

}

 

這里,似乎對px使用減法和乘法,少了一次除法運算;但是,實際上使用模運算或者取余操作效率更高,對

getxy_vl改進(jìn)如下:

point getxy_v2(unsigned int offset,unsigned int bytes_per_line){

point P

Px=offsetbytes_per_1ine;

Py=offsetbytes_per_line

return P;


從下面編譯器的輸出結(jié)果可以看到,只有一次除法調(diào)用。實際上,這個程序要比前面的getxy_vl4條指令(注意,并不是對所有的編譯器和C庫都有這樣的結(jié)果)。getxy_v2

STMFD r13!{r4,r14};保存r4,lr人堆棧

MOV r4rO ;賦值后r4保存的為點P基址

MOV rO,r2 ;rO=bytes_per_line

BL rt_udiv ;調(diào)用無符號除法例程

(r0.;r1)=(rlrOrlrO)

STR r0,[r4,#4] ;Py=offsetbytes_per_line

STR rl,[r4,#o] ;Px=offset%bytes_per_line

LDMFD r13!,(r4,pc);恢復(fù)上下文,返回

 

3 把除法轉(zhuǎn)換為乘法

在程序中,同一個除數(shù)的除法經(jīng)常會出現(xiàn)很多次。在前面的例子中,bytes_per_line的值在整個程序中都是固定不變的。又如32笛卡爾坐標(biāo)變換,其中就使用了同一個除數(shù)兩次:

(x,Y,x)(xz,yz)


這種情況下,使用cache指令中的值1z,并使用1z的乘法來代替除法運算,效率會更高。另外,要盡可能使用int類型的運算,避免使用浮點運算。


下面將更加偏重于從數(shù)學(xué)和理論的角度分析,把重復(fù)除法轉(zhuǎn)換成乘法運算。


下面來區(qū)分精確數(shù)學(xué)意義上的除法和整型除法運算:

nd,即整數(shù)n被分成整數(shù)d份,結(jié)果趨向于O(C語言相同);

nd,即nd除之后的余數(shù),就是n--d(nd);

◇n/d=nd-1,即真正數(shù)學(xué)意義上的nd除。


當(dāng)使用整型除法時,最容易估算
d-1值的方法是計算232d。然后,就可以估算nd為:

(n(232d))232 (1)


在執(zhí)行
n的乘法時,需要精確到64位。對于這種方法,會出現(xiàn)如下問題:

◇為了計算232d,由于一個unsigned int類型的數(shù)據(jù)放不下232,編譯器要使用64long long類型的數(shù),而且必須指定除法為(1 ull32)d。這種64位的除法比32位的除法執(zhí)行起來要慢得多。

◇如果d碰巧是1,那么232d就不再適合于unsigned int數(shù)據(jù)類型。


上面的做法似乎很好,而且解決了這兩個問題。那么,再來看一下用
(2321)d代替232d

s=0xffffffff uld (2)


以上
nd-2,qnd+1為整數(shù)值,所以可得q=ndq=(nd)1,即初步估計的結(jié)果q與正確值nd有可能存在偏差1??梢园l(fā)現(xiàn),通過計算余數(shù)r=nqd(Or2d)是比較容易的。下面的代碼糾正了這個結(jié)果:

r=n--q*d;*初步估計結(jié)果余數(shù)r的范圍為Or2d*

if(r>=d){*若需要校正*

r-=d;/*校正r,使Ord為正確余數(shù)范圍*

n++;*相應(yīng)商加1進(jìn)行校正*

} *得正確結(jié)果q=ndr=nd*


下面給出一個實例,用上面的算法完成了
N個元素的數(shù)組被d除。首先,計算上面所說的s值,然后用乘以5來代替每個被d除的除法。64位的乘是很容易實現(xiàn)的,因為ARM中有一條指令UMULL,可以進(jìn)行232位數(shù)相乘,給出一個64位的結(jié)果。

void scale(

unsigned int*dest *目的數(shù)據(jù)*

unsigned int*src; *源數(shù)據(jù)*

unsignedInt d; *分母d*

urlslglaedInt N;) *數(shù)據(jù)長度*

{

unsigned int s=0xFFFFFFFFud

do{

unsigned int n,q,r;

n=*(src++);

q=(urtslgrted int)(((unsined tong long)n*s)>>32);

r=n*d;

if(r>=d){ *若需要對商進(jìn)行校正*

q++;

}

*(dest++)=q;

}while(一一N)

}


這里假定除數(shù)和被除數(shù)都是
32位的無符號整數(shù)。當(dāng)然,使用32位乘法進(jìn)行16位的無符號數(shù)計算,或者使用1 28位乘法進(jìn)行64位數(shù)計算,運算規(guī)則是一樣的。可以為特定的數(shù)據(jù)選擇最窄的運算寬度。如果數(shù)據(jù)是16位的,那么就設(shè)置s=(2161)/d,然后用標(biāo)準(zhǔn)的整型乘法來求值q

 

4 結(jié)

在嵌入式軟件編程中,為了節(jié)省CPU運行時間,應(yīng)盡可能避免使用除法。對環(huán)形緩沖區(qū)的處理可以不用除法。如果不能避免除法運算,那么應(yīng)盡可能使用除法程序同時產(chǎn)生商nd和余數(shù)nd的好處。對于重復(fù)對一除數(shù)d的除法.預(yù)先計算好s=(2k1)d,用乘以s2k位乘法來代替除以dk位無符號整數(shù)除法,可大大減少由于直接使用除法操作引入的指令周期數(shù)。

c++相關(guān)文章:c++教程


絕對值編碼器相關(guān)文章:絕對值編碼器原理


關(guān)鍵詞: 優(yōu)化 策略 運算 除法 ARM 基于

評論


相關(guān)推薦

技術(shù)專區(qū)

關(guān)閉