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