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

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

(中國電子科技集團公司第五十八研究所，江蘇 無錫214063)

0 引言

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

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

1.1 CORDIC 算法原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1 指令相對原則

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

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

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

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

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

4.2 加載依賴原則

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

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

4.3 指令依賴原則

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)論

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