Work out the smallest FIFO that loses no beat for a source that cannot be held. Answer with and without a pass-through path, from a 64-cycle profile.
Hardware context: A FIFO sink with backpressure or credits between a source and a stalling consumer. Size the smallest FIFO that absorbs a traffic profile without loss, with and without a bypass path.
Lesson P1.6 sized a FIFO from one stall. Real traffic is not one stall: bursts, gaps and a consumer that comes and goes. Every extra entry costs area, so the answer you want is the smallest depth that never loses a beat.
Write module fifo_sizer. It gets two 64-bit profiles. Bit k of arrive says a beat arrives at edge k, and the source cannot wait. Bit k of drain says the consumer can take one beat at edge k.
Report the smallest depth that loses nothing. With bypass = 1 a beat may skip an empty FIFO when the consumer takes it at the edge it arrives. The fixture asks for both answers for every profile.
Signals in the Timeline
| Signal | Width | Role |
|---|---|---|
profile | 5 | input of each check |
Full specification
module fifo_sizer (
input logic [63:0] arrive, // bit k: a beat arrives at edge k; the source cannot be held
input logic [63:0] drain, // bit k: the consumer can take one beat at edge k
input logic bypass, // 1: a beat may pass straight through an empty FIFO
output int depth // the smallest number of entries that loses no beat
);
// your sizer
endmodule
| At edge k | What happens |
|---|---|
| drain[k] = 1 and the FIFO holds a beat | The consumer takes the oldest beat held before edge k. |
| arrive[k] = 1 | The new beat enters the FIFO. |
| bypass = 1, the FIFO is empty, arrive[k] and drain[k] are both 1 | The new beat goes straight to the consumer and uses no entry. |
| bypass = 0 | A beat that arrives at edge k cannot leave before edge k + 1. |
depth is the most beats held after any edge. The FIFO starts empty at edge 0. The result packs the answer with bypass = 1 in bits 15 to 8 and with bypass = 0 in bits 7 to 0.
Examples
Example 1
Full Rate in and Out- Input
arrive 64'hffffffffffffffff, drain 64'hffffffffffffffff (bit k is edge k)
- Output
depth_bypass = 0, depth = 1
Without bypass every beat waits one edge in the FIFO: depth 1. With bypass each beat goes straight through: depth 0.
Example 2
A 12-cycle Stall- Input
arrive 64'hffffffffffffffff, drain 64'hfffffffffff000ff (bit k is edge k)
- Output
depth_bypass = 12, depth = 13
Twelve beats arrive while the consumer sleeps, on top of the one already waiting. Without bypass that is 13 entries; with bypass 12.
Example 3
Bursts into a Half-Rate Consumer- Input
arrive 64'h00ff00ff00ff00ff, drain 64'h5555555555555555 (bit k is edge k)
- Output
depth_bypass = 4, depth = 5
Eight beats arrive in eight edges while the consumer takes one every other edge. The backlog peaks at 5 entries, or 4 with bypass.
Constraints and Contract
- Keep the module name and the ports. The fixture changes the inputs and reads depth 1 ns later, so compute it combinationally.
- A loop over the 64 bits inside always @* is fine.
Hints
Hint 1
Replay the edges. Keep the occupancy and its peak.
Hint 2
Inside one edge, the order matters: the consumer takes from what was there before, then the new beat comes in.
Hint 3
Without bypass, one beat per cycle in and out still needs one entry: every beat waits one edge.
What the grader checks: Your sizer answers thirteen profiles, each with and without bypass, and is compared with an independent replay. Passing shows the edge rules are right on these profiles.
13 checks on Icarus · browser samples / server checks. 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 4 steps and the final capstone