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