Can memory requests finish in a different order?

Yes, for different addresses. The rule: coherence for X is serialized at H, per line. Below H, either H issues at most one memory access for X at a time and waits for its acceptance (the course default: PutM, H writes memory, Put-Ack, and only then the next request for X), or the controller must keep same-address order for what it has accepted. In practice it checks each read against the write queue by address: on a hit it forwards the youngest queued data or holds the read until the write issues. Different addresses may be reordered freely.

How a scheduler reorders

A typical scheduler holds separate read and write queues. It prefers ready row-buffer hits (FR-FCFS: first-ready, first-come-first-served), serves reads before writes, and drains writes in bursts when the write queue passes a high watermark. All of this reorders commands to different addresses. Same-address order is kept by the write-queue address check (forward or block), not by the scheduling policy.

Where overlapping commands for X come from

If H waited for DRAM itself before the next access to X, it would never have two memory accesses for X outstanding. They appear as soon as H treats a write as done when the controller's write queue has accepted it (the acceptance rule of the previous lesson), with or without Part 3's early Put-Ack: C0's PutM puts W X = 1 into the controller's write queue and H sends Put-Ack and records U. C1 then takes M (its GetM's memory read must return 1, by the same check), writes 2 and evicts, so H accepts W X = 2. A later GetS makes H issue R X. The controller now holds W X = 1, W X = 2 and R X for one line at once, alongside unrelated work such as W Y = 9 (Y is a different line).

Worked read-after-write case, keeping that trace's roles: W X = 1 sits in the write queue, C1's GetM reaches H, and H issues R X. DRAM still holds 0. With the address check the read hits the queued write and returns 1, so C1 fills with 1 and H records exclusive(C1). Without the check the scheduler serves R X from DRAM ahead of the queued write: the read returns 0 while H records exclusive(C1), a stale fill that no cache-state check will notice.

The checker below models the controller. All four commands are accepted in order (W X = first, W Y = 9, W X = second, R X) and each order is the order in which they issue to DRAM. A write waits in the write queue until it issues. A read returns the youngest older queued write to its address if there is one, otherwise DRAM. Assume, for this checker only, that commands are accepted in index order. An order is legal when it keeps write-write order per address. Reads may issue early because the check forwards to them. The test enumerates all 24 orders, asserts that exactly the legal ones give the expected result, and keeps two negative cases: an unchecked read that issues before the write drains returns a stale value, and a write-write inversion leaves X equal to the first value.

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
38
39
40
41
42
43
44
45
46
47
48

from itertools import permutations
def legal(order, commands):
    pos = {c: i for i, c in enumerate(order)}
    return all(pos[i] < pos[j]
               for i in range(len(commands)) for j in range(i + 1, len(commands))
               if commands[i][0] == commands[j][0] == "W"
               and commands[i][1] == commands[j][1])
def execute(order, commands, check=True):
    # All commands are accepted in index order. order is the order in which
    # the scheduler issues them to DRAM. A write waits in the write queue
    # until it issues. A read is served when it issues.
    dram, queue, reads = {"X": 0, "Y": 0}, set(range(len(commands))), []
    for i in order:
        op, line, value = commands[i]
        queue.discard(i)
        if op == "W":
            dram[line] = value
            continue
        older = [j for j in queue if j < i and commands[j][:2] == ("W", line)]
        if check and older:
            reads.append(commands[max(older)][2])  # youngest older write
        else:
            reads.append(dram[line])
    return dram, reads
for first, second in ((1, 2), (7, 11)):
    commands = [("W", "X", first), ("W", "Y", 9),
                ("W", "X", second), ("R", "X", None)]
    expected = ({"X": second, "Y": 9}, [second])
    assert execute(range(4), commands) == expected
    orders = list(permutations(range(4)))
    assert len(orders) == 24
    for o in orders:
        assert legal(o, commands) == (execute(o, commands) == expected), o
    assert sum(legal(o, commands) for o in orders) == 12
    # Without the queue check, a read issued before W X = second drains is stale.
    early = [o for o in orders if legal(o, commands) and o.index(3) < o.index(2)]
    assert early and all(execute(o, commands, check=False)[1] != [second]
                         for o in early)
    assert execute((3, 0, 1, 2), commands, check=False)[1] == [0]
    # A write-write inversion leaves X == first, even with forwarding.
    for o in orders:
        if not legal(o, commands):
            assert execute(o, commands)[0]["X"] == first
# The worked read-after-write case: W X = 1 queued, R X issues first.
raw = [("W", "X", 1), ("R", "X", None)]
assert execute((1, 0), raw) == ({"X": 1, "Y": 0}, [1])
assert execute((1, 0), raw, check=False)[1] == [0]
print("PASS: 12 of 24 orders legal, exactly those correct, unchecked read stale")

Reordering different lines below that acceptance point is invisible to every observer. It cannot break coherence (per location) or the memory model, provided H or the requester counts a write complete only at acceptance (see Completion Versus Visibility).

Related topics

• Shared course model

• Default order and early Put-Ack

• Match obligations and responses