今天咱們開(kāi)始聊聊FIFO的設(shè)計(jì)。FIFO是一個(gè)數(shù)字電路中常見(jiàn)的模塊，主要作用是數(shù)據(jù)產(chǎn)生端和接受端在短期內(nèi)速率不匹配時(shí)作為數(shù)據(jù)緩存。FIFO是指First In, First Out，即先進(jìn)先出，跟大家排隊(duì)一樣。越早排隊(duì)的人排在越前面，輪到他的次序也越早，所以FIFO有些時(shí)候也被稱為隊(duì)列queue。

這一篇我們先介紹利用Flip flop來(lái)作為FIFO存儲(chǔ)單元的設(shè)計(jì)方法，這也是同步FIFO中最為簡(jiǎn)單的內(nèi)容，內(nèi)容比較基礎(chǔ)。之后老李會(huì)帶大家了解基于SRAM的FIFO設(shè)計(jì)。 而且我們這里只講同步FIFO， 即寫(xiě)入端和讀出端是屬于同一個(gè)時(shí)鐘域。如果寫(xiě)入和讀出是不同的時(shí)鐘域，那么就是異步FIFO。關(guān)于異步FIFO之前老李在CDC系列里有講過(guò)，大家有興趣可以直接在公眾號(hào)底部點(diǎn)擊CDC可以了解。

我們先來(lái)看一個(gè)FIFO模塊需要那幾個(gè)基本的輸入輸出。

其中寫(xiě)入端寫(xiě)入操作為push，要寫(xiě)入的data為D，當(dāng)push為高時(shí)，數(shù)據(jù)D被寫(xiě)入FIFO。對(duì)于寫(xiě)入端，只需要在乎FIFO是不是滿：如果FIFO已經(jīng)滿了，是不允許再寫(xiě)入的。對(duì)于讀出端，數(shù)據(jù)讀出為pop，Q為讀出的數(shù)據(jù)。在讀出端，只需要在乎FIFO是不是空：如果為空，則不能進(jìn)行pop操作。

對(duì)于讀出端來(lái)說(shuō)，這里有一點(diǎn)需要明確：當(dāng)FIFO里面有數(shù)據(jù)的時(shí)候，Q應(yīng)該輸出當(dāng)前FIFO最前面（最早進(jìn)入）的那個(gè)數(shù)據(jù)，而不是需要pop才能輸出。也就是說(shuō)，假設(shè)FIFO為空，這個(gè)時(shí)候我們寫(xiě)入一個(gè)數(shù)據(jù)D1，那么在下一個(gè)周期，Q應(yīng)該立刻變?yōu)镈1，同時(shí)empty為0。當(dāng)只有讀第二次寫(xiě)入的數(shù)據(jù)的時(shí)候，我們才需要pop第一次，Q才會(huì)指向D2。 這樣的行為和一個(gè)D觸發(fā)器非常類似，所以上面我們才將輸入數(shù)據(jù)表示為D，輸出數(shù)據(jù)表示為Q，便于和D觸發(fā)器類比起來(lái)。為什么強(qiáng)調(diào)這一點(diǎn)，因?yàn)樵诤竺胬肧RAM來(lái)實(shí)現(xiàn)FIFO的時(shí)候如果要實(shí)現(xiàn)這一點(diǎn)是需要技巧的，我們后面會(huì)看到。(老李也見(jiàn)過(guò)要想讀出第一個(gè)數(shù)必須要先pop一次的FIFO設(shè)計(jì)，這種設(shè)計(jì)就不是很高效，要多花一個(gè)周期來(lái)才能讀出第一個(gè)數(shù)）。

另外FIFO還有一個(gè)特性，即當(dāng)FIFO不是空也不是滿的時(shí)候，是允許讀和寫(xiě)發(fā)生在同一個(gè)周期的，即一邊寫(xiě)入，一邊讀出。這個(gè)對(duì)于Flip Flop來(lái)實(shí)現(xiàn)的FIFO很容易做到，但是對(duì)于SRAM來(lái)實(shí)現(xiàn)的FIFO就不是那么容易了，特別是SRAM只有一個(gè)端口，一個(gè)周期內(nèi)要么讀，要么寫(xiě)。這樣設(shè)計(jì)的時(shí)候就更需要技巧了，我們?cè)诤竺娴奈恼轮性偌?xì)聊。

下面我們來(lái)聊FIFO的內(nèi)部細(xì)節(jié)。首先我們說(shuō)存儲(chǔ)單元，對(duì)于利用FlipFlop來(lái)實(shí)現(xiàn)的FIFO，存儲(chǔ)單元就是一個(gè)flop array。

reg [DATA_WIDTH-1:0]    mem[DEPTH]

其中DATA_WIDTH和DEPTH都是兩個(gè)參數(shù)parameter。

然后我們需要兩個(gè)指針pointer，來(lái)分別用于讀和寫(xiě)，分別為wr_ptr, rd_ptr。有人也喜歡用wr_addr， rd_addr。這兩個(gè)指針的意義為：

wr_ptr: 接下來(lái)要寫(xiě)入的位置。

rd_ptr: 當(dāng)前讀出的位置。

初始的時(shí)候，wr_ptr和rd_ptr都被reset成0，那么可以理解為，第一個(gè)要寫(xiě)入的location是mem[0]，第一個(gè)要讀出的位置也是mem[0]。

當(dāng)有一次push操作的時(shí)候，wr_ptr要加1。當(dāng)有一次pop的時(shí)候，rd_ptr要+1。

那么我們可以寫(xiě)出下面的邏輯

always_ff@(posedge clk) begin

if(!rst_n)

for(int i = 0; i < DEPTH; i++)

   mem[i] <= '0;

else begin

if(push & ~full)

   mem[wr_ptr] <= d;

end

end

assign q = mem[rd_ptr];

那么接下來(lái)有兩個(gè)問(wèn)題：一是如何來(lái)判斷空和滿，另個(gè)一問(wèn)題是如何給wr_ptr和rd_ptr加1。

在思考這兩個(gè)問(wèn)題之前，我們看我們需要幾位來(lái)表示wr_ptr和rd_ptr。如果FIFO的深度是DEPTH，那么要來(lái)取址mem[DEPTH]，我們需要的位數(shù)應(yīng)該是$clog2(DEPTH)。比如DEPTH=8，那么需要3位ptr用來(lái)取址。

再來(lái)回答上面兩個(gè)問(wèn)題。通常我們有兩種方式來(lái)處理。第一種方式，如果DEPTH剛好是2的冪次，那么做法是給wr_ptr和rd_ptr各多分配一位。比如DEPTH=8，則分配4位給wr_ptr和rd_ptr。這樣做的好處是我們可以利用2進(jìn)制的特性

空：wr_ptr == rd_ptr。

滿：wr_ptr把rd_ptr套圈了，即低位相等，但是MSB相反。

舉個(gè)例子當(dāng)把mem[0]到mem[7]都寫(xiě)完之后，wr_ptr 由4’b0111再加1就來(lái)到了4'b1000，而如果我們還沒(méi)有pop過(guò)的話rd_ptr就還停留在4‘b0000，這樣就是達(dá)到了套圈，F(xiàn)IFO變滿了。

而且這樣做簡(jiǎn)化了rd_ptr和wr_ptr加1的操作，直接利用2進(jìn)制的進(jìn)位加法，當(dāng)記到4‘b0111的時(shí)候再加1就直接變?yōu)?'b1000，這樣MSB自動(dòng)表示是不是套圈，而低位可以直接用來(lái)取址mem。

localparam PTR_WIDTH = $clog2 (DEPTH) + 1;

logic [DATA_WIDTH-1:0] mem[DEPTH];

logic [PTR_WIDTH-1:0] wr_ptr;

logic [PTR_WIDTH-1:0] rd_ptr;

always_ff@(posedge clk) begin

if(!rst_n)

for(int i = 0; i < DEPTH; i++)

   mem[i] <= '0;

else begin

if(push & ~full)

   mem[wr_ptr[PTR_WIDTH-2:0]] <= d;

end

end

always_ff@(posedge clk) begin

if(!rst_n)

wr_ptr <= '0;

else

if(push & ~full)

  wr_ptr <= wr_ptr + 1'b1;

end

always_ff@(posedge clk) begin

if(!rst_n)

rd_ptr <= '0;

else

if(pop & ~empty)

  rd_ptr <= rd_ptr + 1'b1;

end

assign q = mem[rd_ptr[PTR_WIDTH-2:0]];

assign full = (rd_ptr[PTR_WIDTH-1] ^ wr_ptr[PTR_WIDTH-1]) &&

(rd_ptr[PTR_WIDTH-2:0] == wr_ptr[PTR_WIDTH-2:0]);

assign empty = rd_ptr == wr_ptr;

但是這樣做的限制在于DEPTH必須是2的冪次方個(gè)。 如果不是，比如是6，那么當(dāng)wr_ptr記到3'b101的時(shí)候，下一次寫(xiě)入就不能直接二進(jìn)制加1了，而是要回到3'b000。這個(gè)時(shí)候稍微方便一點(diǎn)的做法是設(shè)計(jì)一個(gè)計(jì)數(shù)器，用來(lái)計(jì)數(shù)當(dāng)前FIFO已經(jīng)被寫(xiě)入但是還未讀出的數(shù)據(jù)個(gè)數(shù)。這樣做的好處是FIFO的空滿可以直接利用這個(gè)計(jì)數(shù)器與0和與DEPTH相比較而得到。老李更推薦這一種寫(xiě)法，而且這個(gè)時(shí)候wr_ptr和rd_ptr也不需要多加1位。

localparam PTR_WIDTH = $clog2 (DEPTH);

logic [DATA_WIDTH-1:0] mem[DEPTH];

logic [PTR_WIDTH-1:0] wr_ptr;

logic [PTR_WIDTH-1:0] rd_ptr;

logic [PTR_WIDTH:0] cnt; //current fifo count

always_ff@(posedge clk) begin

if(!rst_n)

for(int i = 0; i < DEPTH; i++)

   mem[i] <= '0;

else begin

if(push & ~full)

   mem[wr_ptr] <= d;

end

end

always_ff@(posedge clk) begin

if(!rst_n)

wr_ptr <= '0;

else

if(push & ~full)

  wr_ptr <= (wr_ptr == DEPTH-1) ? '0 : (wr_ptr + 1'b1);

end

always_ff@(posedge clk) begin

if(!rst_n)

rd_ptr <= '0;

else

if(pop & ~empty)

  rd_ptr <= (rd_ptr == DEPTH-1) ? '0 : (rd_ptr + 1'b1);

end

always_ff@(posedge clk) begin

if(!rst_n)

cnt <= '0;

else begin

//only push, no pop

if(push && !pop && !full)

  cnt <= cnt + 1'b1;

//only pop, no push

else if(!push && pop && !empty)

  cnt <= cnt - 1'b1;

//no pop or push,

//pop and push in the same cycle

// else cnt <= cnt;

end

end

assign q = mem[rd_ptr];

assign full = cnt == DEPTH;

assign empty = cnt == '0;

這就是基于Flip Flop的同步FIFO的基本原理，還是比較簡(jiǎn)單直接的，RTL code加起來(lái)也就幾十行。下面老李希望大家思考幾個(gè)問(wèn)題：

1. 什么時(shí)候使用基于Flip-flop的同步FIFO？什么時(shí)候使用基于SRAM的FIFO？
2. 最后的q是來(lái)自于寄存器輸出還是來(lái)自于組合邏輯電路輸出？如果是來(lái)自于組合邏輯輸出，如何優(yōu)化？
3. 如果希望full和empty也直接來(lái)自寄存器的輸出，要怎么更改設(shè)計(jì)？

最后再附送一個(gè)老李一個(gè)老朋友的作為面試官的出的面試題，大家可以自己思考一下：如何設(shè)計(jì)一個(gè)深度為1的同步FIFO？