Difficulty: Hard · Puzzle 5 of 6 · Topic: Valid/Ready Handshake Puzzles
A 4-deep FIFO accepts a beat whenever VALID && ready_q. ready_q is a register loaded each edge from the (old) occupancy: ready_q <= (count < THR). The source sends a beat every cycle and the sink never pops. With THR=4 (obvious 'not full' test), which cycle overflows? What is the largest THR that never overflows, and does a ready computed from the NEXT count with THR=4 also work?
`timescale 1ns/1ns
module fifo_rdy #(parameter int THR = 4, parameter bit NEXT = 0) (input bit clk);
localparam int DEPTH = 4;
int count = 0, cyc = 0;
bit push;
bit ready_q = 1; // registered ready: what the source sees THIS cycle was decided last cycle
wire valid = 1; // source always has a beat; the sink never pops
always @(posedge clk) begin
push = valid && ready_q && count < DEPTH;
if (valid && ready_q) begin
if (count == DEPTH) $display("THR=%0d NEXT=%0d cycle %0d: OVERFLOW, beat %0d dropped", THR, NEXT, cyc, cyc);
else count <= count + 1;
end
ready_q <= NEXT ? ((count + int'(push)) < THR) : (count < THR);
cyc++;
end
endmodule
module tb;
bit clk = 0;
always #5 clk = ~clk;
fifo_rdy #(.THR(4)) naive (.clk(clk));
fifo_rdy #(.THR(3)) early (.clk(clk));
fifo_rdy #(.THR(4), .NEXT(1)) nxt (.clk(clk));
initial begin
#(10*8);
$display("THR=4 final count=%0d", naive.count);
$display("THR=3 final count=%0d", early.count);
$display("NEXT final count=%0d", nxt.count);
$finish;
end
endmoduleWrite count and ready_q per edge. The register means ready_q at edge n+1 was decided from the count seen at edge n, before edge n's push.
1) Edge 0: ready_q=1, push, count 0->1; ready_q <= (0<4)=1. Edge 1: count 1->2, ready_q stays 1. Edge 2: count 2->3, ready_q stays 1.
2) Edge 3: ready_q=1, push, count 3->4. The register is loaded from the OLD count 3: (3<4)=1, so ready stays high although the FIFO is now full.
3) Edge 4: ready_q=1 and count=4 -> overflow, the fifth beat (beat 4) is dropped. ready_q finally falls after this edge.
4) With THR=3, ready_q <= (count<3) falls at edge 3 (old count 3), so edge 4 is blocked and the FIFO holds exactly 4 beats, nothing lost.
5) With THR=4 but the NEXT count (count + push) the register sees 4 at edge 3 and also falls in time: also safe and also uses all 4 entries.Answer: THR=4 overflows at cycle 4 (beat 4 is dropped). THR=3 never overflows and still stores 4 beats. Computing the flag from count+push with THR=4 is also safe. In general a registered ready needs one entry of slack (DEPTH-1 on the old count).
Checked by running the code in Verilator 5; the printed output supports the answer above. Only the old-count THR=4 version overflows (at cycle 4); THR=3 and the next-count version never do.
'ready = not full' is correct for a combinational ready but wrong once ready is registered: the flag lags the occupancy by one edge, so one more beat can arrive after the FIFO becomes full. The failure needs a sustained stall plus a full-rate source, so a random test with idle gaps never hits it.
With THR=3 does the FIFO still use all 4 entries, or is one wasted? Model answer: All 4 are used (the simulation ends with count=4). The stale decision lets exactly one more beat in after the threshold is crossed, so the slack is absorbed by the register latency instead of being lost capacity.