一種偶數基Cooley-Tukey FFT高性能實現方法
關鍵詞：快速傅里葉變換算法 偶數基 蝶形計算優化 蝶形網絡優化 simd匯編優化
摘要：快速傅里葉變換(Fast Fourier Transform,FFT)是最重要的基礎算法之一,在科學計算、信號處理、圖像處理等領域都有著廣泛的應用。隨著這些應用領域對實時性需求的進一步提高,FFT算法面臨著越來越高的性能要求。在現有的FFT算法庫中,FFT算法的求解速度和計算精度受到一定程度的限制,而且也少有研究者對偶數基Cooley-Tukey FFT的高性能實現提出相應的優化策略并對技術進行深入研究。基于此,文中提出了一套針對偶數基的Cooley-Tukey FFT的優化策略和方法。首先構建一個SIMD(Single Instruction Multiple Data)友好、支持混合基的蝶形網絡,然后根據偶數基旋轉因子特性最大限度地降低蝶形計算的復雜度,接著通過SIMD匯編優化、匯編指令重排及選擇、寄存器分配策略制定、高性能矩陣轉置算法等方法來優化應用,最后實現一個高性能的FFT算法庫。目前,最流行、應用最廣的FFT有FFTW和Intel MKL。實驗結果表明,在X86計算平臺上,新提出的這套針對偶數基Cooley-Tukey FFT的技術所實現的FFT算法庫的性能全面優于MKL和FFTW。所提出的這套高性能算法優化和實現技術體系,可推廣到除偶數基以外的其他基的實現和優化上,為進一步的研究開發工作奠定一定的基礎,進而突破FFT算法在硬件平臺上的性能瓶頸,實現一套針對特定平臺的高性能FFT算法庫。
計算機科學雜志要求:
{1}正文公式的序號一律靠右空兩格，用(1)、(2)、(3)等表示。
{2}請勿一稿多投，三個月沒有得到用稿通知，可自行處理。
{3}來稿一律文責自負。依照《著作權法》有關規定，本刊可對來稿做文字修改、刪節及圖像處理。凡有涉及原意的修改，則征求作者意見。修改稿逾3個月不寄回者，視作自動撤稿。
{4}標題序號按照“一”、“（一）”、“1”、“第一”或“首先”順序排列，一般不用“①”號。根據文章具體內容，序號可適當減少，但不可反順序使用。
{5}文末注明聯系電話、詳細單位地址郵編。
注：因版權方要求，不能公開全文，如需全文，請咨詢雜志社
