SAR成像應用特征分析及硬件設計空間討論*

孔璽暢,文 梅,藍 強

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

1 引言

合成孔徑雷達SAR(Synthetic Aperture Radar)是一種主動式的對地觀測系統，可安裝在飛機、衛星和宇宙飛船等飛行平臺上，全天時、全天候對地實施觀測，且具有一定的地表穿透能力。因此，SAR系統在災害監測、環境監測、海洋監測、資源勘查、農作物估產、測繪和軍事等方面的應用具有獨特的優勢，可發揮其他遙感手段難以發揮的作用，因此越來越受到世界各國的重視[1]。

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

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

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

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

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

2 SAR成像程序分析

2.1 SAR成像程序的運行模式

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

Figure 1 Two basic calculation kernels

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

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

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

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

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

2.2 SAR成像的計算特征分析

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

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

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

Table 1 Calculation amount of each function

嚴格意義上，FFT/IFFT處理的數據規模是一行(列)，為了方便比較各函數間整體運算量的關系，這里的FFT是指對整個矩陣逐行(列)進行FFT/IFFT。

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

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

2.3 SAR成像的訪存特征分析

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

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

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

Table 2 Memory access amount of each function

2.4 瓶頸分析

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

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

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

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

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

轉置與FFT/IFFT操作不具有交換性，也就是說：若用T(M)表示對矩陣M轉置，Fr(M)表示對矩陣逐行FFT，Fc(M)表示對矩陣逐列進行FFT，不具有以下性質：

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

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

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

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

因此，轉置成為SAR成像的主要性能瓶頸。

3 程序優化與分析

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

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

Table 3 Runtime environment

Table 4 Compilcation information under parallel computing of different core umbers

3.1 SAR成像的串行優化

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

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

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

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

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

3.2 SAR成像的并行優化

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

Figure 3 Run-time comparison of different cores

實際程序中的RemoveRVP、BulkCom、StolIntp都是以實際功能劃分的函數，包含FFT/IFFT(col_order_FFT為逐列做FFT)。但是，為了將矩陣點運算、插值運算和FFT/IFFT運算分離開來單獨分析，表5中RemoveRVP和BulkCom都只包含相應函數中的矩陣點運算操作，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倍，達到了預期。

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

Figure 4 Parallel improves memory access efficiency of column FFT

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

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

3.2.2 訪存的時間開銷分析

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

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

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

但是，對于矩陣轉置的優化，通常也是硬件結構的優化[9]，不在本文探討范圍之內。本文的關注點是轉置函數的性能并不會隨算力提升而提升，且會帶來很大的時間開銷，因此需要盡力尋求避免轉置的方法。

3.3 SAR成像瓶頸優化

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

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

Figure 5 Data input method of FFT in MKL library

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

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

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

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

4 硬件設計空間的相關討論

4.1 基礎硬件結構

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

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

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

因此，本文探討的硬件基礎是DSP+FFT加速器的異構硬件結構，其中DSP負責矩陣點運算和插值運算，FFT加速器[11]負責FFT/IFFT運算。異構多核加速器結構也已經在許多應用領域證明了其可行性，例如FT-M6678 8核數字信號處理器已內嵌了FFT加速器核心。

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

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

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

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

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

(1)

Table 6 Meaning of each variable

下面將介紹建立模型的理論依據：

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

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

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

由式(1)可知，程序的總等待時間是關于x、y的二元函數。由于模型前提假定算力總數一定，即x+y=P，P是一個常量。此時即使不知道P的具體值，也可以求得使T最小時的x/y值。以圖2示例的算法對應的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則是一個經驗值，可由圖3得到。將這些值代入式(1)，可以繪制出如圖6所示的梯度圖。從梯度圖中可以觀察到，圖像的極小點連成一條平行于xoy平面的直線，此直線在xoy平面上的投影是一條直線。這意味著，在近似認為函數性能與算力成線性關系的前提下，使程序的運行效率最優的配比x/y是一個與x+y(平臺的總算力)無關的值。在任何具體的總算力下，得到的最優配比方案是一致的。下面將進行數學推導驗證。

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

設圖6所示梯度圖的解析式為f(x,y),將x+y=P代入f(x,y),可以得到此梯度圖在平面x+y=P上的橫截曲線。需要求得投影曲線最低點的x∶y的值，此時，y可以表示為P-x，二元函數就轉變為了一元函數。

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

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

若a>b，且kb>a，則最優配比為：

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

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

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

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

4.3 算力配比模型的應用

算力配比模型的目標是賦予針對SAR成像程序定制硬件可編程的靈活性，一方面通用DSP具有可編程靈活性，另一方面就是應用算力配比模型實現算力靜態可分配。

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

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

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

4.4 DDR的帶寬影響

下面將著重討論訪存帶寬對轉置函數和FFT/IFFT函數的執行效率的影響。

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

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

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

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

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

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

在考慮核心頻率浮動的情況下，可以認為多核并行運算對FFT/IFFT的訪存速度沒有影響，FFT/IFFT函數的執行時間為計算時間+訪存時間。

同理驗證得到此性質對IFFT也成立。

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

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

4.5 針對SAR成像程序的緩存結構優化探討

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

構建如下硬件結構：

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

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

在此硬件體系結構的基礎上應該提供針對此性質的函數接口。具體實現方式是使每個執行FFT/IFFT的線程從矩陣中完整讀取一列數據并存儲在線程內部的連續內存空間中，之后再對此緩存空間中的數據進行計算后寫回。

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

5 結束語

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

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