H1.2 Parameterized FIFO RTL

MediumFixVerilator · serverReview the topic

Fix a parameterized FIFO whose write pointer wraps at the wrong place when DEPTH is not a power of two.

Hardware context: Clocked FIFO plus ready/valid output adapter. Implement the actual parameterized FIFO RTL.

A FIFO passed every test at depth 4 and depth 8. At depth 3 it returned old data after the second fill. The bug is in how a pointer wraps.

The module submitted_fifo is a synchronous FIFO with parameters DEPTH and WIDTH. It keeps its entries in a ring of memory, with a write pointer and a read pointer. It has one bug. Find it and fix it.

The tests run five copies side by side. Their (DEPTH, WIDTH) pairs are (1, 1), (2, 8), (3, 8), (5, 17) and (8, 32). Each test drives 32 clock edges. An independent queue model checks every flag, response and reset after every edge.

The rules in brief: a write is accepted when the FIFO is not full, and a read when it is not empty. Both use the count from before the edge. A read returns its entry with read_valid = 1 right after the accepting edge. Reset wins and empties the FIFO.

Signals in the Timeline

SignalWidthRole
profile3input of each check
controls96input of each check
values0256input of each check
values1256input of each check
values2256input of each check
values3256input of each check
Full specification
The ports (keep them)
module submitted_fifo #(parameter int DEPTH = 3, WIDTH = 8, FAULT = 0) (
  input  bit        clk, initialize, reset, write_en, read_en,
  input  bit [31:0] write_data,
  output wire       full, empty, read_valid,
  output wire [31:0] read_data);
  // your FIFO
endmodule
RuleWhat a correct FIFO does
WriteAccepted when reset = 0, write_en = 1 and fewer than DEPTH entries are stored before the edge. write_data joins the back.
ReadAccepted when reset = 0, read_en = 1 and at least one entry is stored before the edge. The oldest entry leaves.
Both on one edgeBoth decisions use the count before the edge. When empty, only the write is accepted. When full, only the read is accepted. Otherwise the read takes the oldest entry and the write joins the back.
ResponseThe edge that accepts a read loads the response registers. Right after that edge, read_valid = 1 and read_data holds the entry. This is true even when the read leaves the FIFO empty.
No readAfter an edge that accepts no read, read_valid = 0. read_data may then hold any old value.
Resetreset is synchronous, active high, and wins over both requests. It empties the FIFO and clears read_valid and read_data to 0.
Flagsfull = 1 exactly when DEPTH entries are stored. empty = 1 exactly when none are. Both follow the count with no delay.
Design ruleMeaning
StorageClocked memory with nonblocking updates. Only addresses 0 to DEPTH - 1 hold entries.
PointersA pointer moves only when its request is accepted. It wraps from DEPTH - 1 back to 0, not at the next power of two.
WidthOnly the low WIDTH bits of write_data are stored. read_data is the stored value with zeros above it.
Memory sizeThe memory array is rounded up to a power of two. The extra slots exist only so that a wrong wrap gives a repeatable result.
initializeA test-only input. It clears everything, memory included, before each test. FAULT is unused and always 0.

Depth 1 is legal. Avoid declaring a vector of zero width for it.

The result has error_edges, with bit i set when edge i broke a rule, counting edges from 0. It also counts accepted writes, accepted reads, entries thrown away by reset and reset edges. final_queued is the number of entries left, and depth names the copy under test.

Examples

Example 1

Depth 1 and Width 1
Input
(DEPTH, WIDTH) = (1, 1): write+read 0x11, read, write 0x30, write 0xee, write+read 0xef, write+read 0x71, reset with write+read 0x99, write 0x81, read, read, then idle
Output
error_edges = {}, accepted_writes = 4, accepted_reads = 3, reset_discarded = 1, reset_edges = 1, final_queued = 0, depth = 1

Only the low bit of each value is stored. With one slot, full and empty swap on every accepted request. A write offered while full is refused. Reset throws away the stored entry before the last write and read.

Example 2

Depth 3 Keeps the Oldest Entry First
Input
(3, 8): write+read 0x11, read, write 0x30, 0x31, 0x32, write 0xee, write+read 0xef, write+read 0x71, reset with write+read 0x99, write 0x81, read, read, then idle
Output
error_edges = {}, accepted_writes = 6, accepted_reads = 4, reset_discarded = 2, reset_edges = 1, final_queued = 0, depth = 3

When full, write+read 0xef returns 0x30 and refuses 0xef. The next write+read returns 0x31 and stores 0x71. Reset then throws away 0x32 and 0x71. The last response is 0x81.

Example 3

Width 17 Drops the High Bits
Input
(5, 17): write 0x1ffff, write 0x20000, read, read, reset with write+read 0xffffffff, then idle
Output
error_edges = {}, accepted_writes = 2, accepted_reads = 2, reset_discarded = 0, reset_edges = 1, final_queued = 0, depth = 5

The two responses are 0x1ffff and 0x00000, because bit 17 is not stored. Reset accepts neither request and leaves the FIFO empty.

Example 4

A Second Fill Shows the Wrong Wrap
Input
(3, 8): write 0x11, 0x22, 0x33, read three times, write 0x44, 0x55, 0x66, read three times, then 20 idle edges
Output
error_edges = {}, accepted_writes = 6, accepted_reads = 6, reset_discarded = 0, reset_edges = 0, final_queued = 0, depth = 3

All six writes and reads are accepted. The second drain must return 0x44, 0x55 and 0x66 in order. A write pointer that wraps at 4 puts 0x44 in slot 3, and the read returns old data.

Constraints and Contract

  • Do not accept a request early. Do not pass write data straight to read_data when the FIFO is empty.
  • Use only your ports. Do not read the state of the checker.
  • Keep the module name, the parameters and the ports.

Hints

Hint 1

Work through depth 3 by hand: three writes, three reads, then three more writes. Where should the fourth write land?

Hint 2

For DEPTH = 3 the memory has four slots. A pointer that wraps with % over the memory size visits slot 3, which this FIFO must never use.

Hint 3

Wrap a pointer with a compare: if it equals DEPTH - 1, the next value is 0; otherwise add 1. Check that both pointers do this.

What the grader checks: Five copies with (DEPTH, WIDTH) of (1, 1), (2, 8), (3, 8), (5, 17) and (8, 32) run the same traces. An independent queue checks every flag, response, reset and value. The tests wrap the pointers many times, but they are not a proof for every parameter.

59 checks on Verilator · server. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.

See all 9 steps and the final capstone

Report a problem with this page

Your code SystemVerilogSaved locally
Ln 1, Col 1Tab indents · Ctrl/⌘ + Enter runs samples
Not run yet

Depth 1 and Width 1

Input
(DEPTH, WIDTH) = (1, 1): write+read 0x11, read, write 0x30, write 0xee, write+read 0xef, write+read 0x71, reset with write+read 0x99, write 0x81, read, read, then idle
Expected output
error_edges = {}, accepted_writes = 4, accepted_reads = 3, reset_discarded = 1, reset_edges = 1, final_queued = 0, depth = 1

Only the low bit of each value is stored. With one slot, full and empty swap on every accepted request. A write offered while full is refused. Reset throws away the stored entry before the last write and read.

Run samples executes all 4 public checks. Check all tests runs 59 checks on the server.

Verilator · server