無(wú)線通信系統(tǒng)-FFT與信道譯碼VLSI設(shè)計(jì) 課件 第3章 基于單端口存儲(chǔ)器的FFT處理器及VLSI結(jié)構(gòu)

第3章基于單端口存儲(chǔ)器的FFT處理器及VLSI結(jié)構(gòu)3.1FFT處理器頂層架構(gòu)設(shè)計(jì)3.2FFT處理器數(shù)據(jù)訪問(wèn)方案設(shè)計(jì)3.3FFT處理器VLSI結(jié)構(gòu)設(shè)計(jì)3.4理論分析與硬件測(cè)試本章小結(jié)

3.1FFT處理器頂層架構(gòu)設(shè)計(jì)

一般地，radix-2kFFT算法通過(guò)

級(jí)的radix-2k蝶形計(jì)算來(lái)完成N=2n點(diǎn)的FFT運(yùn)算，其中

表示向上取整運(yùn)算符。各級(jí)采用的蝶形運(yùn)算階數(shù)

分別為：

(3.1)

為便于討論，這里還定義k0=0。令表

示數(shù)據(jù)索引，相應(yīng)地在radix-2k信號(hào)流圖中，F(xiàn)FT輸入數(shù)據(jù)、計(jì)算結(jié)果以及每一級(jí)的操作數(shù)均按從上至下的方式利用數(shù)據(jù)索引依次編號(hào)。第m級(jí)運(yùn)算的操作數(shù)構(gòu)成了

個(gè)radix-蝶形，第t+1個(gè)蝶形（

）包含的數(shù)據(jù)索引構(gòu)成向量

(3.2)

其中

，

表示為

同時(shí)，公式(3.2)中的數(shù)組Im定義為：

其中

表示在

范圍內(nèi)以

為增量的整數(shù)序列。

Radix-2k蝶形運(yùn)算的實(shí)現(xiàn)方式有多種，除了直接根據(jù)信號(hào)流圖布設(shè)加法器、乘法器并進(jìn)行電路互聯(lián)外，還可以基于多路延遲換向（multipathdelaycommutator,MDC）結(jié)構(gòu)來(lái)實(shí)現(xiàn)，此時(shí)每個(gè)MDC結(jié)構(gòu)獨(dú)立執(zhí)行radix-2k蝶形運(yùn)算。MDC結(jié)構(gòu)的輸入與輸出數(shù)據(jù)均為2路并行方式，當(dāng)計(jì)算與bm.t相關(guān)的蝶形時(shí)，MDC結(jié)構(gòu)輸入數(shù)據(jù)對(duì)應(yīng)的數(shù)據(jù)索引為

(3.4)

其中

利用向量x的元素依次填充u×v維矩陣的每一列，產(chǎn)生一個(gè)u×v維的矩陣。

的第一行和第二行分別描述了MDC結(jié)構(gòu)上支路和下支路的輸入數(shù)據(jù)順序。MDC結(jié)構(gòu)輸出數(shù)據(jù)對(duì)應(yīng)的數(shù)據(jù)索引為：

(3.5)

類似地，

的第一行和第二行表示上支路和下支路的輸出數(shù)據(jù)次序。

基于存儲(chǔ)器的radix-2kFFT處理器頂層設(shè)計(jì)方案如圖3.1所示，主要由處理單元、數(shù)據(jù)訪問(wèn)單元、數(shù)據(jù)緩存單元、數(shù)據(jù)次序變換單元以及輸入輸出轉(zhuǎn)換單元五部分構(gòu)成，其中數(shù)據(jù)訪問(wèn)單元和數(shù)據(jù)次序變換單元作為橋梁控制數(shù)據(jù)讀寫，用于連通FFT處理器的處理單元與數(shù)據(jù)緩存單元。

圖3.1基于存儲(chǔ)器的radix-2kFFT處理器頂層架構(gòu)

圖3.2以

為例給出了處理單元的底層詳細(xì)硬件結(jié)構(gòu)，除了執(zhí)行蝶形運(yùn)算的MDC結(jié)構(gòu)外，在處理單元數(shù)據(jù)輸出側(cè)還排列了一組復(fù)數(shù)乘法器，用于對(duì)蝶形運(yùn)算結(jié)果進(jìn)行旋轉(zhuǎn)因子加權(quán)。

圖3.2基于MDC計(jì)算電路的處理單元結(jié)構(gòu)

FFT處理器的數(shù)據(jù)調(diào)度流程如圖3.3所示。圖3.3FFT處理器數(shù)據(jù)調(diào)度流程

3.2FFT處理器數(shù)據(jù)訪問(wèn)方案設(shè)計(jì)

與CPU中算術(shù)邏輯單元與數(shù)據(jù)緩存的關(guān)系類似，在基于存儲(chǔ)器的FFT處理器中，對(duì)處理單元于數(shù)據(jù)緩存單元之間的數(shù)據(jù)存取操作進(jìn)行沖突消解，是保證FFT處理器高吞吐量運(yùn)行的關(guān)鍵。圖3.4以并行度為4的32點(diǎn)radix-22FFT計(jì)算為例，展示了不同數(shù)據(jù)訪問(wèn)方案下的計(jì)算流程，其中灰色格點(diǎn)表示數(shù)據(jù)訪問(wèn)存在沖突。

圖3.4并行度為4的32點(diǎn)radix-22FFT在不同數(shù)據(jù)訪問(wèn)方案下的計(jì)算流程

3.2.1輸入數(shù)據(jù)緩存方案

輸入數(shù)據(jù)首先通過(guò)輸入輸出轉(zhuǎn)換單元將q路并行轉(zhuǎn)換為pc路并行，然后以pc路并行的方式寫入數(shù)據(jù)緩存單元，其數(shù)據(jù)次序可以表示為

(3.6)

3.2.2中間計(jì)算結(jié)果存取方案

對(duì)于第m級(jí)（

）的蝶形運(yùn)算，處理單元每次會(huì)從數(shù)據(jù)緩存單元讀取pc個(gè)數(shù)據(jù)，這些數(shù)據(jù)分屬于pc/2個(gè)radix-蝶形，并依托處理單元內(nèi)的pc/2個(gè)MDC運(yùn)算結(jié)構(gòu)分別進(jìn)行處理。用

分別表示同時(shí)處理的pc/2個(gè)radix-蝶形對(duì)應(yīng)的數(shù)據(jù)索引向量，其中t屬于數(shù)組

(3.9)

公式(3.7)既描述了輸入數(shù)據(jù)的緩存方法，同時(shí)也是FFT第1級(jí)操作數(shù)的緩存方法。對(duì)于第m級(jí)（

）的蝶形計(jì)算，其操作數(shù)緩存方式為

(3.15)

值得注意的是，這里第2級(jí)至第M-1級(jí)蝶形運(yùn)算操作數(shù)的緩存方式，實(shí)際也是第1級(jí)至第M-2級(jí)蝶形運(yùn)算計(jì)算結(jié)果的緩存方式。

基于(3.15)的數(shù)據(jù)存儲(chǔ)方式，可以滿足第1級(jí)至第M-2級(jí)計(jì)算過(guò)程中的數(shù)據(jù)無(wú)沖突訪問(wèn)，具體總結(jié)如下：

定理3.1：若第m級(jí)（

）的數(shù)據(jù)讀取和數(shù)據(jù)寫入次序分別為

，那么

1）第1級(jí)的數(shù)據(jù)無(wú)沖突訪問(wèn)要求數(shù)據(jù)讀取基于(3.7)執(zhí)行，蝶形運(yùn)算結(jié)果寫入基于m=2情況下的(3.15)執(zhí)行；

2）第u級(jí)（

）的無(wú)沖突數(shù)據(jù)訪問(wèn)要求數(shù)據(jù)讀取基于m=u情況下的(3.15)執(zhí)行，蝶形運(yùn)算結(jié)果寫入基于m=u+1情況下的(3.15)執(zhí)行，并且數(shù)據(jù)寫入與數(shù)據(jù)讀取操作之間的延遲為

個(gè)時(shí)鐘周期。

與前M-1級(jí)不同，第M-1級(jí)蝶形運(yùn)算結(jié)果按照如下方式存儲(chǔ)在數(shù)據(jù)緩存單元中：

定理3.2：若第M-1級(jí)數(shù)據(jù)讀取和數(shù)據(jù)寫入次序分別為

，那么其無(wú)沖突數(shù)據(jù)訪問(wèn)要求數(shù)據(jù)讀取基于m=M-1情況下的(3.15)執(zhí)行，數(shù)據(jù)寫入基于(3.16)執(zhí)行，并且數(shù)據(jù)寫入與數(shù)據(jù)讀取操作之間的延遲為

個(gè)時(shí)鐘周期。

定理3.3：若第M級(jí)數(shù)據(jù)讀取和數(shù)據(jù)寫入次序分別為

，那么其無(wú)沖突數(shù)據(jù)訪問(wèn)要求數(shù)據(jù)讀取基于(3.16)執(zhí)行，數(shù)據(jù)寫入基于(3.23)執(zhí)行，并且對(duì)于前N/2個(gè)數(shù)據(jù)，數(shù)據(jù)寫入與數(shù)據(jù)讀取操作之間的延遲為

個(gè)時(shí)鐘周期，對(duì)于后N/2個(gè)數(shù)據(jù)，數(shù)據(jù)寫入與數(shù)據(jù)讀取操作之間的延遲為2k+1個(gè)時(shí)鐘周期。

因此的具體表達(dá)式為

進(jìn)而基于(3.23)，可以確定數(shù)據(jù)緩存單元寫入?yún)?shù)的表達(dá)式為

3.2.3輸出數(shù)據(jù)讀取方案

用

來(lái)表示以pc路并行的方式來(lái)從數(shù)據(jù)緩存單元中讀取計(jì)算結(jié)果的數(shù)據(jù)次序，其形式與(3.6)中

的形式相同。通過(guò)輸入輸出轉(zhuǎn)換單元的數(shù)據(jù)速率變換，F(xiàn)FT計(jì)算結(jié)果的輸出并行度變?yōu)閝，與輸入數(shù)據(jù)的并行度保持一致。由于處理單元輸出的計(jì)算結(jié)果以倒位序方式排序，并且基于映射規(guī)則(3.23)存儲(chǔ)在數(shù)據(jù)緩存單元中，通過(guò)將(3.23)中的數(shù)據(jù)索引d替換為

，并利用

，從數(shù)據(jù)緩存單元中讀取自然序排列的FFT計(jì)算結(jié)果，應(yīng)當(dāng)遵循的映射規(guī)則為

此外，這里所設(shè)計(jì)的映射規(guī)則能夠允許FFT計(jì)算結(jié)果讀取與新數(shù)據(jù)寫入在數(shù)據(jù)緩存單元內(nèi)并發(fā)執(zhí)行，這使得FFT處理器不必為輸入數(shù)據(jù)和待輸出數(shù)據(jù)配置獨(dú)立的存儲(chǔ)資源，將輸入緩沖區(qū)與輸出緩沖區(qū)混合，從而顯著降低無(wú)沖突數(shù)據(jù)存取所對(duì)應(yīng)的存儲(chǔ)開銷。具體而言，當(dāng)數(shù)據(jù)緩存單元中的兩塊RAM在數(shù)據(jù)讀取模式下輸出FFT計(jì)算結(jié)果時(shí)，另外兩塊RAM可以工作在輸入寫入模式下，利用已經(jīng)釋放的RAM存儲(chǔ)空間來(lái)接收新數(shù)據(jù)。FFT計(jì)算結(jié)果讀取與新數(shù)據(jù)寫入的并發(fā)操作需要輸入數(shù)據(jù)在緩存時(shí)使用與FFT計(jì)算結(jié)果讀取相同的映射規(guī)則。

通過(guò)比較(3.8)和(3.25)，這兩個(gè)映射規(guī)則以相同的方式生成i和j，而物理地址a的生成僅在N=22k或N=22k-1時(shí)相同。而當(dāng)N>22k時(shí)，通過(guò)移除(3.25)中的

操作，物理地址a可以轉(zhuǎn)換為

舉例：假設(shè)FFT處理器采用radix-22算法執(zhí)行4路并行的64點(diǎn)FFT運(yùn)算，即N=64

，Pc=4

。整個(gè)計(jì)算分為三級(jí)，算法階數(shù)設(shè)置為

。圖3.5詳細(xì)描述了FFT并行計(jì)算過(guò)程中輸入數(shù)據(jù)次序、處理單元輸入與輸出數(shù)據(jù)流的數(shù)據(jù)次序，以及數(shù)據(jù)緩存單元的4塊單端口RAM內(nèi)數(shù)據(jù)的排列方式，。通過(guò)圖3.5可以直觀反映出(3.9)、(3.18)規(guī)定的蝶形處理次序，以及(3.17)和(3.22)中的數(shù)據(jù)重排操作給數(shù)據(jù)次序帶來(lái)的影響。

圖3.5FFT處理器無(wú)沖突數(shù)據(jù)訪問(wèn)流程示意圖（以64點(diǎn)的4路并行FFT計(jì)算為例）

3.3FFT處理器VLSI結(jié)構(gòu)設(shè)計(jì)

以上三種運(yùn)算覆蓋了數(shù)據(jù)映射規(guī)則中的基本運(yùn)算類型，這表明數(shù)據(jù)訪問(wèn)參數(shù)i，j和a的可以通過(guò)數(shù)據(jù)位的調(diào)整來(lái)生成。為了說(shuō)明這一點(diǎn)，我們首先對(duì)前M-2級(jí)計(jì)算中的數(shù)據(jù)訪問(wèn)次序進(jìn)行討論。如圖3.6所示。

圖3.6通過(guò)對(duì)計(jì)數(shù)器劃分的數(shù)據(jù)段重排來(lái)產(chǎn)生前M-2級(jí)數(shù)據(jù)訪問(wèn)索引

對(duì)于第M-1級(jí)計(jì)算，包含log2N比特的二進(jìn)制計(jì)數(shù)器被劃分為5段，從最高位開始數(shù)據(jù)段長(zhǎng)度分別為

比特、1比特、

比特、1比特和k-1比特，如圖3.7所示。注意當(dāng)M=2時(shí)需要略去第一個(gè)數(shù)據(jù)段，因?yàn)榇藭r(shí)其長(zhǎng)度為

。依據(jù)定理3.2的推導(dǎo)結(jié)果，可通過(guò)對(duì)劃分后數(shù)據(jù)段進(jìn)行次序調(diào)整來(lái)產(chǎn)生

對(duì)應(yīng)的數(shù)據(jù)索引。

圖3.7通過(guò)對(duì)計(jì)數(shù)器劃分的數(shù)據(jù)段重排來(lái)產(chǎn)生第

級(jí)數(shù)據(jù)訪問(wèn)索引

對(duì)于第M級(jí)FFT計(jì)算，計(jì)數(shù)器被劃分為6個(gè)數(shù)據(jù)段，從最高位開始數(shù)據(jù)段長(zhǎng)度分別為1比特、

比特、1比特、k-1比特、1比特和k-1比特，其中包含單一比特位的第1段和第3段通過(guò)異或運(yùn)算進(jìn)一步產(chǎn)生新的輔助數(shù)據(jù)段。依據(jù)定理3.3的推導(dǎo)結(jié)果，通過(guò)對(duì)計(jì)數(shù)器中的6個(gè)數(shù)據(jù)段以及輔助數(shù)據(jù)段進(jìn)行重新排列，可以產(chǎn)生數(shù)據(jù)索引

，如圖3.8所示。

圖3.8通過(guò)對(duì)計(jì)數(shù)器劃分的數(shù)據(jù)段重排來(lái)產(chǎn)生第M級(jí)數(shù)據(jù)訪問(wèn)索引

圖3.8通過(guò)對(duì)計(jì)數(shù)器劃分的數(shù)據(jù)段重排來(lái)產(chǎn)生第M級(jí)數(shù)據(jù)訪問(wèn)索引

通過(guò)數(shù)據(jù)段調(diào)整來(lái)得到數(shù)據(jù)索引后，可以根據(jù)映射規(guī)則確定數(shù)據(jù)訪問(wèn)所需的RAM標(biāo)識(shí)符

與物理地址

。如圖3.9所示，數(shù)據(jù)訪問(wèn)參數(shù)的生成只涉及到數(shù)據(jù)截位和邏輯異或操作。

圖3.9基于給定的數(shù)據(jù)訪問(wèn)索引產(chǎn)生數(shù)據(jù)訪問(wèn)參數(shù)的方式

圖3.9基于給定的數(shù)據(jù)訪問(wèn)索引產(chǎn)生數(shù)據(jù)訪問(wèn)參數(shù)的方式

3.3.2輸入輸出轉(zhuǎn)換單元及數(shù)據(jù)次序變換單元

輸入輸出轉(zhuǎn)換單元的VLSI實(shí)現(xiàn)結(jié)構(gòu)如圖3.10所示，其作用是完成

路并行輸入/輸出數(shù)據(jù)與pc路數(shù)據(jù)緩存單元并行讀寫數(shù)據(jù)之間的并行度轉(zhuǎn)換。

圖3.10輸入輸出轉(zhuǎn)換單元VLSI實(shí)現(xiàn)結(jié)構(gòu)

數(shù)據(jù)次序變換單元用于對(duì)處理單元輸入數(shù)據(jù)次序進(jìn)行調(diào)節(jié)，并對(duì)處理單元輸出數(shù)據(jù)進(jìn)行重新排序，以保證在第M-1級(jí)和第M級(jí)計(jì)算過(guò)程中能夠?qū)?shù)據(jù)緩存單元進(jìn)行無(wú)沖突訪問(wèn)。數(shù)據(jù)次序變換單元的硬件結(jié)構(gòu)如圖3.11所示，包括數(shù)據(jù)轉(zhuǎn)置模塊和延遲換向模塊兩個(gè)部分。

圖3.11數(shù)據(jù)次序變換單元VLSI實(shí)現(xiàn)結(jié)構(gòu)

3.3.3混合抽取多路延遲反饋VLSI結(jié)構(gòu)設(shè)計(jì)

從圖3.1的頂層設(shè)計(jì)方案可以看出，處理單元在MDC計(jì)算結(jié)構(gòu)輸出端部署復(fù)數(shù)乘法器，用于對(duì)計(jì)算結(jié)果進(jìn)行旋轉(zhuǎn)因子加權(quán)。旋轉(zhuǎn)因子加權(quán)不改變數(shù)據(jù)索引，即加權(quán)前后的數(shù)據(jù)對(duì)應(yīng)的數(shù)據(jù)索引相同。對(duì)于第m級(jí)運(yùn)算，用

表示處理單元某個(gè)輸出數(shù)據(jù)的數(shù)據(jù)索引，那么用于對(duì)該數(shù)據(jù)進(jìn)行加權(quán)的旋轉(zhuǎn)因子表示為：

由于處理單元在執(zhí)行第M級(jí)運(yùn)算時(shí)，MDC計(jì)算結(jié)構(gòu)的輸出不必乘以旋轉(zhuǎn)因子，我們重點(diǎn)考慮前M-1級(jí)運(yùn)算過(guò)程中的旋轉(zhuǎn)因子的快速生成。具體而言，在第m級(jí)（

）可將(3.26)中的數(shù)據(jù)索引d例化為

。參照?qǐng)D3.6和圖3.7中基于數(shù)據(jù)段分割與重排方法生成的

格式，可以快速生成(3.26)中旋轉(zhuǎn)因子復(fù)指數(shù)項(xiàng)的分子部分作為旋轉(zhuǎn)因子的訪問(wèn)索引，如圖3.12所示。

圖3.12旋轉(zhuǎn)因子訪問(wèn)索引生成方式（以第1至第M-1級(jí)計(jì)算涉及的旋轉(zhuǎn)因子為例）

3.4理論分析與硬件測(cè)試

3.4.1FFT處理器性能及資源消耗估計(jì)與比較

表3.1總結(jié)了所設(shè)計(jì)的FFT處理器在FFT計(jì)算長(zhǎng)度為N=2n、數(shù)據(jù)輸入與計(jì)算結(jié)果輸出并行度為q、計(jì)算并行度為pc=2k情況下的硬件開銷，并同時(shí)評(píng)估了計(jì)算延遲與吞吐量。

在處理性能上，F(xiàn)FT處理器的計(jì)算延遲被定義為處理器接收第一個(gè)有效輸入數(shù)據(jù)到提供第一個(gè)有效輸出數(shù)據(jù)之間的時(shí)間間隔，其數(shù)值為

根據(jù)圖3.3(a)給出的數(shù)據(jù)調(diào)度流程，當(dāng)FFT處理器部署一個(gè)數(shù)據(jù)緩存單元時(shí)，以時(shí)鐘速率為單位的吞吐量可表示為

這里假設(shè)FFT在開始輸出計(jì)算結(jié)果的同時(shí)立刻接收新的數(shù)據(jù)。當(dāng)FFT處理器部署兩個(gè)數(shù)據(jù)緩存單元時(shí)，處理單元在執(zhí)行FFT運(yùn)算時(shí)即可接收新的數(shù)據(jù)，此時(shí)吞吐量進(jìn)一步提升至

表3.2將所設(shè)計(jì)的FFT處理器與現(xiàn)有設(shè)計(jì)方案進(jìn)行了比較。在計(jì)算并行度為2的冪次的各類FFT處理器中，所提方案支持的計(jì)算并行度高于一般基于單端口RAM的FFT處理器，與基于雙端口RAM的FFT處理器性能保持一致。

3.4.2FFT處理器硬件實(shí)現(xiàn)與測(cè)試

我們首先利用速度等級(jí)為-3的XilinxFPGA對(duì)FFT處理器進(jìn)行原型測(cè)試。這里FPGA型號(hào)為Kintex7XC7K325T，所采用的編譯器為Vivado2015.2，在該測(cè)試中文獻(xiàn)[22]和[24]的FFT處理器VLSI實(shí)現(xiàn)結(jié)構(gòu)作為對(duì)比方案。與本章基于MDC計(jì)算結(jié)構(gòu)搭建的處理單元不同，對(duì)比方案直接基于radix-r（

r=pc）信號(hào)流圖結(jié)構(gòu)來(lái)實(shí)現(xiàn)并行度為pc的處理單元。三種用于測(cè)試的FFT處理器的數(shù)據(jù)緩存開銷均為N個(gè)復(fù)數(shù)存儲(chǔ)單元，但對(duì)應(yīng)的RAM模塊數(shù)量和存儲(chǔ)深度各不相同。FFT處理器中的通用復(fù)數(shù)乘法器和常數(shù)復(fù)數(shù)乘法器均基于FPGA內(nèi)的DSP48E乘法單元實(shí)現(xiàn)，其中每個(gè)復(fù)數(shù)乘法器消耗3個(gè)DSP48E乘法單元。

此外，盡管兩個(gè)對(duì)比方案是面向的是數(shù)據(jù)串行輸入與計(jì)算結(jié)果串行輸出的場(chǎng)景，而文獻(xiàn)[24]中的FFT處理器內(nèi)支持輸入/輸出并行度擴(kuò)展到pc，同時(shí)文獻(xiàn)[24]中的FFT處理器也可以支持2路并行的數(shù)據(jù)輸入與輸出，這些因素在評(píng)估FFT處理器吞吐量時(shí)會(huì)被一并考慮。不同F(xiàn)FT處理器占用的FPGAslice數(shù)量與可以達(dá)到的數(shù)據(jù)吞吐量如圖3.13所示。表3.3以N=16384，pc=16,為例對(duì)FFT處理器再FPGA上的實(shí)現(xiàn)情況進(jìn)行了詳細(xì)的統(tǒng)計(jì)。

圖3.13不同F(xiàn)FT處理器占用的FPGAslice數(shù)量與可以達(dá)到的數(shù)據(jù)吞吐量關(guān)系圖

根據(jù)FPGA測(cè)試結(jié)果，F(xiàn)FT處理器所占用的slice資源主要用于實(shí)現(xiàn)處理單元和數(shù)據(jù)無(wú)沖突訪問(wèn)電路結(jié)構(gòu)，并且從圖3.13可以看出，F(xiàn)FT處理器對(duì)slice的消耗與計(jì)算并行度pc成正比。

所設(shè)計(jì)的FFT處理器基于SMIC-40nmCMOS工藝進(jìn)行了ASIC實(shí)現(xiàn)，所用的邏輯綜合工具為SynopsysDesignComplier，布局布