孔璽暢,文 梅,藍(lán) 強(qiáng)

(1.國防科技大學(xué)計算機(jī)學(xué)院，湖南 長沙 410073;2.國防科技大學(xué)氣象海洋學(xué)院，湖南 長沙 410073)

1 引言

合成孔徑雷達(dá)SAR(Synthetic Aperture Radar)是一種主動式的對地觀測系統(tǒng)，可安裝在飛機(jī)、衛(wèi)星和宇宙飛船等飛行平臺上，全天時、全天候?qū)Φ貙嵤┯^測，且具有一定的地表穿透能力。因此，SAR系統(tǒng)在災(zāi)害監(jiān)測、環(huán)境監(jiān)測、海洋監(jiān)測、資源勘查、農(nóng)作物估產(chǎn)、測繪和軍事等方面的應(yīng)用具有獨特的優(yōu)勢，可發(fā)揮其他遙感手段難以發(fā)揮的作用，因此越來越受到世界各國的重視[1]。

SAR最初是搭載在人造衛(wèi)星上，隨著科技的發(fā)展和需求的多樣化，地基SAR在過去幾年也扮演著主要角色。而SAR的未來正朝著多平臺化的方向發(fā)展。

SAR成像的運算量很大，且對時效性有限制。以往傳統(tǒng)的地面設(shè)備進(jìn)行數(shù)據(jù)接收和SAR成像處理有著充足的電力和算力支持[2]，但隨著嵌入式芯片上(on-board)計算的需求日益凸顯，因為其特殊的運行平臺，對高性能和低能耗有特定需求。如何針對特定平臺提供高性能、低功耗的應(yīng)用支持，便成為了其核心要點。

SAR成像的核心是快速傅里葉變換FFT(Fast Fourier Transform)，它已經(jīng)發(fā)展得很成熟。在x86平臺的MKL(Math Kernel Library)庫中，對快速傅里葉變換功能有很好的優(yōu)化支持，因此在x86平臺上使用MKL庫的SAR成像模擬實驗可以作為一個重要的性能參考。

以往的SAR成像應(yīng)用優(yōu)化的研究，一般以基于GPU的運行作為基本方向[3]，或針對固定程序進(jìn)行硬件定制，不具有可編程靈活性。

本文面向異構(gòu)加速器針對算力分配問題構(gòu)建了算力配比模型。依據(jù)最優(yōu)算力配比，一方面可以指導(dǎo)高能效硬件設(shè)計；另一方面在固定硬件下，可以指導(dǎo)不同SAR成像應(yīng)用中能效最優(yōu)的運行配置。針對SAR成像應(yīng)用的特征及其性能瓶頸，提出了隱式轉(zhuǎn)置的優(yōu)化方法和緩存結(jié)構(gòu)優(yōu)化設(shè)計，可以顯著降低SAR成像應(yīng)用中轉(zhuǎn)置占用的大量時間開銷。

2 SAR成像程序分析

2.1 SAR成像程序的運行模式

SAR成像算法有許多版本，根據(jù)不同的運行環(huán)境，不同的應(yīng)用需求，成像算法也會有一些變化，但是成像算法的基本運算模式大體都是一致的，如圖1所示。

Figure 1 Two basic calculation kernels

圖1顯示了2種基本運算模式，本文把執(zhí)行這種模式的函數(shù)稱為一個Kernel。Kernel之間、Kernel內(nèi)部按需求會對矩陣進(jìn)行轉(zhuǎn)置。根據(jù)算法計算過程，算法中可能會出現(xiàn)矩陣的鏡像翻轉(zhuǎn)變換，為了方便討論，把傳統(tǒng)的矩陣轉(zhuǎn)置和矩陣的鏡像翻轉(zhuǎn)統(tǒng)稱為轉(zhuǎn)置，下文中所有轉(zhuǎn)置都是這類訪存密集型變換的統(tǒng)稱。

圖1中FFT指快速傅里葉變換，IFFT (Inverse Fast Fourier Transform) 指快速傅里葉逆變換。矩陣的點運算在這里指同一個矩陣內(nèi)部的點與點之間不產(chǎn)生依賴關(guān)系，運算規(guī)模為一個矩陣，是具有高并行性的一類運算。

插值運算主要是sinc插值，它是一種stencil領(lǐng)域運算。插值運算的結(jié)果矩陣內(nèi)部的點與點之間也不存在依賴關(guān)系，即結(jié)果矩陣中每個點的運算結(jié)果不依賴另一個點的運算結(jié)果。因此，對于先算哪個點后算哪個點沒有要求，有著良好的并行性。

本文主要針對如圖2所示的Range-Doppler[4]經(jīng)典算法流程展開對計算、訪存行為的分析，并以此構(gòu)建一個算力配比的數(shù)學(xué)模型，展開硬件結(jié)構(gòu)設(shè)計空間探討。

Figure 2 An example of SAR imaging process using Range-Doppler algorithm

2.2 SAR成像的計算特征分析

SAR成像的計算量主要集中在FFT/IFFT、矩陣的點運算和插值運算。

設(shè)矩陣的規(guī)模為N*M，對于FFT/IFFT，目前主流的算法為分治算法，其計算復(fù)雜度為O(N*log2N)，對矩陣逐行進(jìn)行FFT/IFFT的總復(fù)雜度為O(N*M*log2M)，逐列進(jìn)行FFT/IFFT的總復(fù)雜度為O(M*N*log2N)。對于矩陣的點運算，計算總復(fù)雜度為O(N*M)。

插值運算目前有多種算法[5]，應(yīng)用最廣的為sinc插值[6]，使用了多個相鄰點的信息，通常這個數(shù)值設(shè)為8，稱為8點sinc插值。該數(shù)值與計算精度有關(guān)，為了獲得更高精度數(shù)據(jù)，可選擇16點sinc插值，若不需要高精度，可選擇4點sinc插值。設(shè)相鄰點數(shù)量為k，則總計算復(fù)雜度為O(k*N*M)。表1列出了8K*8K的float_complex矩陣完成各類運算的理論運算量。

Table 1 Calculation amount of each function

嚴(yán)格意義上，F(xiàn)FT/IFFT處理的數(shù)據(jù)規(guī)模是一行(列)，為了方便比較各函數(shù)間整體運算量的關(guān)系，這里的FFT是指對整個矩陣逐行(列)進(jìn)行FFT/IFFT。

需要注意，在同一個SAR成像程序的不同位置，點運算之間也可能存在運算量差別。點運算和與點運算相鄰的運算(如果點運算相鄰的運算也是點運算，那么將兩者合并處理)之間運算量的差異會影響3.2節(jié)的最優(yōu)算力配比，解決此問題的方法也會在3.3節(jié)中進(jìn)行討論。

這里的插值運算以8點sinc插值為例，sinc運算的運算量以7階代數(shù)逼近法[6]計算得出。

2.3 SAR成像的訪存特征分析

SAR成像的訪存操作主要集中在2個部分：轉(zhuǎn)置變換和FFT/IFFT。

在轉(zhuǎn)置運算中，因為寫數(shù)據(jù)在內(nèi)存中的地址不連續(xù)，而矩陣點運算與插值運算中都是順序讀寫，所以在同樣的數(shù)據(jù)規(guī)模(O(N*M))訪存量的情況下，轉(zhuǎn)置性能會下降。

對于FFT/IFFT，因為其采用分治算法，存在O(N*M*log2M)(行序)或O(M*N*log2N)(列序)復(fù)雜度的訪存開銷，其訪存行為為順序讀寫。表2列出了8K*8K的float_complex矩陣完成各類運算的理論訪存量。

Table 2 Memory access amount of each function

2.4 瓶頸分析

通常將FFT/IFFT運算歸類為計算訪存參半的運算，其性能同時受限于算力和帶寬[7]。高算力并行運算時，由于訪存瓶頸導(dǎo)致速度受限十分明顯。

矩陣點運算和插值運算中，訪存行為為順序讀寫，相對于計算來說速度非?？?，總體特征是計算占主導(dǎo)。需要注意的是，在計算量不大時，多核并行帶來的速度提升不是嚴(yán)格的線性提升。其原因不只是訪存受限，還有循環(huán)本身存在時間開銷，其隨多核并行帶來的速度提升并非線性，應(yīng)該針對循環(huán)方式進(jìn)行分塊優(yōu)化[8]。只有當(dāng)計算中帶有例如三角函數(shù)、除法等計算量大的運算時，多核并行帶來的提升才非常明顯。

轉(zhuǎn)置操作的速度主要受限于非順序訪存行為，屬于訪存密集型。

整個程序的運行流程是： 計算訪存參半-計算較密集-計算訪存參半-訪存密集型。

對于點運算、插值運算和FFT/IFFT變換的優(yōu)化，因其粒度間運算不具有數(shù)據(jù)依賴性，并行性很好。

轉(zhuǎn)置與FFT/IFFT操作不具有交換性，也就是說：若用T(M)表示對矩陣M轉(zhuǎn)置，F(xiàn)r(M)表示對矩陣逐行FFT，F(xiàn)c(M)表示對矩陣逐列進(jìn)行FFT，不具有以下性質(zhì)：

T(Fr(M))=Fc(T(M))

T(Fc(M))=Fr(T(M))

通常轉(zhuǎn)置和FFT/IFFT在SAR成像程序中的位置是相鄰的，這意味著在SAR成像程序中無法將轉(zhuǎn)置隱藏于計算較密集的點運算或插值運算中。

因為FFT/IFFT運算的并行粒度是一行或一列，粒度內(nèi)具有數(shù)據(jù)依賴性，而轉(zhuǎn)置過程中會破壞FFT/IFFT的運算并行粒度，再加上FFT/IFFT運算本身也會占用一定的訪存帶寬資源，使得轉(zhuǎn)置無法與FFT/IFFT并行執(zhí)行，并且并行執(zhí)行的收益也不高。這意味著轉(zhuǎn)置無法通過函數(shù)間并行的方式隱藏于其他計算密集型函數(shù)過程中。

因此，轉(zhuǎn)置成為SAR成像的主要性能瓶頸。

3 程序優(yōu)化與分析

上文對SAR成像程序做出了初步分析。為了得到可靠的性能參考，需要對程序進(jìn)行優(yōu)化，盡量消除其他因素的干擾。在此基礎(chǔ)上，對程序并行性能進(jìn)行實驗，以進(jìn)一步掌握應(yīng)用的特征并獲得性能參照。

本文的實驗平臺配置如表3和表4所示。

Table 3 Runtime environment

Table 4 Compilcation information under parallel computing of different core umbers

3.1 SAR成像的串行優(yōu)化

(1) 部分分支代碼采用順序執(zhí)行代碼執(zhí)行，降低分支預(yù)測失敗懲罰時間，并使程序能更好地向量化。

(2) 對不會產(chǎn)生讀寫沖突的部分去除不需要的數(shù)據(jù)復(fù)制，函數(shù)調(diào)用數(shù)組時直接使用公用的矩陣地址。在轉(zhuǎn)置處設(shè)置線程同步點。例如FFT/IFFT時其各行/列之間的數(shù)據(jù)互不干擾，所有線程可以同時對同一矩陣操作。

(3) 對于非實時數(shù)據(jù)使用查表的方式提前運算。通常這些數(shù)據(jù)是與飛行器有關(guān)的參數(shù)以及由這些參數(shù)產(chǎn)生的參考數(shù)據(jù)。

(4) 去除不必要的內(nèi)存申請與釋放，改為一次性申請足夠的地址。因為飛行器不像PC，需要同步執(zhí)行許多進(jìn)程，不需要太過擔(dān)心內(nèi)存空間的利用率，一次性申請足夠的空間，同一代碼段后續(xù)都使用同一片空間能夠節(jié)省許多內(nèi)存調(diào)度開銷。

以上優(yōu)化步驟使得本測試程序串行運行時間從22 s優(yōu)化至11.5 s。

3.2 SAR成像的并行優(yōu)化

為了分析并行對程序性能的影響，本文分別使用單核、6核和12核對程序性能進(jìn)行測試，實驗結(jié)果如圖3所示。

Figure 3 Run-time comparison of different cores

實際程序中的RemoveRVP、BulkCom、StolIntp都是以實際功能劃分的函數(shù)，包含F(xiàn)FT/IFFT(col_order_FFT為逐列做FFT)。但是，為了將矩陣點運算、插值運算和FFT/IFFT運算分離開來單獨分析，表5中RemoveRVP和BulkCom都只包含相應(yīng)函數(shù)中的矩陣點運算操作，StolIntp只包含插值運算。

Table 5 Function name and cooresponding operation type

3.2.1 計算的時間開銷分析

如圖3所示，對于FFT，從單核串行到6核并行，性能提升了3.5倍，從6核并行到12核并行，性能提升了1.5倍，與理想加速效果相比還有一定距離。

對于IFFT，從單核串行到6核并行，性能提升4.9倍，從六核并行到12核并行，性能提升1.9倍。相比FFT稍好。

對于col_order_FFT，單核串行到6核并行和12核并行，性能提升6倍和12倍，達(dá)到了預(yù)期。

由此可以看出，MKL庫函數(shù)中FFT/IFFT優(yōu)化已經(jīng)做得很好，速度非?？?，但由于FFT/IFFT包含的訪存開銷，它們的計算時間并不能夠簡單地通過增加算力來同比減少，而受限于訪存帶寬。但是，IFFT相比FFT有更少的訪存開銷，通過提高算力帶來的加速效果優(yōu)于FFT。對于col_order_FFT(按列FFT)，即使12核并行下，速度依然比按行FFT慢許多，但是多核并行的優(yōu)化效果顯著。這是因為，按列FFT并不是連續(xù)讀寫，而是隨機(jī)讀寫，不能很好地利用空間局域性。但是，多核并行能夠使原來無法利用的空間局域性得到利用，所以并行在提高計算效率的同時，也提高了訪存效率，其實現(xiàn)原理如圖4所示。

Figure 4 Parallel improves memory access efficiency of column FFT

RemoveRVP中每個點的運算包含了2次三角函數(shù)運算，計算量很大，其性能提升基本與核數(shù)增加保持線性關(guān)系。而對于BulkCom，其中計算很少，都是乘加運算，因此增加核心數(shù)時運算性能的提升不那么明顯。

StolIntp是插值運算，也包含大量三角函數(shù)運算，其性能提升基本與核心數(shù)增加成線性關(guān)系。

3.2.2 訪存的時間開銷分析

除FFT/IFFT不同程度上受限于訪存速度之外，訪存時間的開銷主要集中在轉(zhuǎn)置，可發(fā)現(xiàn)多核并行并不能給轉(zhuǎn)置帶來明顯加速，其速度主要受限于訪存行為。

性能測試結(jié)果顯示，隱式轉(zhuǎn)置時間約為0.05 s，這個數(shù)據(jù)由按列FFT和按行FFT運行時間的差值得到。該差值主要是由于非順序讀寫造成的，因為測試樣例矩陣規(guī)模較大，為8K*8K個float_complex，共計512 MB，一行的大小為64 KB。這個規(guī)模使得訪存行為同時具有Cache內(nèi)讀寫特征和Cache與DDR間的讀取特征。因此，隱式轉(zhuǎn)置的速度同時受DDR帶寬和緩存容量影響。

實驗數(shù)據(jù)顯示，使用MKL庫函數(shù)的條件下，轉(zhuǎn)置的時間開銷約為0.4 s。但是,考慮到實驗使用的MKL庫沒有專門的轉(zhuǎn)置函數(shù)，而是使用單位矩陣與原矩陣相乘并配置結(jié)果矩陣轉(zhuǎn)置參數(shù)實現(xiàn)，其并不能代表轉(zhuǎn)置函數(shù)的性能瓶頸。實際轉(zhuǎn)置函數(shù)在讀寫并發(fā)、合理分塊等優(yōu)化下性能應(yīng)該更優(yōu)。

但是，對于矩陣轉(zhuǎn)置的優(yōu)化，通常也是硬件結(jié)構(gòu)的優(yōu)化[9]，不在本文探討范圍之內(nèi)。本文的關(guān)注點是轉(zhuǎn)置函數(shù)的性能并不會隨算力提升而提升，且會帶來很大的時間開銷，因此需要盡力尋求避免轉(zhuǎn)置的方法。

3.3 SAR成像瓶頸優(yōu)化

2.4節(jié)中已分析過轉(zhuǎn)置是性能瓶頸，傳統(tǒng)的轉(zhuǎn)置優(yōu)化方式[10]需要對硬件提出要求，并且會造成運算核心空轉(zhuǎn)。本文通過同時對列序行序FFT/IFFT運算的支持，用隱式轉(zhuǎn)置的方式代替轉(zhuǎn)置。

下面介紹隱式轉(zhuǎn)置的思路，MKL庫提供了通過按列進(jìn)行FFT/IFFT的函數(shù)接口，用來避免不必要的轉(zhuǎn)置。如圖5所示，其內(nèi)部實現(xiàn)方法是改變按行FFT函數(shù)的數(shù)據(jù)輸入輸出方式；原本是相鄰的一行數(shù)據(jù)作為輸入輸出數(shù)據(jù)，改為彼此間隔為m(矩陣的列數(shù))的n(矩陣的行數(shù))個數(shù)據(jù)作為輸入輸出數(shù)據(jù)。

Figure 5 Data input method of FFT in MKL library

分析可知,按列FFT/IFFT的數(shù)據(jù)讀寫由按行FFT/IFFT的順序讀寫變成了隨機(jī)讀寫，訪存速度會慢很多，可以認(rèn)為隱式地做了2次轉(zhuǎn)置。但需要注意的是，隱式轉(zhuǎn)置從原矩陣間隔讀取數(shù)據(jù)到一個緩存空間中，對這個緩存空間中的數(shù)據(jù)進(jìn)行FFT/IFFT，對緩存空間內(nèi)的數(shù)據(jù)進(jìn)行操作是順序讀寫。最后將數(shù)據(jù)寫回原矩陣的原位置。整個過程用到的緩存空間粒度是一行，相較于普通的轉(zhuǎn)置，使用了更少的緩存空間(普通轉(zhuǎn)置是一個矩陣)，無論是申請和分配空間的速度，還是緩存空間內(nèi)的訪存速度，都比普通轉(zhuǎn)置要快(注意：此處的緩存空間指程序運行時申請的局部空間，并非指硬件中的緩存模塊)。

隱式轉(zhuǎn)置的讀取是非順序讀取，速度慢于轉(zhuǎn)置的順序讀取，寫回時隱式轉(zhuǎn)置和轉(zhuǎn)置都是非順序?qū)懟?，可以認(rèn)為速度一致。雖然非順序的讀取使得隱式轉(zhuǎn)置讀取速度降低，但隱式轉(zhuǎn)置是伴隨著計算發(fā)生的，能夠隱藏相當(dāng)一部分訪存時間。這個性質(zhì)使得按列FFT(其中包含隱式轉(zhuǎn)置)所花費的時間大于按行FFT轉(zhuǎn)置所需的時間，但小于按行FFT+轉(zhuǎn)置所需的時間。

從圖3的實驗結(jié)果也可以看出6核和12核時,col_order_FFT執(zhí)行時間小于FFT+Transpose執(zhí)行時間，這和我們的分析是一致的。

在設(shè)計硬件芯片時，應(yīng)該支持MKL庫中這種按列FFT的形式[10]，此方式在4.5節(jié)中會繼續(xù)討論，同時應(yīng)該對轉(zhuǎn)置進(jìn)行優(yōu)化。若用按列FFT的方式省去轉(zhuǎn)置，可以節(jié)省很大一部分時間開銷。但是，此種方法有一定局限性，例如：轉(zhuǎn)置后需要將矩陣當(dāng)作中間結(jié)果輸出，那么此處的轉(zhuǎn)置不可省去。因為隱式轉(zhuǎn)置實際上并未將矩陣轉(zhuǎn)置而只是通過后續(xù)操作的換方向來達(dá)到邏輯上省去轉(zhuǎn)置的效果。

4 硬件設(shè)計空間的相關(guān)討論

4.1 基礎(chǔ)硬件結(jié)構(gòu)

根據(jù)SAR成像程序的運行模式——FFT/IFFT與矩陣點運算或插值運算交替出現(xiàn)，那么可以通過將FFT/IFFT運算與矩陣點運算或插值運算分開的方法來進(jìn)行硬件設(shè)計，以達(dá)到加速目的。

而為了滿足高性能、低功耗的需求，F(xiàn)FT/IFFT和點運算、插值運算之間在復(fù)雜度上的差別，也決定了它們需要運行在異構(gòu)的運算核心上。從計算的復(fù)雜度可知，F(xiàn)FT/IFFT的運算規(guī)模是矩陣點運算的log2N倍，是插值運算的log2N/k倍。當(dāng)矩陣規(guī)模為8K*8K時，log2N高達(dá)13，把FFT/IFFT和矩陣點運算和插值運算當(dāng)作同樣復(fù)雜度使用同一加速器核心來處理是不合理的。因為同一核心算力不能動態(tài)變化，必然導(dǎo)致特征不同的2種運算間，一種算力盈余，一種算力不足。算力盈余時，性能受限于訪存，造成功耗浪費；算力不足時，又不滿足高性能需求。

另一方面，因為SAR成像程序的特征：FFT與點運算、插值運算交替出現(xiàn)，且每行(列)數(shù)據(jù)間不存在依賴，使用異構(gòu)多核加速器可以實現(xiàn)流水化，從而達(dá)到進(jìn)一步加速的目的。

因此，本文探討的硬件基礎(chǔ)是DSP+FFT加速器的異構(gòu)硬件結(jié)構(gòu)，其中DSP負(fù)責(zé)矩陣點運算和插值運算，F(xiàn)FT加速器[11]負(fù)責(zé)FFT/IFFT運算。異構(gòu)多核加速器結(jié)構(gòu)也已經(jīng)在許多應(yīng)用領(lǐng)域證明了其可行性，例如FT-M6678 8核數(shù)字信號處理器已內(nèi)嵌了FFT加速器核心。

4.2 DSP與FFT加速器算力配比模型

對于DSP+FFT加速器的流水線計算模式，最重要的一點是做好雙核心的并行。而做好并行的關(guān)鍵是使運算核心空閑時間盡可能少，以達(dá)到高效率計算的目的。

在硬件設(shè)計的實際工程中，通常整個平臺能支持的功耗是有限的，為了解決雙核心的算力最優(yōu)分配方案問題，本節(jié)的目的就是解決有限功耗下算力分配的問題。

此處建立一個數(shù)學(xué)模型，前提是可分配給通用DSP和FFT加速器的算力總數(shù)有限且固定，并認(rèn)為算力變化時，函數(shù)的實際處理速度也隨之線性變化。因為DSP的功耗主要集中分布在運算核心上，認(rèn)為功耗和算力成線性關(guān)系是合理的。而整個問題的求解目的是實現(xiàn)高性能與低功耗，平臺總體的算力不會大大超過實際所需(若超過，也應(yīng)該關(guān)閉不必要的運算核心)，在此情況下，函數(shù)的實際處理速度主要受算力影響，并認(rèn)為函數(shù)的處理速度與算力成線性關(guān)系也是合理的。

設(shè)各個變量的含義如表6所示，得到程序總等待時間關(guān)于x、y的函數(shù)如式(1)所示：

(1)

Table 6 Meaning of each variable

下面將介紹建立模型的理論依據(jù)：

因為雙核心的流水線處理模式使得不同類型的運算不在同一個核心中完成，而整個程序的每個Kernel的運算量也存在區(qū)別，無法做到雙核心處理不同Kernel的時間完全一致，必然存在雙核心互相等待的時間。但是，這個閑置時間可以通過合理配比來達(dá)到最小。

在FFT/IFFT和點運算、插值運算之間，可能存在計算行為上的差別，如三角函數(shù)和乘加運算，復(fù)雜度一致時，運算量也不一樣。除了計算行為的差別之外，訪存密度的差距也會使相同規(guī)模的FFT/IFFT與(點運算、插值運算)之間存在執(zhí)行速度差距。因此，同規(guī)模的FFT/IFFT與(點運算、插值運算)之間速度懸殊，同時受計算行為和訪存行為因素影響。通常這2種影響是很難單獨測量出來的。為了減少這些影響，將這二者的影響統(tǒng)一為一個參數(shù)比例(C1∶C2)來修正結(jié)果，這個比例的直觀意思是單位計算量下的執(zhí)行時間的比例，該參數(shù)由實驗平臺測得。

實際上不同Kernel的矩陣點運算和插值運算的參數(shù)也有細(xì)微區(qū)別，但若完全考慮，則會讓問題的求解變得非常復(fù)雜。若以本文圖2流程為例，RemoveRVP點運算和StolIntp插值運算的參數(shù)是相近的。數(shù)學(xué)建模對此進(jìn)行合理精簡，即認(rèn)為各個Kernel的矩陣點運算與插值運算的參數(shù)一致，參數(shù)的差別僅存在于FFT/IFFT與矩陣的(點運算、插值運算)之間。

由式(1)可知，程序的總等待時間是關(guān)于x、y的二元函數(shù)。由于模型前提假定算力總數(shù)一定，即x+y=P，P是一個常量。此時即使不知道P的具體值，也可以求得使T最小時的x/y值。以圖2示例的算法對應(yīng)的SAR成像程序為例：

k=1.1,a∶b=3∶1,N∶M=0.69，C1∶C2=0.4

其中,k、N:M可由表1計算得到，a∶b可由圖2得到，C1∶C2則是一個經(jīng)驗值，可由圖3得到。將這些值代入式(1)，可以繪制出如圖6所示的梯度圖。從梯度圖中可以觀察到，圖像的極小點連成一條平行于xoy平面的直線，此直線在xoy平面上的投影是一條直線。這意味著，在近似認(rèn)為函數(shù)性能與算力成線性關(guān)系的前提下，使程序的運行效率最優(yōu)的配比x/y是一個與x+y(平臺的總算力)無關(guān)的值。在任何具體的總算力下，得到的最優(yōu)配比方案是一致的。下面將進(jìn)行數(shù)學(xué)推導(dǎo)驗證。

Figure 6 Relationship between the total waiting time of computing and the ratio of dual core computing power

設(shè)圖6所示梯度圖的解析式為f(x,y),將x+y=P代入f(x,y),可以得到此梯度圖在平面x+y=P上的橫截曲線。需要求得投影曲線最低點的x∶y的值，此時，y可以表示為P-x，二元函數(shù)就轉(zhuǎn)變?yōu)榱艘辉瘮?shù)。

x∶y=x∶(P-x)=a

使用拉格朗日乘子法求最小值以及分類討論，得到以下結(jié)論：

若a>b，且kb>a，則最優(yōu)配比為：

可以看出，此結(jié)果是與P(平臺總算力)無關(guān)的量。

以圖2所示程序為例，代入表1和表2的數(shù)據(jù)求得：

因為a>bk>b,則α=x∶y的最佳配比為0.276=1∶3.62。

這意味著若某個嵌入式芯片運行圖2中的程序，則其FFT加速器與通用DSP的算力最優(yōu)配比為1∶3.62。

4.3 算力配比模型的應(yīng)用

算力配比模型的目標(biāo)是賦予針對SAR成像程序定制硬件可編程的靈活性，一方面通用DSP具有可編程靈活性，另一方面就是應(yīng)用算力配比模型實現(xiàn)算力靜態(tài)可分配。

應(yīng)用方式有2種：一種是設(shè)計硬件前，提前根據(jù)特定應(yīng)用程序的需求，計算出最優(yōu)算力配比來劃分硬件算力。另一種是硬件已經(jīng)固定，需要更換應(yīng)用程序時，根據(jù)模型求出新的最優(yōu)算力配比，據(jù)此合理關(guān)閉多余算力。因為在DSP中，運算核心即使不執(zhí)行任何指令，也會存在靜態(tài)功率，這樣的空轉(zhuǎn)消耗是不必要的。

值得注意的是，F(xiàn)FT加速器啟用核心的數(shù)目與DSP啟用核心數(shù)目的比值只能是2個整數(shù)的比值，相應(yīng)的算力分配比例也不具有連續(xù)性，而是離散的。采用最近舍入即可解決該問題，或者對2個最近候選可分配比例代入求最優(yōu)。容易證明，可啟用的核心數(shù)越多，可分配的比例數(shù)量就越多，離理論最優(yōu)解就越接近。但是，核心數(shù)過多會導(dǎo)致運算核心靜態(tài)功率與動態(tài)功率的比值上升，計算效率下降。設(shè)計時需要做出權(quán)衡取舍，但此問題不在本文討論范圍內(nèi)。

3.2節(jié)中已提到過，DSP算力的功率主要在于計算指令，從這個角度上來說，節(jié)省算力資源，就是節(jié)省平臺功耗。

4.4 DDR的帶寬影響

下面將著重討論訪存帶寬對轉(zhuǎn)置函數(shù)和FFT/IFFT函數(shù)的執(zhí)行效率的影響。

轉(zhuǎn)置函數(shù)為訪存密集型，但由于其寫回時訪存模式為非順序訪存，轉(zhuǎn)置的性能瓶頸在訪存帶寬不太低時，和訪存帶寬關(guān)系不大。具體的帶寬臨界值可以參考3.2節(jié)中隱式轉(zhuǎn)置的瓶頸得出，約為10.24 GB/s，即帶寬大于此值時轉(zhuǎn)置性能受帶寬影響不大。

隱式轉(zhuǎn)置同樣具有非順序訪存的性質(zhì)，故帶寬大于10.24 GB/s時，性能受帶寬影響不大。

下面討論訪存帶寬對FFT/IFFT性能的影響:

設(shè)FFT/IFFT的計算時間為tx，訪存時間為ty。依據(jù)圖3的實驗數(shù)據(jù)，觀察不同核心數(shù)下FFT的執(zhí)行時間，可以列出如下方程組：

由①②解得tx=0.27，ty=0.05。

tx/12+ty=0.0727基本符合式③。

在考慮核心頻率浮動的情況下，可以認(rèn)為多核并行運算對FFT/IFFT的訪存速度沒有影響，F(xiàn)FT/IFFT函數(shù)的執(zhí)行時間為計算時間+訪存時間。

同理驗證得到此性質(zhì)對IFFT也成立。

由上述計算得到FFT的訪存時間約為0.05 s。FFT訪存規(guī)模為3.25 GB，平臺訪存帶寬為68.3 GB/s，計算得3.25/68.3=0.047 s，約等于0.05 s，可以認(rèn)為FFT/IFFT的訪存速度與訪存帶寬成線性關(guān)系。從FFT/IFFT的訪存行為上來說，這種性質(zhì)是因為FFT/IFFT采用分治算法，F(xiàn)FT中的數(shù)據(jù)訪存大部分為順序讀寫。

這種性質(zhì)同樣適用于點運算和插值運算的順序訪存行為?？梢哉J(rèn)為提高帶寬主要是提升FFT/IFFT和點運算、插值運算的速度，但點運算和插值運算依然是計算占主導(dǎo)，性能提升不如FFT/IFFT。因此，提高訪存帶寬對FFT/IFFT、點運算和插值運算的訪存時間具有線性提升效果，但因為這些操作同時有計算時間開銷，使得整體提升效果不甚理想。

4.5 針對SAR成像程序的緩存結(jié)構(gòu)優(yōu)化探討

4.1節(jié)提到了并行的列序FFT/IFFT能夠利用緩存降低非順序讀寫的開銷，此特性能很大程度降低隱式轉(zhuǎn)置非順序訪存帶來的負(fù)面影響，則針對SAR成像程序的硬件定制應(yīng)該具有對此性質(zhì)很好的適配性。

構(gòu)建如下硬件結(jié)構(gòu)：

3級緩存設(shè)計為多核心共享。已經(jīng)驗證無論是行序FFT或列序FFT在并行粒度上也就是線程間是沒有數(shù)據(jù)相關(guān)性的，因此3級緩存即使是多核共享也不會產(chǎn)生讀寫沖突。關(guān)于3級緩存的大小，條件允許的情況下，應(yīng)該大于最大的矩陣規(guī)模。但是，有的SAR成像需求的矩陣大小超過8K*8K，難以完整存儲在緩存中，幸運的是可以驗證即使緩存無法完整存儲一個矩陣，也只會使處理速度稍微降低(多幾次突發(fā)(burst)訪問)，并不會破壞并行線程間對于共享緩存的讀取。

1、2級緩存設(shè)置為單核獨占。因為FFT/IFFT需要同時支持行序和列序執(zhí)行，因此依然要支持已經(jīng)被證明在順序讀寫時高效的多級緩存結(jié)構(gòu)。但同時因為對列序FFT/IFFT的支持，需要將1級緩存設(shè)計為4字節(jié)burst訪問，即一個float(32位體系結(jié)構(gòu)下)。因為列序訪問數(shù)據(jù)的不連續(xù)性，更大的burst訪問讀取沒有意義，相反還占用burst訪問資源。

在此硬件體系結(jié)構(gòu)的基礎(chǔ)上應(yīng)該提供針對此性質(zhì)的函數(shù)接口。具體實現(xiàn)方式是使每個執(zhí)行FFT/IFFT的線程從矩陣中完整讀取一列數(shù)據(jù)并存儲在線程內(nèi)部的連續(xù)內(nèi)存空間中，之后再對此緩存空間中的數(shù)據(jù)進(jìn)行計算后寫回。

而為了達(dá)到多線程并行利用共享緩存降低非順序讀寫開銷的目的，需要在多線程讀取數(shù)據(jù)的步驟中添加同步點，當(dāng)所有進(jìn)程均讀取完3級緩存中能取到的所有數(shù)據(jù)后，3級緩存再對DDR進(jìn)行burst訪問讀取數(shù)據(jù)，以達(dá)到多線程同步讀取同一塊矩陣的目的。極端情況下，例如3級緩存能夠完整存儲整個矩陣時，具有此體系結(jié)構(gòu)支撐的列序FFT/IFFT理論上能達(dá)到行序FFT/IFFT的性能。

5 結(jié)束語

本文首先對基于目前最成熟、使用最廣泛的Range-Dopller算法的SAR成像程序進(jìn)行了計算和訪存特征分析；然后對SAR成像代碼進(jìn)行了優(yōu)化并基于x86平臺進(jìn)行了模擬SAR成像實驗，進(jìn)一步細(xì)化算法特征且得到了性能參照；最后基于DSP+FFT加速器體系結(jié)構(gòu)和算法特征，建立了一個數(shù)學(xué)模型，來解決硬件設(shè)計空間里的算力配比問題。根據(jù)算力配比模型，在給定應(yīng)用參數(shù)情況下，可以獲得最優(yōu)比例；在硬件確定的情況下，可以根據(jù)不同應(yīng)用的算力配比提供最優(yōu)的能效。

硬件設(shè)計空間探討還包括訪存帶寬和緩存結(jié)構(gòu)。為解決訪存瓶頸問題，根據(jù)實驗分析了提高訪存帶寬對程序性能的影響，并給出了解決轉(zhuǎn)置瓶頸的方式。訪存帶寬主要影響FFT/IFFT的速度，其次是影響點運算和插值運算的速度。在算力提升到瓶頸時，可以考慮分配更多的功率給讀寫帶寬。