A processor misses in its cache on the word at address 0x28. The cache line holding it is 64 bytes, from 0x00 to 0x3F, and the whole line must be fetched. The processor only needs one word right now, the one at 0x28. If the line arrives in address order, starting at 0x00, the processor waits for five words it does not need yet before it gets the one it does.

How does one request describe many data beats, and why are there several kinds of burst?

The obvious answer, and why it breaks

The obvious way to move many words is many requests, one per word. Each request costs an address beat, a slot in the target's queue and a decode, so a 16-word transfer spends as much effort on addressing as on data. A burst sends one address and a length, and the target generates the rest. But "the rest" can be computed in different ways, and the simple choice, incrementing from the start address, is not right for every use.

The idea: three ways to generate beat addresses

A burst is described by its start address, its length (number of beats) and its size (bytes per beat).

For a WRAP burst, the block that holds the burst is aligned to its own size, the wrap boundary:

So a WRAP burst always touches exactly the words of one aligned block, each once, starting with the one the requester asked for. That is critical word first: the cache line from the opening arrives starting at 0x28, and the processor can continue after the first beat.

Build it: a burst address generator

The generator computes every beat's address for each burst type, including the interview's WRAP4 at 0x38 and the opening's 64-byte cache line, and checks that each WRAP burst covers its block exactly once.

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
36
37

"""Beat addresses of FIXED, INCR and WRAP bursts.

A burst is described by its start address, its number of beats and the bytes per
beat (the transfer size). FIXED repeats the start address; INCR adds the size each
beat; WRAP increments like INCR but wraps at a boundary of beats x size bytes, so
every beat stays inside one aligned block (a cache line).
"""


def beats(kind, start, n, size):
    if kind == "FIXED":
        return [start] * n
    if kind == "INCR":
        return [start + i * size for i in range(n)]
    assert kind == "WRAP" and n in (2, 4, 8, 16) and start % size == 0
    block = n * size                      # the wrap boundary
    base = start - start % block          # aligned block that holds the burst
    return [base + (start - base + i * size) % block for i in range(n)]


def show(kind, start, n, size):
    addrs = beats(kind, start, n, size)
    print(f"{kind}{n} at 0x{start:02X}, {size} bytes per beat: " + " ".join(f"0x{a:02X}" for a in addrs))
    return addrs


show("FIXED", 0x38, 4, 4)
show("INCR", 0x38, 4, 4)
w4 = show("WRAP", 0x38, 4, 4)
w8 = show("WRAP", 0x38, 4, 8)
line = show("WRAP", 0x28, 8, 8)           # a 64-byte cache line, critical word at 0x28

for addrs, n, size in ((w4, 4, 4), (w8, 4, 8), (line, 8, 8)):
    block = n * size
    base = addrs[0] - addrs[0] % block
    assert sorted(addrs) == [base + i * size for i in range(n)]   # each word of the block once
print("PASS: a WRAP burst touches every word of its aligned block exactly once, starting at the requested word")

It prints:

FIXED4 at 0x38, 4 bytes per beat: 0x38 0x38 0x38 0x38
INCR4 at 0x38, 4 bytes per beat: 0x38 0x3C 0x40 0x44
WRAP4 at 0x38, 4 bytes per beat: 0x38 0x3C 0x30 0x34
WRAP4 at 0x38, 8 bytes per beat: 0x38 0x20 0x28 0x30
WRAP8 at 0x28, 8 bytes per beat: 0x28 0x30 0x38 0x00 0x08 0x10 0x18 0x20
PASS: a WRAP burst touches every word of its aligned block exactly once, starting at the requested word

Read the WRAP rows against the formula. WRAP4 with 4-byte beats has a 16-byte boundary, so the block is 0x30–0x3F: after 0x38 and 0x3C the address wraps to 0x30. With 8-byte beats the boundary is 32 bytes and the block is 0x20–0x3F, so the burst wraps after its first beat. The WRAP8 line fill starts at 0x28, runs to 0x38, wraps to 0x00 and finishes at 0x20: all eight words of the line, critical word first.

Rules protocols add

• WRAP lengths are powers of two, so the boundary is a power of two and the wrap is a simple bit mask on the address.

• WRAP start addresses must be aligned to the size, so every beat is a whole word of the block.

• Bursts may not cross certain boundaries, such as a 4 KB page, because targets and address translation work per page (lesson 5.10).

• Maximum lengths limit how long one burst can occupy shared paths, which bounds the latency it adds for others.

How real protocols chose

What breaks

A memory controller (illustrative) implemented WRAP bursts as INCR bursts that "usually" stayed inside the line. A cache-line fill starting at the last word of a line ran off its end into the next line, returning the wrong seven words. It passed every test that started fills at the beginning of a line, which was all of them. Test wrapping bursts from every start position in the block, not just the aligned one.

Key takeaways

• A burst sends one address and a length; the target generates the beat addresses.

• INCR increments, FIXED repeats, WRAP increments within an aligned block of length × size bytes.

• WRAP gives critical word first for cache lines; test every start offset.

Related topics

• Part 5 overview: Transactions