Difficulty: Medium · Puzzle 5 of 6 · Topic: FIFO, Arbitration and Credit Puzzles
A sender has 3 credits. Each beat sent consumes one credit; the credit comes back exactly 5 cycles after the cycle in which the beat was sent (round trip including the receiver freeing the slot), usable in the cycle it arrives. The sender always has data. In which cycles does it send during cycles 0-14, how many beats is that, and how many credits does it need for full rate?
`timescale 1ns/1ns
module tb;
localparam int CREDITS = 3, RTT = 5, N = 15;
bit clk = 0;
int cyc = 0, credits = CREDITS, sent = 0;
int arrive [N + RTT + 1]; // credits arriving back at the sender in a given cycle
string s = "";
always #5 clk = ~clk;
always @(posedge clk) begin
credits += arrive[cyc]; // returned credits are usable in the cycle they arrive
if (credits > 0) begin // sender always has data
credits--; sent++;
arrive[cyc + RTT] += 1; // the receiver frees the slot; the credit is back RTT cycles after the send
s = {s, $sformatf("%0d ", cyc)};
end
if (cyc == N-1) begin
$display("sends happened in cycles: %s", s);
$display("sent %0d beats in %0d cycles", sent, N);
end
cyc <= cyc + 1;
end
initial #(10*N) $finish;
endmoduleCredits sent at cycles 0, 1 and 2 return at cycles 5, 6 and 7.
1) Cycles 0, 1, 2: send; credits go 3 -> 0.
2) Cycles 3, 4: no credit, no send. Cycle 5: the credit from cycle 0 arrives, send. Cycles 6 and 7 likewise.
3) The pattern repeats every 5 cycles: sends at 0 1 2 5 6 7 10 11 12 = 9 beats in 15 cycles (rate 3/5).
4) Full rate (1 beat per cycle) needs credits >= round-trip time in cycles = 5.Answer: Sends in cycles 0, 1, 2, 5, 6, 7, 10, 11, 12: 9 beats in 15 cycles (60%). Full rate needs at least 5 credits (credits >= RTT).
Checked by running the code in Verilator 5; the printed output supports the answer above. The sender in the code stalls whenever its 3 credits are out; the pattern repeats every RTT=5 cycles.
The link is idle not because the receiver is slow but because the credit window is smaller than the round-trip: adding receiver speed or sender buffering does nothing. A performance test with only a few outstanding credits looks like 'low bandwidth' with no protocol error to find.
How many receiver buffer entries must exist for the 5-credit full-rate link? Model answer: At least 5, one per credit, since the credit count equals the number of beats the receiver must be able to store when the sender sends a full window without any returns (bandwidth x round-trip).