How many bits are we actually comparing?

Baseline: the pilot entry is 2 state bits (U/S/exclusive) plus one presence bit per cache, 4 bits for C0/C1 and 66 bits for 64 caches, tags and ECC excluded.

Now define two illustrative alternatives rather than claiming universal formats. A four-pointer entry uses 2 state bits, four core-id fields, one valid bit per pointer and one overflow bit (the Dir_i B scheme of the next lesson). A groups-of-eight coarse entry has one bit per group of 8 caches, 2 state bits and a separate exact exclusive-holder id, because a group bit cannot identify that holder. Both describe MESI coverage, not the extra dirty-responsible O tracking needed for MOESI.

Two crossovers follow from these formulas. Four pointers beat the full vector from 26 caches (so from 32 in the table; at 16 they cost 23 bits against 18). The groups-of-eight format grows as N/8 while four pointers grow only with log2 N, so it exceeds four pointers from 233 caches (256 in the table). At 1024 caches a full vector is twice the size of the 512-bit line it tracks.

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

def formats(n, pointers=4, group=8):
    assert n >= 2 and pointers >= 1 and group >= 1
    ident = (n - 1).bit_length()
    full = 2 + n
    limited = 2 + pointers * (ident + 1) + 1
    coarse = 2 + (n + group - 1) // group + ident
    return full, limited, coarse
assert formats(2)[0] == 4 and formats(64) == (66, 31, 16)  # pilot baseline
table = {16: (18, 23, 8), 32: (34, 27, 11), 128: (130, 35, 25),
         256: (258, 39, 42), 1024: (1026, 47, 140)}
for n, row in table.items():
    assert formats(n) == row
pct = {n: round(100 * formats(n)[0] / 512, 1) for n in (256, 1024)}
assert pct == {256: 50.4, 1024: 200.4}
# Crossovers: four pointers beat the full vector only from 26 caches,
# and the groups-of-eight format exceeds four pointers from 233 caches.
first = min(n for n in range(2, 2048) if formats(n)[1] < formats(n)[0])
assert first == 26 and formats(16)[1] > formats(16)[0]
over = min(n for n in range(2, 2048) if formats(n)[2] > formats(n)[1])
assert over == 233 and formats(128)[2] < formats(128)[1]
# Small-N countercase: even one pointer costs more than the full vector.
full, limited, coarse = formats(2, pointers=1)
assert (full, limited) == (4, 5) and limited > full
lines = (1024 * 1024) // 64  # 1 MiB of memory, one full-map entry per line
assert lines * formats(64)[0] // 8 == 132 * 1024
print("PASS: storage table, crossovers and small-N countercase")

Example total: a full-map directory for 1 MiB of memory keeps one entry per memory line and needs no tag, so 16,384 lines times 66 bits gives 132 KiB for 64 caches. A sparse directory instead tracks cached capacity: sized for 1 MiB of private-cache lines it has the same 16,384 entries, but each also needs an address tag, and its size no longer grows with memory. Physical SRAM rounding, ECC and pending buffers are further terms in both cases.

Related topics

• Shared course model

• Original 4/66-bit calculation