[發(fā)明專利]多粒度并行FFT計(jì)算裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 201110459907.0
• 申請(qǐng)日: 2011-12-31
• 公開（公告）號(hào): CN102411557A
• 公開（公告）日: 2012-04-11
• 發(fā)明（設(shè)計(jì)）人: 王東琳;謝少林;蒿杰;林嘯;汪濤;尹磊祖
• 申請(qǐng)（專利權(quán)）人: 中國(guó)科學(xué)院自動(dòng)化研究所
• 主分類號(hào): G06F17/14
• 分類號(hào): G06F17/14
• 代理公司: 中科專利商標(biāo)代理有限責(zé)任公司 11021
• 代理人: 周國(guó)城

技術(shù)領(lǐng)域

本發(fā)明涉及集成電路設(shè)計(jì)領(lǐng)域中的快速傅立葉變換(FFT)數(shù)據(jù)的并行存儲(chǔ)、并行讀寫及并行計(jì)算。

背景技術(shù)

信號(hào)處理系統(tǒng)經(jīng)常需要將信號(hào)內(nèi)容在時(shí)域和頻域進(jìn)行轉(zhuǎn)換，快速傅立葉變換算法(FFT)可進(jìn)行時(shí)域和頻域間的信號(hào)轉(zhuǎn)換。相對(duì)于其它轉(zhuǎn)換算法來說，快速傅立葉變換算法具有結(jié)構(gòu)統(tǒng)一、計(jì)算量少的優(yōu)點(diǎn)，因此廣泛應(yīng)用于信號(hào)處理系統(tǒng)中。

FFT算法輸入N個(gè)數(shù)據(jù)，輸出N個(gè)數(shù)據(jù)；一般稱時(shí)域至頻域的變換為正向變換，而頻域至?xí)r域的變換變逆向變換。FFT算法有多種實(shí)現(xiàn)方式，但都由庫(kù)利-圖基算法演變而來。對(duì)于N個(gè)數(shù)據(jù)點(diǎn)，基2的庫(kù)利-圖基算法包括log₂N個(gè)計(jì)算級(jí)。每個(gè)計(jì)算級(jí)輸入N個(gè)數(shù)，輸出N個(gè)數(shù)；前一計(jì)算級(jí)的輸出經(jīng)過一定的排序后作為后一計(jì)算級(jí)的輸入。第一級(jí)輸入為原始數(shù)據(jù)，最后一級(jí)輸出為FFT計(jì)算結(jié)果，如圖1所示。圖1中假定數(shù)據(jù)點(diǎn)長(zhǎng)度為8，整個(gè)計(jì)算過程需要計(jì)算三個(gè)計(jì)算級(jí)103：S0、S1、S2。

每個(gè)計(jì)算級(jí)103由N/2個(gè)蝶形(102)組成，蝶形計(jì)算的計(jì)算結(jié)構(gòu)如圖2所示。每個(gè)蝶形計(jì)算輸入兩個(gè)數(shù)據(jù)點(diǎn)A和B，以及一個(gè)旋轉(zhuǎn)因子W，得到兩個(gè)計(jì)算結(jié)果：A+BW和A-BW。在每個(gè)蝶形計(jì)算中，輸入數(shù)據(jù)A和B的序號(hào)具有確定的對(duì)應(yīng)關(guān)系，該對(duì)應(yīng)關(guān)系由蝶形所在的計(jì)算級(jí)以及輸入數(shù)據(jù)A或B的序號(hào)來確定；同時(shí)，旋轉(zhuǎn)因子W的值由當(dāng)前蝶形所在的計(jì)算級(jí)103、輸入數(shù)據(jù)A或B的序號(hào)以及FFT的數(shù)據(jù)長(zhǎng)度確定。例如在圖1中，S0計(jì)算級(jí)中的第1個(gè)數(shù)據(jù)必定與第0個(gè)數(shù)據(jù)構(gòu)成一蝶形，并且第0個(gè)數(shù)據(jù)為蝶形輸入的A，第1個(gè)數(shù)據(jù)為蝶形輸入的B，而W的值為1。而S1計(jì)算級(jí)中的第1個(gè)數(shù)據(jù)必定與第3個(gè)數(shù)據(jù)構(gòu)成一蝶形，并且第1個(gè)數(shù)據(jù)為蝶形輸入的A，第3個(gè)數(shù)據(jù)為蝶形輸入的B，而W的值為1。

蝶形計(jì)算的計(jì)算級(jí)之間存在數(shù)據(jù)相關(guān)，后一計(jì)算級(jí)必須等待前一計(jì)算級(jí)完成以后才能開始計(jì)算。因此，每級(jí)計(jì)算完成后都需要將結(jié)果存放在存儲(chǔ)器中，下一級(jí)計(jì)算從存儲(chǔ)器中讀取上一級(jí)的計(jì)算結(jié)果作為本計(jì)算級(jí)計(jì)算的輸入。計(jì)算級(jí)內(nèi)的蝶形相互獨(dú)立，蝶形的計(jì)算順序不影響計(jì)算結(jié)果，但每個(gè)蝶形所讀取的數(shù)據(jù)A、B和旋轉(zhuǎn)因子W必須滿足內(nèi)在的對(duì)應(yīng)關(guān)系。

在并行FFT計(jì)算中，運(yùn)算部件從多粒度并行存儲(chǔ)器中讀取多個(gè)蝶形所需數(shù)據(jù)及對(duì)應(yīng)的旋轉(zhuǎn)因子，并行計(jì)算多個(gè)、多級(jí)蝶形，然后將計(jì)算結(jié)果并行寫入存儲(chǔ)器，以便進(jìn)行一下級(jí)計(jì)算，如圖3所示。

圖3中，假定數(shù)據(jù)長(zhǎng)度為64，并行粒度為4，即多粒度并行存儲(chǔ)器300一次可讀寫4個(gè)數(shù)據(jù)。此時(shí)，兩相鄰計(jì)算級(jí)中存在數(shù)據(jù)相關(guān)的4個(gè)蝶形303構(gòu)成一個(gè)蝶形組302，兩相鄰計(jì)算級(jí)中的蝶形組構(gòu)成一計(jì)算節(jié)301。在蝶形組302中，每個(gè)蝶形的輸入A、B、W仍必須滿足其內(nèi)在的對(duì)應(yīng)關(guān)系，因此，并行FFT算法中必須考慮計(jì)算數(shù)據(jù)和旋轉(zhuǎn)因子在存儲(chǔ)器中的分布，以及每個(gè)蝶形組302的讀寫地址和讀寫方式，以保證蝶形計(jì)算裝置每次都能并行讀取所需數(shù)據(jù)和旋轉(zhuǎn)因子。

大部分并行FFT算法相關(guān)的專利都著重討論如何將長(zhǎng)序列的FFT數(shù)據(jù)分解成多個(gè)短序列的FFT，利用多個(gè)處理器并行計(jì)算各個(gè)短序列的FFT，最后對(duì)多個(gè)短序列的FFT進(jìn)行交織計(jì)算，得到最終的長(zhǎng)序列FFT結(jié)果。

如美國(guó)專利US?6,792,441?B2(Parallel?MultiProcessing?For?Fast?Fourier?Transform?With?Pipeline?Architecture)。這一類算法都沒考慮多個(gè)處理單元同時(shí)訪問存儲(chǔ)器時(shí)的沖突問題，以及多個(gè)處理器如何交織多個(gè)短序列FFT結(jié)果。而實(shí)際應(yīng)用中，存儲(chǔ)器訪問沖突以及處理器之間的同步和通信效率將嚴(yán)重影響FFT的計(jì)算效率。

美國(guó)專利US?6,304,887?B1(FFT-Based?Parallel?System?For?Array?Processing?With?Low?Latency)討論了FFT算法中數(shù)據(jù)并行讀寫的問題，該專利將FFT數(shù)據(jù)存放在多個(gè)存儲(chǔ)器中，利用多個(gè)數(shù)據(jù)緩沖區(qū)、多個(gè)選擇器對(duì)數(shù)據(jù)進(jìn)行排序，以保證每次讀寫的數(shù)據(jù)分布在不同的存儲(chǔ)器中，實(shí)現(xiàn)并行讀寫。但該專利需要專用的存儲(chǔ)器、數(shù)據(jù)緩沖區(qū)和選擇器，讀寫地址計(jì)算復(fù)雜，難以實(shí)現(xiàn)不同數(shù)據(jù)長(zhǎng)度、不同讀寫粒度的并行FFT算法。

發(fā)明內(nèi)容

(一)要解決的技術(shù)問題

本發(fā)明要解決的技術(shù)問題實(shí)現(xiàn)對(duì)不同數(shù)據(jù)算度、不同讀寫粒度的FFT計(jì)算的支持，并提高FFT計(jì)算裝置的計(jì)算效率，。

(二)技術(shù)方案