Difficulty: Easy · Puzzle 2 of 6 · Topic: FIFO, Arbitration and Credit Puzzles
A 2-deep synchronous FIFO accepts a write only if !full and a read only if !empty, where full and empty come from the registered count (no bypass). Over the 5 cycles below, write requests are 1,1,1,1,0 and read requests 1,0,1,0,0. For each cycle, say which requests are accepted and what the read returns.
`timescale 1ns/1ns
module tb;
localparam int DEPTH = 2;
localparam int N = 5;
// cycle: 01234
localparam bit [0:N-1] WR = 5'b11110;
localparam bit [0:N-1] RD = 5'b10100;
bit clk = 0;
int cyc = 0, count = 0, wptr = 0, rptr = 0;
bit [7:0] mem [DEPTH];
bit [7:0] wdata = 8'h11; // 0x11, 0x22, 0x33 ... one new value per accepted write
always #5 clk = ~clk;
wire full = (count == DEPTH);
wire empty = (count == 0);
always @(posedge clk) begin
bit wr_ok, rd_ok;
wr_ok = WR[cyc] && !full; // decided from the registered flags only
rd_ok = RD[cyc] && !empty;
if (WR[cyc] && !wr_ok) $display("cycle %0d: write of 0x%0h REJECTED (full=%0b)", cyc, wdata, full);
if (RD[cyc] && !rd_ok) $display("cycle %0d: read REJECTED (empty=%0b)", cyc, empty);
if (wr_ok) begin
mem[wptr] <= wdata; wptr <= (wptr + 1) % DEPTH; wdata <= wdata + 8'h11;
$display("cycle %0d: write 0x%0h accepted", cyc, wdata);
end
if (rd_ok) begin
rptr <= (rptr + 1) % DEPTH;
$display("cycle %0d: read returns 0x%0h", cyc, mem[rptr]);
end
count <= count + int'(wr_ok) - int'(rd_ok);
cyc <= cyc + 1;
end
initial #(10*N) $finish;
endmoduleEvaluate the flags at the START of each cycle (from the registered count), not after the cycle's own write or read.
1) Cycle 0: count=0 (empty). The read is rejected; the write of 0x11 is accepted. Count becomes 1.
2) Cycle 1: write 0x22 accepted (count 1 -> 2, now full). No read requested.
3) Cycle 2: count=2 (full). The read is accepted and returns 0x11; the write of 0x33 is rejected because full is high at the start of the cycle even though a read happens in the same cycle. Count becomes 1.
4) Cycle 3: the write of 0x33 is retried and accepted.Answer: Cycle 0: read rejected, write 0x11 accepted. Cycle 1: write 0x22 accepted. Cycle 2: read returns 0x11, write 0x33 rejected. Cycle 3: write 0x33 accepted.
Checked by running the code in Verilator 5; the printed output supports the answer above. Flags are taken from the registered count, so same-cycle read on empty and same-cycle write on full are both rejected.
Two natural assumptions are wrong for this design: a read in the same cycle as the first write does not pick up the new word (no flow-through), and a write at full succeeds in the same cycle as a read only if the design explicitly allows it. A reference model that always accepts a simultaneous read/write pair disagrees with the RTL at both points.
How can a FIFO accept a write at full when a read happens in the same cycle, and what does it cost? Model answer: Use wr_ok = wr && (!full || rd_ok). That is a combinational path from the read side to write acceptance (or a deeper FIFO with an almost-full flag). It gains one slot of throughput at the cost of a longer timing path.