Extend H into two home instances H0 and H1, with exactly one selected home per line. C0/C1 remain the requesters. Compare two illustrative mappings of the line number, address // 64. The simple map, home = (address // 64) % 2, uses only bit 6 of the address. The parity hash, home = popcount(address // 64) % 2, XORs every line-number bit together. X at address 0 belongs to H0 under both. These are design exercises, not mappings attributed to any processor. Every conflict on X still goes to its one home.
Eight accesses | Lines touched | Simple map H0 / H1 | Parity hash H0 / H1 |
|---|---|---|---|
Stride 64: 0, 64, ..., 448 | 0 to 7 | 4 / 4 | 4 / 4 (parities 0, 1, 1, 0, 1, 0, 0, 1) |
Stride 128: 0, 128, ..., 896 | 0, 2, ..., 14 | 8 / 0: the stride never changes bit 6 | 4 / 4 |
Stride 256: 0, 256, ..., 1792 | 0, 4, ..., 28 | 8 / 0 | 4 / 4 |
Stride 192: 0, 192, ..., 1344 | 0, 3, ..., 21 | 4 / 4 | 7 / 1: popcounts 0, 2, 2, 2, 2, 4, 2, 3 |
Eight requests to X = 0 | 0 only | 8 / 0 | 8 / 0: no address map splits one line |
The parity hash fixes the 128- and 256-byte strides that alias the simple map, because a stride that never changes bit 6 still changes higher bits that the XOR includes. It is not stride-proof: stride 192 (three lines) gives an even popcount for seven of the eight lines, while the simple map balances it. Every fixed map has some pathological stride; a hash moves it to strides that are less common in real code. No map can spread a single hot line, because all its accesses share one line number.
from collections import Counter
def mod2(address):
return (address // 64) % 2 # bit 6 of the address
def parity(address):
return bin(address // 64).count("1") % 2 # XOR of all line-number bits
def demand(home, stride, n=8):
c = Counter(home(stride * i) for i in range(n))
return (c[0], c[1])
for stride in (64, 128, 256):
assert demand(parity, stride) == (4, 4)
assert demand(mod2, 64) == (4, 4)
assert demand(mod2, 128) == demand(mod2, 256) == (8, 0)
assert [bin(3 * i).count("1") for i in range(8)] == [0, 2, 2, 2, 2, 4, 2, 3]
assert demand(parity, 192) == (7, 1) # a stride that defeats the hash
assert demand(mod2, 192) == (4, 4) # but not the simple map
for home in (mod2, parity):
assert Counter(home(0) for _ in range(8)) == {0: 8} # one hot X
assert home(0) == home(8) == home(63) # one home per line
print("PASS: parity balances 64/128/256 strides but not 192, mod 2 the reverse, one hot X stays 8/0")The count measures offered address demand, not service time. A balanced line count may still contain one expensive dirty intervention at one home and cheap hits at the other. Measure per-home queue occupancy, active time and request mix as well as request counts. Pending entries and finite completion buffers can be the limiting resource.
The mappings are compared as static choices fixed before traffic starts; changing one while lines are cached would need a separate migration protocol.
It must resolve C0's current data through the selected protocol. Selecting H0 by address does not make memory current.