基于超標量處理器的高效FFT映射方法

高立寧，朱亮，劉騰飛，劉峰

(北京理工大學 信息與電子學院，北京 100081)

?

基于超標量處理器的高效FFT映射方法

高立寧，朱亮，劉騰飛，劉峰

(北京理工大學 信息與電子學院，北京 100081)

針對超標量處理器的結(jié)構(gòu)特點，研究新的映射方法，實現(xiàn)高效FFT運算. 對現(xiàn)代超標量結(jié)構(gòu)處理器進行建模，分析FFT算法在其上執(zhí)行情況，得出內(nèi)存訪問是FFT算法執(zhí)行的關(guān)鍵點. 并進一步對FFT的內(nèi)訪問過程進行建模分析，最終實現(xiàn)了一種基于cache優(yōu)化的高效FFT映射方法，該方法將FFT進行拆分實現(xiàn)，充分發(fā)揮了cache的作用，進而提高了處理性能. 最后在ADI公司的TS201數(shù)字信號處理器上，以該映射方法為指導實現(xiàn)了基2FFT算法，實驗結(jié)果顯示在處理點數(shù)超出cache容量時，本映射方法可以大幅度提高處理性能.

快速傅里葉變化(FFT)；高速緩存(cache)；超標量處理器

快速傅里葉變化(fast Fourier transform， FFT)是現(xiàn)代化雷達信號處理中的關(guān)鍵技術(shù)之一，由于雷達系統(tǒng)是一種強實時處理系統(tǒng)，F(xiàn)FT作為系統(tǒng)中的重要組成部分，必須在限定的時間內(nèi)完成處理，因此高效的FFT處理是必要的[1].

目前高效FFT算法實現(xiàn)主要有兩種：一種是通過ASIC或FPGA實現(xiàn)，這種硬件實現(xiàn)方法適應(yīng)算法特點，功耗低且實時性高，但是這種方法缺乏靈活性且開發(fā)周期長. 常用的另一種方法是基于處理器的編程實現(xiàn)，該方法通過程序代碼將FFT實現(xiàn)，開發(fā)周期短且靈活，并且處理器的主頻在不斷提高，F(xiàn)FT的執(zhí)行時間也在不斷縮短，因此基于處理器程序編寫的方法有著更多的優(yōu)勢. 然而處理器結(jié)構(gòu)固定，并非完全按照FFT算法結(jié)構(gòu)特點設(shè)計，這就要求在編程實現(xiàn)時，找到一種新的映射方法將FFT映射到處理器中，使處理器的處理效率最大化發(fā)揮，進而滿足實時性需求.

針對上述分析，本文對超標量處理器結(jié)構(gòu)進行研究，將與處理相關(guān)的因素進行參量化，建立了超標量處理器的程序執(zhí)行模型. 以基2FFT算法為例，分析了常規(guī)FFT算法映射方法的缺點，并針對這些問題提出解決方法，提出了可拆分的FFT映射算法，該映射算法充分利用了處理器上的處理資源，同時利用cache特點大大縮短了內(nèi)存訪問時間，進而使處理器性能最大發(fā)揮. 最后以該映射算法為指導，在ADI公司的TS201數(shù)字信號處理器(DSP)上實現(xiàn)了基2FFT算法，并取得了滿意的結(jié)果.

1 超標量處理器的結(jié)構(gòu)特點

現(xiàn)代化處理器中均采用了超標量流水線技術(shù)，超標量流水線是并行流水線，其將指令執(zhí)行分為若干部分(通常包括取址、譯碼、執(zhí)行、訪存、寫回)，然后通過流水線技術(shù)，使同一時刻多條指令處于不同的處理階段. 其利用時間并行方法，提高了處理器的吞吐率. 并且處理器中采用不同的執(zhí)行單元，執(zhí)行不同功能指令，可以在每個機器周期中啟動對多個指令的處理，提高了指令的執(zhí)行效率[2-3]，圖1顯示了超標量處理器的工作原理.

圖1所示為同時有4條指令執(zhí)行的超標量流水原理圖，從圖中可以看出指令執(zhí)行被分為6個階段：① 讀取階段，主要負責從內(nèi)存中獲取執(zhí)行代碼；② 解碼階段，主要任務(wù)是將指令翻譯為機器可識別的操作碼；③ 調(diào)度階段，負責將指令按照功能分配到各個功能執(zhí)行部件上執(zhí)行，同時在該階段負責查找指令中的相關(guān)指令，并進行調(diào)度；④ 執(zhí)行階段，主要完成指令的功能；⑤、⑥完成和退出階段，這兩個階段主要負責修改指令完成后的機器狀態(tài)，同時保證指令的順序完成. 在超標量架構(gòu)的處理器中，如上處理中階段①，②，③，⑤及階段⑥針對所有指令工作機理一樣，因此在設(shè)計中常常通過集中處理方式完成這⑤個階段，針對階段④，不同功能指令執(zhí)行過程會不同，因此這一階段設(shè)計采用了分布式處理方式[2-3].

以上介紹均是假設(shè)流水處理中每個階段執(zhí)行時間相同，然而實際應(yīng)用中由于內(nèi)存訪問速度遠遠低于內(nèi)核速度，導致數(shù)據(jù)訪問時間很長，這種情況會打破流水線運行，降低處理效率. 為解決這一問題，處理器中引入了同內(nèi)核速度相當?shù)母咚倬彺?cache). cache利用程序的局部性原理，將最近訪問的數(shù)據(jù)存儲在cache中，當訪問內(nèi)存時首先會查詢cache中是否緩存，如果在緩存命中(hit)，那么直接獲取數(shù)據(jù)，減少時間開銷；如果沒有命中(miss)，將會啟動內(nèi)存訪問，并將訪問結(jié)果緩存[4-6]. 通過合理設(shè)置cache容量，可以有效緩和內(nèi)存速度與處理器內(nèi)核速度不匹配問題，充分發(fā)揮處理器性能.

綜上所述，基于超標量結(jié)構(gòu)的現(xiàn)代化處理器，通過并行流水增加處理器吞吐量，并提高處理效率；為了緩和內(nèi)存與內(nèi)核的不均衡，現(xiàn)代處理器中引入cache，使內(nèi)核計算與數(shù)據(jù)訪問相匹配. 通過如上技術(shù)改進，可以不斷提高處理器的處理能力. 在實際應(yīng)用中程序執(zhí)行的實時性，一方面與處理器的處理能力相關(guān)；另一方面也與應(yīng)用算法在處理器上的映射相關(guān)，需要采用合適的映射算法，使程序執(zhí)行過程適合超標量架構(gòu)特點，最大化發(fā)揮處理能力，才可實現(xiàn)實時處理.

2 基于超標量處理器的FFT映射方法

如上討論可知，現(xiàn)代處理器中不同類別指令分別由獨立的執(zhí)行單元運行，因此處理器可以抽象為若干相互關(guān)聯(lián)的執(zhí)行單元的集合，設(shè)處理器中執(zhí)行單元數(shù)為s，其中任意一個單元i的執(zhí)行速度為vi，那么所有執(zhí)行單元的處理速度(對于不同執(zhí)行單元處理速度定義也不同，內(nèi)存控制執(zhí)行單元以訪問帶寬表示；內(nèi)核計算單元以單位時間內(nèi)執(zhí)行的操作次數(shù)表示)可構(gòu)成集合V={v1，v2，…，vs}. 運行于處理器上的程序，也可按照執(zhí)行單元劃分為s個處理任務(wù)(任務(wù)包括內(nèi)存讀寫、乘法操作等)，設(shè)其中任意一個處理任務(wù)i的任務(wù)量(對于不同任務(wù)的任務(wù)量定義不同，內(nèi)存訪問以訪問的字節(jié)數(shù)表示，數(shù)據(jù)計算以運算次數(shù)表示任務(wù)量)為ci，那么程序的任務(wù)量可由集合C={c1，c2，…，cs}表示. 當程序在各個部件執(zhí)行時，每個單元的執(zhí)行時間可組成集合

T={t1，t2，…，ts}={c1/v1，c2/v2，…，cs/vs}.

集合T中每個元素表示程序中各個任務(wù)的執(zhí)行時間，這些執(zhí)行相互交疊，構(gòu)成了程序最終處理時間. 因此為研究實時性，應(yīng)對集合T中的元素間關(guān)系進行研究，為方便討論符號定義如下：

①αi|j表示任務(wù)j的執(zhí)行時間與任務(wù)i執(zhí)行時間重疊部分占任務(wù)j執(zhí)行時間的百分比，這里稱該百分比為重疊度(使用重疊度，主要反映各個執(zhí)行單元間的并行度，該比值與映射算法及處理器資源相關(guān))；

②t(i，j)表示任務(wù)i，j的總執(zhí)行時間.

由如上定義可得處理過程中任務(wù)i，j的總執(zhí)行時間為

(1)

如果將任務(wù)i，j合并為一個大的任務(wù)I，那么該任務(wù)與任務(wù)集C中的任務(wù)k并行執(zhí)行時間可表示為

(2)

對如上計算過程進行遞歸計算，那么可得程序中s個任務(wù)并行執(zhí)行總時間為

(3)

式(3)表明了執(zhí)行過程中，程序每部分任務(wù)處理時間與總時間關(guān)系. 由于集合T中的各個元素具有對等性，不失一般性，這里令t1為所有執(zhí)行時間中數(shù)值最大的，即滿足如下:

(4)

這里稱t1為最大執(zhí)行時間，那么可得如下關(guān)系:

(5)

由式(4)和(5)可知當所有重疊度均為1時，執(zhí)行時間最小，此時的物理意義為：程序在處理器上各執(zhí)行單元的處理過程均隱藏在執(zhí)行時間最長的處理過程中. 因此應(yīng)用算法映射到處理器上執(zhí)行時，應(yīng)結(jié)合處理器特點合理安排處理順序，盡量使所有處理均能隱藏在處理時間最長的任務(wù)中，即要求程序在實現(xiàn)時應(yīng)充分發(fā)掘指令間的并行性，合理安排指令流水，使程序執(zhí)行時間趨于最大處理時間.

基于如上分析，對程序在現(xiàn)代處理器上的執(zhí)行時間建立了模型. 當FFT算法映射到處理器上執(zhí)行時，按照如上所述可劃分為4個處理任務(wù)：乘法任務(wù)、加法任務(wù)、減法任務(wù)和讀寫任務(wù). 針對現(xiàn)代化處理器，如上4個任務(wù)可分別在乘法器、加法器、減法器和內(nèi)存訪問控制器中執(zhí)行. 對指令流水進行合理安排，F(xiàn)FT執(zhí)行時序如圖2所示(該圖所示時序圖為處理數(shù)據(jù)一部分位于cache，一部分位于內(nèi)存).

流水建立分為填充、流水、排空3個階段[6]. 當進入流水階段后，所有的處理(乘法運算、加減法運算)均隱藏在內(nèi)存訪問中，只有在填充和排空階段部分隱藏. 因此可以把內(nèi)存執(zhí)行時間作為最大執(zhí)行時間，即任務(wù)1，令乘法處理為任務(wù)2，加法處理為任務(wù)3，減法為任務(wù)4，設(shè)處理中每級FFT的蝶形計算個數(shù)為n，那么可得每級處理中的重疊度為

(6)

式(6)表明FFT處理中各個任務(wù)的重疊度與處理中每級蝶形運算個數(shù)n成反比，當n取值較大時，可認為所有任務(wù)執(zhí)行的重疊度為1，即所有內(nèi)核計算隱藏在內(nèi)存訪問中進行. 對于雷達系統(tǒng)而言，F(xiàn)FT處理通常是在幾千點以上，每級的蝶形計算次數(shù)也在幾千個以上，因此內(nèi)存訪問便成為FFT映射中的關(guān)鍵性問題. 通過第1節(jié)介紹可知，內(nèi)存訪問速度低于內(nèi)核處理速度，故引入了緩存解決該問題. 通過圖2中所示時序圖可以看出，當數(shù)據(jù)在cache中時，內(nèi)存讀或?qū)懙臅r間與內(nèi)核計算時間相匹配，但是訪問數(shù)據(jù)沒有命中時，會在流水線中引入額外的時間消耗[7-9]. 可見cache的利用對FFT程序執(zhí)行很重要. 如下主要針對FFT在處理器中的內(nèi)存訪問過程進行建模并分析，首先對一些相關(guān)因素符號化：

① cache命中率設(shè)為P，該值表示數(shù)據(jù)訪問過程中，數(shù)據(jù)在cache中的概率；

② 丟失時引入的額外時間設(shè)為tmiss，當訪問數(shù)據(jù)不在cache中，需從內(nèi)存獲取數(shù)據(jù)而產(chǎn)生的額外消耗時間；

③ 高速緩存的存儲容量設(shè)為cacheL，為方便討論以復(fù)數(shù)點為單位，其中每個復(fù)數(shù)點包括IQ兩個數(shù)據(jù)，每個數(shù)據(jù)由b個字節(jié)組成;

④ 高速緩存一行可以緩存的數(shù)據(jù)容量為w，為了討論方便這里w表示的是復(fù)數(shù)點，其中每個復(fù)數(shù)點包括IQ兩個數(shù)據(jù)，每個數(shù)據(jù)由b個字節(jié)組成；

⑤ 數(shù)據(jù)的訪問時間Tio，該值表示數(shù)據(jù)的讀寫時間；

⑥ 處理的數(shù)據(jù)長度為L，該值以復(fù)數(shù)點為單位且為2的整數(shù)次冪，其中每個復(fù)數(shù)點包括IQ兩個數(shù)據(jù)，每個數(shù)據(jù)由b個字節(jié)組成；

⑦ cache訪問帶寬為Bc，單位為byte/s.

目前常用的FFT算法大部分是基2的快速變換算法，因此本文中以基2算法為例對內(nèi)存訪問過程建模，所得結(jié)果對其他快速變換算法同樣適用[10-11]. 基2FFT算法的蝶形數(shù)據(jù)流圖如圖3所示.

圖4為蝶形運算的傳統(tǒng)實現(xiàn)方法流程圖.

依據(jù)圖4可知，傳統(tǒng)的FFT映射算法需要做n級(n=lbL)蝶形運算，每一級蝶形運算訪問的數(shù)據(jù)量為L，因此，如果每一級訪問的cache命中率為Pi，時間消耗為tmiss，那么FFT的執(zhí)行時間中因cache丟失所引入的時間消耗為

(7)

有前面論證可知FFT執(zhí)行中主要時間為數(shù)據(jù)訪問(包括數(shù)據(jù)讀、寫)，由于每級處理數(shù)據(jù)訪問量2L(包括讀一次，寫一次數(shù)據(jù)訪問)，根據(jù)前面的參數(shù)假設(shè)，可得處理長度為L的數(shù)據(jù)時內(nèi)存訪問時間(傳統(tǒng)FFT中有效執(zhí)行時間)為

(8)

綜上所述，傳統(tǒng)的FFT映射方法的執(zhí)行時間近似為

(9)

由于基2FFT數(shù)據(jù)流為原位處理，所以數(shù)據(jù)寫回內(nèi)存時不會發(fā)生丟失，故每級處理中丟失次數(shù)為L(1-Pi). 可用如下公式表示正常映射方式的內(nèi)存訪問時間:

(10)

在式(10)的表示含義為：處理過程中的第一級處理必然存在丟失現(xiàn)象，由于內(nèi)存控制器以cache的行長w為單位訪問數(shù)據(jù)，那么訪問w個數(shù)據(jù)后便會丟失一次，所以第一級丟失概率為1/w；如果處理長度小于cache容量，以后每級處理均可在cache中命中數(shù)據(jù)，丟失率為0；如果處理長度大于cache容量，以后的每級都與第一級處理過程一樣，每級的丟失率為1/w.

為了充分發(fā)揮cache的作用，縮短大點數(shù)處理時間，應(yīng)提高訪問過程中的命中率，減少丟失次數(shù). 一種解決方法便是考慮映射實現(xiàn)時將大點數(shù)劃分為小點數(shù)分段處理，這樣每次小點數(shù)處理時可以充分發(fā)揮cache作用，縮短了處理時間[12]. 為實現(xiàn)這個目的可以從離散傅里葉變換公式入手.

(11)

對式(11)中的變量l，k分別進行分解：

(12)

將式(12)帶入式(11)中可得

(13)

式(13)中第二項求和表示按列方向進行離散傅里葉變換，那么通過式(13)可以獲得拆分的方法：

① 將一維的數(shù)據(jù)序列分為一個F*Y矩陣；

② 對矩陣的每一列進行傅里葉變換；

④ 再逐行進行離散傅里葉變換.

基于如上思想FFT算法映射到處理器執(zhí)行時，可以先拆分，然后對每維采用FFT算法進行處理，為了縮短處理時間，可將第3步融合到每列FFT計算的最后一級. 通過該映射方式映射后的程序執(zhí)行流程圖如圖5所示.

采用本文介紹的映射方法實現(xiàn)快速傅里葉變化，可根據(jù)式(12)計算每步執(zhí)行時間.

對二維矩陣所有列FFT變換的時間消耗：

(14)

因子相乘，可與FFT中最后一級的運算放在一起進行，那么乘以因子的時間消耗主要是內(nèi)存讀時間，可表示如下：

(15)

對矩陣所有行FFT變換的時間消耗為

(16)

按照如上3個步驟執(zhí)行完后，總時間消耗為

(17)

按照將大點數(shù)數(shù)據(jù)拆分成小段去運算的思路，使得每一小段能夠放到cache中，將cache充分利用起來，提高了cache命中率，進而總運算時間得以下降. 如式(17)表示，采用本映射算法映射后的FFT算法，在處理數(shù)據(jù)長度小于cache容量時，并沒有優(yōu)勢，但是當處理長度大于cache容量時，要優(yōu)于正常映射方法. 為了驗證本映射方法的有效性，如下以該映射算法為指導，在ADI公司的TS201處理器上實現(xiàn)基2FFT算法.

3 基于TS201處理器的高效FFT映射實現(xiàn)

TS201處理器是ADI公司推出的一款高性能靜態(tài)超標量信號處理器，主頻為600 MHz，采用超標量流水線技術(shù)每個時鐘周期可執(zhí)行4條指令，在內(nèi)核計算方面采用SIMD(單指令多數(shù)據(jù)流)方式，每個時鐘周期可以執(zhí)行2個浮點乘法，2個浮點加法和2個浮點減法；存儲性能方面，處理器內(nèi)部集成了24 Mbit內(nèi)存，共分為6個分區(qū)(bank)；TS201內(nèi)部有4條128 bit寬度的內(nèi)部總線，通過J和K兩個整型ALU可以實現(xiàn)一個周期內(nèi)4個32 bit數(shù)據(jù)的讀取和4個32 bit數(shù)據(jù)的存儲；為解決內(nèi)核速度與內(nèi)存速度不均衡問題，每個bank帶有一個容量為128 kbit(2 048個浮點型復(fù)數(shù))的高速緩存，每個cache的行長度為256 bit(4個浮點型復(fù)數(shù))，當數(shù)據(jù)位于高速緩存中，一個時鐘周期便可完成數(shù)據(jù)訪問，如果數(shù)據(jù)不在cache中，將會花費7～8個時鐘周期完成數(shù)據(jù)訪問任務(wù).

按照映射算法將FFT映射到TS201上執(zhí)行，首先應(yīng)確定拆分后的二維矩陣大小. 這里以使兩維處理均衡為目的，按照如下準則劃分：

(18)

在實際應(yīng)用中由于處理的數(shù)據(jù)量很大，常常將數(shù)據(jù)存儲在DSP片外存儲空間中(通常為SDRAM)，因此在從SDRAM中訪問數(shù)據(jù)時可以使用DSP處理器中的DMA按照式(18)的劃分方式將數(shù)據(jù)搬移到片內(nèi)存儲空間. 由于第一步處理是按列進行，所以搬移可按照列連續(xù)，行跳躍的方式讀取數(shù)據(jù)，目前所有DMA均支持該方式. 數(shù)據(jù)獲取完畢，便可訪問數(shù)據(jù)進行處理，在處理過程中為了充分發(fā)揮處理器的存儲資源，本程序?qū)⑿D(zhuǎn)因子和數(shù)據(jù)放在不同bank中，這樣便可在讀取處理數(shù)據(jù)的同時，訪問旋轉(zhuǎn)因子. 另外對于程序中旋轉(zhuǎn)因子長度設(shè)置，只需根據(jù)Y值設(shè)置，根據(jù)參考文獻[13]可得長度應(yīng)為

(19)

這里用符號step表示跳變步長，n表示處理的級數(shù)，那么在處理長度為Y的數(shù)據(jù)時，跳變步長與級數(shù)關(guān)系為

(20)

當處理長度為F的數(shù)據(jù)時，如果F與Y值相同那么可按照式(20)計算步進長度，如果F

(21)

通過如上介紹方法便可完成旋轉(zhuǎn)因子的快速訪問，在進行數(shù)據(jù)訪問時每級處理需進行反序計算，這里可直接使用TS201處理其中的反序?qū)ぶ分噶? 獲取數(shù)據(jù)后便利用內(nèi)核的乘法器等資源完成蝶形運算. 為了充分發(fā)揮處理器的性能，程序中同時訪問兩個蝶形，分別放入x，y運算單元中，這樣可在同一刻進行兩個蝶形計算. 前面第2節(jié)介紹可知，合理安排流水后內(nèi)核計算應(yīng)隱藏在內(nèi)存訪問中，可把其作為優(yōu)化目標，對蝶形計算進行軟件流水建立，參考文獻[14]中詳細介紹了DSP排流水的方法，這里不再詳細介紹. 排完指令流水后結(jié)果如圖6所示.

如上便完成了每級蝶形流水線的建立，為了縮短處理時間，程序?qū)崿F(xiàn)中將列處理的最后一級蝶形計算單獨編寫，以便可以同乘補償因子操作融合在一起. 具體操作方法如前面所述.

程序優(yōu)化后對其進行測試結(jié)果如表1所示.

通過表1可以看出采用本文介紹的映射方法實現(xiàn)基2FFT，在小點數(shù)時(小于2 048點)處理時間比正常映射方式要長，原因是小點數(shù)處理可存在cache中(TS201cache可緩存2 048點浮點型復(fù)數(shù)點數(shù)據(jù))，在這種情況下采用本文介紹的映射方法會多出乘以補償因子的時間. 當處理的數(shù)據(jù)長度大于2 048點以后，由于本文的映射方法充分利用cache，處理時間要明顯優(yōu)于正常的映射方法，速度約提高1倍. 另外通過該表可以看出理論計算時間同實際測試時間相近，可驗證本文模型建立的正確性. 雖然表1所示正常映射方法中，大點數(shù)(2 048點)執(zhí)行時間與理論時間存在較大偏差，其原因是DSP內(nèi)部存儲器采用的是DRAM，訪問過程中在換頁情況下會額外引入頁激活時間，因此在換頁和數(shù)據(jù)丟失同時存在時，額外開銷要比手冊給出的時間長，而本文理論計算時額外開銷選取的只是手冊提供數(shù)值，故大點數(shù)處理情況下會存在一定偏差.

表1 FFT執(zhí)行時間對比表

4 結(jié) 論

針對雷達信號處理中常用的FFT算法到處理器上的映射進行研究. 首先分析了現(xiàn)代處理器的結(jié)構(gòu)特點，基于分析結(jié)果將與處理性能相關(guān)的因素參量化，建立了基于現(xiàn)代化處理器的程序執(zhí)行模型. 進而基于該模型對FFT算法在處理器上的執(zhí)行過程分析，得知處理中的內(nèi)存訪問是影響實時性的關(guān)鍵因素. 進一步研究FFT的內(nèi)訪問特點，并建立模型進行分析，發(fā)現(xiàn)cache命中率直接影響算法執(zhí)行的實時性. 對于采用正常映射的FFT方法，由于沒有充分利用cache，導致大點數(shù)處理時效率低. 為了提高命中率，文中實現(xiàn)了一種可拆分的FFT映射方法，其將大點數(shù)劃分成小點數(shù)處理，對cache進行充分利用，進而大大提高處理性能. 最后在TS201數(shù)字信號處理器上，以該映射方法為指導，實現(xiàn)了基2FFT算法，驗證了本文所提供映射方法的有效性，同時驗證了模型建立的正確性.

[1] Yang J， Xiong T， Peng Y. A fuzzy approach to filtering interferometric SAR data [J]. International Journal of Remote Sensing， 2007，28(6):1375-1382.

[2] Geer D. Chip makers turn to multicore processors[J]. Computer， 2005，38(5):11-13.

[3] Shen J P， Lipasti M H. Modern processor design: fundamentals of superscalar processors[M]. [S.l.]： Waveland Press， 2013.

[4] Suh G E， Rudolph L， Devadas S. Dynamic partitioning of shared cache memory[J]. The Journal of Supercomputing， 2004，28(1):7-26.

[5] Mazreah A A， Shalmani M T M. Low-leakage soft error tolerant dual-port SRAM cells for cache memory applications [J]. Microelectronics Journal， 2012，43(11):766-792.

[6] 范長永.32位RISC微處理器模塊設(shè)計[D].北京：北京工業(yè)大學，2003.

Fan Changyong. 32 bit microprocessor module design[D]. Beijing: Beijing University of Technology， 2003. (in Chinese)

[7] Austin T， Larson E， Ernst D. Simple Scalar: an infrastructure for computer system modeling[J]. Computer， 2002，35(2):59-67.

[8] Benedetto S， Montorsi G. Unveiling turbo codes: some results on parallel concatenated coding schemes[J]. IEEE Transactions on Information Theory， 1996，42(2):409-428.

[9] 劉莉，高梅國，周閏,等.大點數(shù)FFT的多DSPs并行處理算法及實現(xiàn)[J].系統(tǒng)工程與電子技術(shù)，2003，25(10):1193-1196.

Liu Li， Gao Meiguo， Zhou Run, et al. Algorithm and implementation of a large-point FFT under the master-slave parallel multi-processor architecture[J]. Systems Engineering and Electronics, 2003，25(10):1193-1196. (in Chinese)

[10] 喬樹山，黑勇，吳斌,等.塊浮點FFT處理器的有限字長效應(yīng)分析[J].電子科技大學學報，2008，37(1):58-60.

Qiao Shushan， Hei Yong, Wu Bin, et al. Finite word-length effects in implementation of a block floating-point FFT processor[J]. Journal of UEST of China, 2008，37(1):58-60. (in Chinese)

[11] Yi J J， Eeckhout L， Lilja D J， et al. The future of simulation: a field of dreams[J]. Computer， 2006，39(11):22-29.

[12] Magnusson P S， Christensson M， Eskilson J， et al. Simics: a full system simulation platform[J]. Computer， 2002，35(2):50-58.

[13] 王世一.數(shù)字信號處理[M].北京：北京理工大學出版社，1997.

Wang Shiyi. Digital signal processing[M]. Beijing: Publishing House of Electronics Industry， 1997. (in Chinese)

[14] 李方慧，王飛，何佩琨.TMS320C6000系列DSPs原理與應(yīng)用[M]. 北京：電子工業(yè)出版社，2003.

Li Fanghui, Wang Fei, He Peikun. Principle and application of TMS320C6000 series DSPs[M]. Beijing: Publishing House of Electronics Industry, 2003. (in Chinese)

(責任編輯：劉芳)

An Efficient FFT-Mapping Method Based on Superscalar Processor

GAO Li-ning，ZHU Liang，LIU Teng-fei，LIU Feng

(School of Information and Electronics， Beijing Institute of Technology， Beijing 100081， China)

Considering the technology background and the structure characteristic of superscalar processor, novel mapping method was studied to implement the FFT effectively. Firstly, the structure of modern superscalar processor was modeled, and then the effect of FFT implementation on the processor was analyzed. The analysis results show that the EMS memory accessing is the key point of FFT algorithm implementation. Further more, the accessing process of FFT processing was modeled to implement FFT mapping effectively based on cache optimization. The new mapping method splits sequence of FFT into short sequence to exert the function of cache sufficiently. Finally, a radix-2 FFT was implemented on the ADI’s TS201 digital signal processor based on the new mapping method. The result shows that the implementation time of FFT is improved greatly.

fast Fourier transform (FFT); cache; superscalar processor

2015-04-02

國家自然科學基金資助項目(61370017)

高立寧(19XX—)，男，講師，碩士生導師，E-mail:gaolining@bit.edu.cn.

TB 114.3

A

1001-0645(2016)09-0940-08

10.15918/j.tbit1001-0645.2016.09.011