基于PowerPC 架構(gòu)的波束指向算法的優(yōu)化

雷淑嵐，吳會(huì)祥，李文學(xué)

(中國(guó)電子科技集團(tuán)公司第五十八研究所，江蘇 無(wú)錫214063)

0 引言

波束指向算法主要完成在已知衛(wèi)星大地坐標(biāo)系的經(jīng)度、緯度、高度(long、lati、heig)，無(wú)人機(jī)大地系坐標(biāo)系的經(jīng)度、緯度、高度(long、lati、heig)，飛機(jī)俯仰角、橫滾角、航向角(p、r、y)的情況下，天線陣面中心在機(jī)體直角坐標(biāo)系中的位置(Xb、Yb、Zb)，計(jì)算衛(wèi)星在天線球坐標(biāo)系中的方位角、俯仰角(θ、φ)，從而進(jìn)行收發(fā)天線的波束對(duì)準(zhǔn)[1]。 本文主要是基于PowerPC460 架構(gòu)處理器對(duì)波束指向算法進(jìn)行合理的優(yōu)化，以期在算法的實(shí)時(shí)性處理上有所優(yōu)化。 本文從四個(gè)方面對(duì)波束指向算法進(jìn)行優(yōu)化：(1)基于CORDIC 算法設(shè)計(jì)的硬件電路實(shí)現(xiàn)三角函數(shù)的速算優(yōu)化；(2)浮點(diǎn)數(shù)運(yùn)算的優(yōu)化；(3)循環(huán)嵌套優(yōu)化；(4)基于PowerPC 指令集的優(yōu)化。

1 基于CORDIC 算法設(shè)計(jì)的硬件電路實(shí)現(xiàn)三角函數(shù)的速算優(yōu)化

1.1 CORDIC 算法原理

在傳統(tǒng)的硬件算法設(shè)計(jì)中，乘、除等基本數(shù)學(xué)函數(shù)運(yùn)算是一種既耗時(shí)又占用面積大的運(yùn)算，甚至有時(shí)是難以實(shí)現(xiàn)的，CORDIC 算法正是為解決這種問題而產(chǎn)生的。它從算法本身入手，將其分解成為一些簡(jiǎn)單的且在硬件中容易實(shí)現(xiàn)的基本算法，如加法、移位等，因此使得這些算法在硬件上可以得到較好的實(shí)現(xiàn)。 又由于該算法是一種規(guī)則化的算法，它滿足了硬件對(duì)算法的模塊化、規(guī)則化的要求，因此CORDIC 算法可以充分發(fā)揮硬件的優(yōu)勢(shì)[2-3]。 利用硬件的資源，從而實(shí)現(xiàn)硬件與算法相結(jié)合的一種優(yōu)化方案，正是由于上述原因，CORDIC 算法的原始思想一經(jīng)提出，就受到了人們的普遍關(guān)注，40年來(lái)人們不斷地對(duì)其進(jìn)行探索研究，并提出了各種改進(jìn)算法和優(yōu)化方案以適應(yīng)各種不同的需求[4-11]。

在處理數(shù)字信號(hào)過程中，由于三角函數(shù)發(fā)生器在高速和高精度方面特點(diǎn)使得其有著較為廣泛的使用范圍。而相對(duì)于傳統(tǒng)的方法實(shí)現(xiàn)多為采用查表、多項(xiàng)式展開或近似的方法[12-14]，但是帶來(lái)問題是速度、精度、簡(jiǎn)單性和高效方面做的不好。 而用CORDIC 算法實(shí)現(xiàn)的三角函數(shù)發(fā)生器能很好地兼顧這幾個(gè)方面，因此對(duì)于VLSI 的實(shí)現(xiàn)就顯得非常適合[15]。 下面簡(jiǎn)要介紹一下CORDIC 算法的計(jì)算流程。

CORDIC 算法是一種迭代的算法，把所需旋轉(zhuǎn)的角度分解成N 步去完成，每一步的迭代方程如下：

迭代次數(shù)一般人為控制，限制范圍是Zn足夠小，精度已經(jīng)達(dá)標(biāo)。

迭代完成后的方程可以表示為：

其中P(N)是每一步迭代中提出項(xiàng)cosθN的累積值，求極限可以得到這個(gè)累計(jì)值是P(N)≈0.607 253，若取X0=1/P(N)，Y0=0，A=θ，則從上式可以推出：

1.2 CORDIC 算法可以用以下兩種硬件結(jié)構(gòu)來(lái)實(shí)現(xiàn)

CORDIC 算法的最簡(jiǎn)單最容易想到的實(shí)現(xiàn)方式是反饋結(jié)構(gòu)。 這種結(jié)構(gòu)只設(shè)計(jì)一級(jí)流水，將系統(tǒng)輸出反饋到輸入進(jìn)行迭代運(yùn)算。迭代次數(shù)和移位位數(shù)通過控制命令來(lái)實(shí)現(xiàn)。 這種結(jié)構(gòu)硬件開銷比較小，但可想而知比較耗時(shí)，在實(shí)時(shí)性要求很高的系統(tǒng)上，比如衛(wèi)星導(dǎo)航系統(tǒng)，就不太合適了。

第二種可能實(shí)現(xiàn)的結(jié)構(gòu)是流水線型。 這種流水線的思想主要是為了滿足實(shí)時(shí)性的要求。每一級(jí)迭代都是一級(jí)流水線，移位的位數(shù)等于本級(jí)流水線的級(jí)數(shù)，順時(shí)針還是逆時(shí)針可以通過Zn的最高位來(lái)判斷，0 的時(shí)候是順時(shí)針，1 的時(shí)候表示逆時(shí)針。 每一級(jí)迭代的結(jié)果就是下一級(jí)流水線的輸入。進(jìn)過N 級(jí)流水線后的輸出結(jié)果：Zn=0(滿足精度要求的情況下，趨向于0)，X 和Y 的值就是輸入的旋轉(zhuǎn)角度的正弦值和余弦值。

如果選擇迭代15 次，則硬件上需要設(shè)計(jì)一個(gè)16 級(jí)流水線的結(jié)構(gòu)，字長(zhǎng)是19 bit，最高位為符號(hào)位，i 的初始值是1。 流水線結(jié)構(gòu)可以設(shè)計(jì)成如圖1 所示。

圖1 CORDIC 流水線結(jié)構(gòu)

由于在波束指向的算法處理中，坐標(biāo)系之間的變換最常見的運(yùn)算就是正弦函數(shù)和余弦函數(shù)的計(jì)算，傳統(tǒng)的計(jì)算方式用的是冪級(jí)數(shù)展開的方式，是基于純軟件的運(yùn)算，如果可以使用上述的流水線硬件結(jié)構(gòu)來(lái)計(jì)算正弦值和余弦值，那算法處理的速度將會(huì)大大提高。

2 運(yùn)算浮點(diǎn)數(shù)的變型和位數(shù)的控制

對(duì)浮點(diǎn)數(shù)而言，波束指向算法要求達(dá)到的精度是小數(shù)點(diǎn)后三位， 單精度浮點(diǎn)數(shù)小數(shù)點(diǎn)后有效數(shù)字是6～7位，雙精度浮點(diǎn)數(shù)小數(shù)點(diǎn)后有效數(shù)字是15～16 位，所以運(yùn)算過程中，使用單精度型浮點(diǎn)數(shù)已經(jīng)可以達(dá)到要求。對(duì)于在算法中出現(xiàn)的浮點(diǎn)數(shù)的乘除運(yùn)算，可以將浮點(diǎn)數(shù)轉(zhuǎn)換成整型數(shù)進(jìn)行計(jì)算，以提高運(yùn)算速度。 計(jì)算出結(jié)果后再通過反向移位還原到正確結(jié)果。 舉例說(shuō)明如下：

俯仰角一般是單精度型的浮點(diǎn)數(shù)，有效位數(shù)在小數(shù)點(diǎn)后三位，那么在運(yùn)算之前可以將pitch 乘以1 000，化成整型數(shù)再進(jìn)行計(jì)算。 在計(jì)算完成之后，運(yùn)算結(jié)果再除以1 000。 整型數(shù)的計(jì)算比浮點(diǎn)數(shù)運(yùn)算要快得多。

3 循環(huán)嵌套優(yōu)化

循環(huán)嵌套優(yōu)化是將具有相同循環(huán)變量和循環(huán)次數(shù)的循環(huán)體嵌套，在一個(gè)循環(huán)里完成循環(huán)，這樣可以大大減少因循環(huán)占用的時(shí)間消耗，舉個(gè)例子如下所示：

優(yōu)化前找到滿足條件的航向角和橫滾角需要2×9個(gè)循環(huán)，優(yōu)化后只需要一半的循環(huán)次數(shù)就找到了滿足要求的航向角和橫滾角。

4 基于PowerPC 指令集的優(yōu)化

基于PowerPC 體系的CPU 種類很多，優(yōu)化也是建立在對(duì)環(huán)境很了解的基礎(chǔ)上。 比如基于CORDIC 算法設(shè)計(jì)的硬件電路如果選擇第二種流水線結(jié)構(gòu)，習(xí)慣上，主頻越高，流水線越長(zhǎng)，速度就越快，處理性能也越好，但在PowerPC 的環(huán)境下，流水線的長(zhǎng)度和分支預(yù)測(cè)失誤代價(jià)是成正比的，單條指令執(zhí)行效率也會(huì)隨之降低。 CPU 一般根據(jù)應(yīng)用場(chǎng)合不同采取不同的優(yōu)化策略：科學(xué)性計(jì)算機(jī)、商務(wù)型計(jì)算機(jī)和多媒體型計(jì)算機(jī)。 而對(duì)于科學(xué)性計(jì)算機(jī)來(lái)說(shuō)，采用的是小而密集的循環(huán)計(jì)算。 應(yīng)用場(chǎng)合不同，優(yōu)化策略也不同。 PowerPC460 內(nèi)核的體系是短流水線型，主頻雖然低，但處理速度卻驚人。下面從四個(gè)方面來(lái)闡述指令優(yōu)化的原則和方法。

4.1 指令相對(duì)原則

PowerPC 的環(huán)境下有三種指令的類型，PowerPC 的系統(tǒng)能夠在一個(gè)周期內(nèi)執(zhí)行完兩種不同類型的指令：

(1)加載或存儲(chǔ)數(shù)據(jù)的指令；

(2)設(shè)置CR 寄存器進(jìn)行比較，分支，乘除SPR 寄存器更新；

(3)其他種類操作：非SPR/CR 寄存器更改，算術(shù)與邏輯。

PowerPC 體系下對(duì)指令執(zhí)行的這個(gè)原則就使得如果相鄰兩條指令是同一類型，第二條就必須要等到第一條執(zhí)行結(jié)束才能執(zhí)行，這樣就浪費(fèi)了一個(gè)時(shí)鐘周期，所以在寫匯編語(yǔ)句的時(shí)候，就要注意把兩條相同類型的語(yǔ)句隔開，以達(dá)到最大的執(zhí)行效率。 在某些體系的流水線結(jié)構(gòu)中，相鄰兩條語(yǔ)句如果是無(wú)依賴的代碼都可以并行執(zhí)行，但在PowerPC 的體系下，無(wú)依賴的指令若屬于同一類型，仍然不能并行執(zhí)行。舉個(gè)例子，整數(shù)計(jì)算指令屬于同一類型，載入指令屬于同一類型，如下語(yǔ)句混合寫才最有效率：

4.2 加載依賴原則

PowerPC 體系下，數(shù)據(jù)從緩存中被加載到寄存器里再到被其他語(yǔ)句調(diào)度，至少需要等兩個(gè)周期，也就是說(shuō)在加載數(shù)據(jù)到寄存器后，第三個(gè)時(shí)鐘周期才能使用該寄存器里的數(shù)據(jù)，這樣就可以利用中間兩個(gè)周期的真空期做一些優(yōu)化。 根據(jù)第一個(gè)指令相對(duì)原則，兩條不同類型的指令可以在同一個(gè)時(shí)鐘周期內(nèi)被執(zhí)行完成。 這樣，在這段真空期里，就可以放置最多5 條指令。 在實(shí)際使用中，具體能放置的指令數(shù)同樣取決于這些指令類型的混合順序，最少也能放置兩條指令。

有一些具有更新功能的加載指令，比如lwzu 這個(gè)指令，這個(gè)指令不但能加載數(shù)據(jù)到目標(biāo)寄存器，同時(shí)也能更新源寄存器。所以，在使用這個(gè)指令的時(shí)候，要等到兩個(gè)周期后才能對(duì)源寄存器里的數(shù)據(jù)進(jìn)行調(diào)度。

4.3 指令依賴原則

如果兩條指令有上下文的依賴關(guān)系，那這兩條指令就不能在同一個(gè)時(shí)鐘周期內(nèi)被調(diào)度，也就是說(shuō)，如果第一條指令調(diào)度的寄存器被第二條指令使用了，那第二條指令一定會(huì)在第一條指令執(zhí)行完成后才能被執(zhí)行，這樣，就可以在兩條指令中間放置一條指令來(lái)填補(bǔ)這個(gè)時(shí)間差。

舉個(gè)例子來(lái)說(shuō)，周期k 內(nèi)，執(zhí)行了add r4，r5，r6 這個(gè)語(yǔ)句，這個(gè)語(yǔ)句里更新了r4 寄存器，那在周期k 內(nèi)，就不能再執(zhí)行任何與r4 寄存器有數(shù)據(jù)交換的動(dòng)作，比如srawi r7，r4，4 指令，必須要等到k+1 周期內(nèi)才能被執(zhí)行，這樣就可以在兩條指令中間添加一句lwz r3，0(r10)語(yǔ)句，就可以把這個(gè)時(shí)間差填補(bǔ)了，這樣程序執(zhí)行起來(lái)更有效率。

4.4 緩存優(yōu)化原則

CPU 在從主存里取數(shù)的時(shí)候，工作原理是先把主存加載到緩存中，然后在緩存里對(duì)數(shù)據(jù)進(jìn)行處理，最后才把數(shù)據(jù)更新到主存里。 根據(jù)加載依賴原則可以得知，數(shù)據(jù)從緩存中加載到寄存器里需要等待三個(gè)周期才能被再次調(diào)度，也就是說(shuō)如果CPU 想使用某個(gè)主存地址里的數(shù)據(jù)， 那它就要先把主存地址里的數(shù)據(jù)加載到緩存，然后才能把緩存里的數(shù)據(jù)加載到寄存器里，這樣等待周期就超過了三個(gè)周期。 所以，現(xiàn)在的PowerPC 體系為了減少?gòu)耐獯婕虞d到緩存的時(shí)間，都使用了一個(gè)DCBT(Data Cache Block Touch)的指令：

DCBT rA,rB： 將rA 和rB 地址里的數(shù)據(jù)預(yù)先存儲(chǔ)到緩存里。

這個(gè)指令的作用是提前告訴CPU 程序要使用哪塊內(nèi)空間的數(shù)據(jù)，CPU 先把這塊數(shù)據(jù)加載到緩存里，過段時(shí)間等用到這個(gè)數(shù)據(jù)的時(shí)候，就不用再浪費(fèi)時(shí)間從內(nèi)存里加載到緩存上。

舉個(gè)例子來(lái)總結(jié)一下PowerPC 體系下上述幾個(gè)優(yōu)化原則的使用，如下所示：

上述代碼使用到的三種優(yōu)化是：

(1)緩存預(yù)讀??；

(2)多寄存器并行使用；

(3)非同類型指令同周期執(zhí)行達(dá)到并行處理的效率。

在波束指向算法中，C 代碼的執(zhí)行效率不如匯編語(yǔ)言高，但在滿足實(shí)時(shí)性要求的基礎(chǔ)上，并不需要對(duì)通篇代碼進(jìn)行匯編改寫，這里選取C 代碼里耗時(shí)最長(zhǎng)的天線選擇函數(shù)進(jìn)行匯編改寫， 并使用上述指令集的優(yōu)化原則，以期達(dá)到最高的執(zhí)行效率。因代碼過長(zhǎng)，現(xiàn)提取部分代碼如下所示：

# 找到旋轉(zhuǎn)俯仰角最小的天線編號(hào)

5 優(yōu)化結(jié)果分析

在50 MHz 時(shí)鐘頻率的JS71232 芯片環(huán)境下，編譯優(yōu)化等級(jí)選擇-O2，通過在程序里添加set_time_base(0，0)和get_time_base(&Tbu，&Tbl)的指令，來(lái)測(cè)試程序的運(yùn)行的時(shí)鐘周期。表1 是不使用優(yōu)化的程序?qū)崪y(cè)時(shí)間和使用各種類型優(yōu)化的實(shí)測(cè)時(shí)間，已將耗時(shí)轉(zhuǎn)換成以毫秒(ms)為單位的計(jì)時(shí)。

表1 優(yōu)化結(jié)果顯示

從實(shí)測(cè)結(jié)果上來(lái)看，使用三角函數(shù)速算算法設(shè)計(jì)的硬件電路對(duì)程序執(zhí)行效率提高最明顯，循環(huán)嵌套優(yōu)化由于循環(huán)使用次數(shù)的原因，并未對(duì)程序處理提高太多效率。指令集的優(yōu)化是建立在匯編語(yǔ)言的基礎(chǔ)上，在滿足處理實(shí)時(shí)性的前提下，可以適當(dāng)使用指令集優(yōu)化。 波束指向算法在衛(wèi)星導(dǎo)航的平臺(tái)上應(yīng)用時(shí)，慣導(dǎo)周期在10 ms 到150 ms 之間，由INS 性能和指向類型決定。 在PowerPC的環(huán)境下，使用以上四種優(yōu)化，已經(jīng)滿足絕大多數(shù)類型的波束指向的實(shí)時(shí)性的要求。

6 結(jié)論

本文在PowerPC 架構(gòu)下提出了一種針對(duì)波束指向算法的優(yōu)化策略，將算法處理的時(shí)間減少到1/10 左右，一方面，將CORDIC 旋轉(zhuǎn)算法應(yīng)用在波束指向算法中，在數(shù)學(xué)函數(shù)層面對(duì)系統(tǒng)實(shí)時(shí)性上提供了優(yōu)化的空間，另一方面，PowerPC 本身的架構(gòu)為波束指向算法的優(yōu)化提供了可能性。 同時(shí)為PowerPC 平臺(tái)的應(yīng)用提供了一個(gè)很好的優(yōu)化思路，指令集上的優(yōu)化策略同樣適用于所有基于PowerPC 平臺(tái)的應(yīng)用開發(fā)。 此外，基于CORDIC 算法的設(shè)計(jì)的硬件電路在芯片開發(fā)領(lǐng)域有很強(qiáng)的使用價(jià)值，打破了將復(fù)雜數(shù)學(xué)函數(shù)計(jì)算的負(fù)擔(dān)交給純軟件來(lái)實(shí)現(xiàn)的傳統(tǒng)。本論文提出的所有優(yōu)化策略對(duì)其他平臺(tái)的算法開發(fā)和算法優(yōu)化也有一定的借鑒價(jià)值。