How many slots does the crossing need?

Retries, NACKs and Credits introduced credits: the sender holds one credit per free receiver slot and sends only with a credit, so the buffer never overflows. Across a clock crossing the credit has to come back across the same boundary. The receiver frees a slot when it reads an entry, and that news reaches the sender only after its own synchronization.

In an asynchronous FIFO the credit return is built in: the read pointer, Gray-coded and synchronized into the write domain, tells the writer how many slots are free, and the full flag is credits = 0. When the buffer sits wholly in the receiver's domain (a receive queue at H fed over a link), the receiver needs an explicit credit-return path back to the sender, and that path must itself be a proper crossing: a Gray-coded count of returned credits, or a two-phase toggle per credit. Never a multi-bit binary counter sampled directly, and never single-cycle pulses through a two-flop synchronizer, which merge when they arrive closer together than the receiving clock can see.

Depth must cover bandwidth times round trip

Each slot is unavailable for one credit round trip: forward crossing, receiver read, credit return crossing. If the sender wants to send B messages per cycle, it has B x RTT messages outstanding at any time, so it needs at least that many credits:

depth >= ceil(B x RTT), with RTT measured in sender cycles. With fewer credits the sender stalls, and throughput falls to depth / RTT messages per cycle.

Worked case on the course model: C0 streams misses to independent lines (a prefetch stream, illustrative), one GetS per cluster cycle, into the cluster-to-H request crossing. Illustrative latencies in cluster cycles: 4 for the message to become readable at H (write, two synchronizer flops, phase uncertainty), 1 for H to read the entry, 4 for the credit to become visible back at C0. RTT = 9, so the request crossing needs 9 slots for full rate.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

import math
def sent_per_cycle(depth, rtt, every=1, cycles=1800):
    """Credit loop: a message sent at cycle t returns its credit at t + rtt."""
    credits, returns, offered, sent = depth, {}, 0, 0
    backlog = 0
    for t in range(cycles):
        credits += returns.pop(t, 0)
        if t % every == 0:
            offered += 1
            backlog += 1
        if backlog and credits:
            credits -= 1
            backlog -= 1
            sent += 1
            returns[t + rtt] = returns.get(t + rtt, 0) + 1
        assert 0 <= credits <= depth
    return sent / cycles, offered / cycles
def min_depth(rtt, every):
    d = 1
    while True:
        got, want = sent_per_cycle(d, rtt, every)
        if got >= want:
            return d
        d += 1
# general claim: minimum depth = ceil(bandwidth x round trip)
for rtt in range(2, 17):
    for every in (1, 2, 3):
        assert min_depth(rtt, every) == math.ceil(rtt / every), (rtt, every)
# the worked case: RTT 9, one message per cycle
full, _ = sent_per_cycle(9, 9)
assert full == 1.0
# failing case: one slot less loses throughput, to depth / RTT
short, _ = sent_per_cycle(8, 9)
assert short < 1.0 and abs(short - 8 / 9) < 0.01
print("PASS: depth ceil(B x RTT) sustains the rate, depth one less drops to depth/RTT")

The check searches the smallest depth that keeps up with the offered rate for round trips 2 to 16 and rates of 1, 1/2 and 1/3 messages per cycle, and finds ceil(B x RTT) every time. For the worked case, depth 9 sends every cycle and depth 8 drops to 8/9.

Two different reasons for depth

Bandwidth times round trip is a throughput rule. Deadlock freedom is a separate rule from Part 5: responses always sink, meaning the response FIFO is drained without waiting on another class. If that holds, even a one-slot response FIFO is deadlock-free, just slow. If it does not hold, no depth is safe. Size the response crossing for throughput; prove sinking from the consumer's behaviour.

The receiver clock matters. If H runs at half the cluster rate, the forward crossing and H's read take more cluster cycles, so RTT and the required depth grow, and H cannot drain faster than its own clock however deep the FIFO is.

Related topics

• Shared course model

• Credits as capacity, not permission

• CDC course: FIFO depth sizing

• CDC course: two-phase toggle

• Per-class crossings