H1.1 FIFO Trace Evaluator

EasyFixVerilator · serverReview the topic

Fix a FIFO reference model so that its predictions match a real FIFO on every clock edge.

Hardware context: Clocked FIFO plus ready/valid output adapter. Evaluate a concrete FIFO cycle trace under its acceptance policy.

A scoreboard trusts its reference model. If the model is wrong, every comparison after it is wrong too. This FIFO model has one bug, and the real FIFO disagrees with it.

The class trace_evaluator predicts a FIFO of 8-bit entries with DEPTH 1, 3 or 5. Each call to step() gives the inputs of one clock edge. It returns what the FIFO accepts on that edge, the count and flags after the edge, and the value a read returns. contents() returns what the FIFO holds, oldest first.

The tests drive 32 edges into a real FIFO and call step() once per edge. They compare every prediction with the hardware pins. At the end they compare every byte that contents() returns.

Find the bug and fix it. The rules in brief: a write is accepted when the FIFO is not full, and a read when it is not empty. Both decisions use the count from before the edge. Reset wins and empties the FIFO. The full rules are in the specification.

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 class (keep these names and types)
class trace_evaluator;
  function new(input int depth);
  function bit [23:0] step(input bit reset, write_en, read_en, input bit [7:0] write_data);
  function bit [39:0] contents();
endclass
Bits of step()Holds
23:21Always 0.
20post_full: full after the edge.
19post_empty: empty after the edge.
18read_valid after the edge. It equals accepted_read.
17accepted_read: this edge accepts the read.
16accepted_write: this edge accepts the write.
15:8post_count: the number of entries after the edge.
7:0response: the entry the accepted read returns, or 0 when no read is accepted.
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.

contents() packs the stored entries into 40 bits. The oldest entry goes in bits 7:0, the next in bits 15:8, and so on. Unused bytes are 0. contents() only looks; it must not remove anything.

A response of 0 when no read is accepted is a rule of the model. The read_data pin of the hardware may hold anything then.

Each test starts with an empty model and an empty FIFO. failed_edges in the result has bit i mod 16 set when edge i failed, counting edges from 0. The write and read counts come from the hardware and include entries that a later reset threw away.

Examples

Example 1

Depth 1 with Offers on Every Edge
Input
Depth 1: write+read 0x12, write+read 0x34, write+read 0x56, then 29 idle edges
Output
failed_edges = {}, accepted_writes = 2, accepted_reads = 1, final_count = 1, final_items = 0x56

Edge 0 finds the FIFO empty, so only the write of 0x12 is accepted. Edge 1 finds it full, so only the read is accepted and 0x34 is refused. Edge 2 stores 0x56. That is two writes, one read and one entry left.

Example 2

A Read and a Write in the Middle
Input
Depth 3: write 0x11, write 0x22, write+read 0x33, then 29 idle edges
Output
failed_edges = {}, accepted_writes = 3, accepted_reads = 1, final_count = 2, final_items = 0x3322

Two entries are stored when both requests arrive, so both are accepted. The read returns the oldest entry, 0x11, and 0x33 joins the back. 0x22 and 0x33 remain, packed as 0x3322.

Example 3

Reset Throws Entries Away but Not the Counts
Input
Depth 5: write 0x81, reset with write+read 0x99, write 0x42, then 29 idle edges
Output
failed_edges = {}, accepted_writes = 2, accepted_reads = 0, final_count = 1, final_items = 0x42

Reset refuses both offers and throws away 0x81. The write count still includes 0x81, so it is 2. Only 0x42 remains at the end.

Constraints and Contract

  • DEPTH is 1, 3 or 5. Data is 8 bits. The tests never drive x or z.
  • Requests are offers. The tests often offer a write to a full FIFO or a read from an empty one.
  • Keep the class name, the method names and their argument and return types.

Hints

Hint 1

Decide both requests from the queue size before the edge. Change the queue only after both decisions are made.

Hint 2

Trace a short case by hand: write 0x11, write 0x22, then read. Which value must the read return? Which value does the model return?

Hint 3

A FIFO is first in, first out. Writes join the back of the queue, so a read must take from the front.

What the grader checks: Each test replays 32 edges on a real FIFO of depth 1, 3 or 5. It compares every prediction and every final byte. Passing shows that the model matches these traces, not every possible FIFO.

54 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 with Offers on Every Edge

Input
Depth 1: write+read 0x12, write+read 0x34, write+read 0x56, then 29 idle edges
Expected output
failed_edges = {}, accepted_writes = 2, accepted_reads = 1, final_count = 1, final_items = 0x56

Edge 0 finds the FIFO empty, so only the write of 0x12 is accepted. Edge 1 finds it full, so only the read is accepted and 0x34 is refused. Edge 2 stores 0x56. That is two writes, one read and one entry left.

Run samples executes all 3 public checks. Check all tests runs 54 checks on the server.

Verilator · server