A trace sees one line for microseconds; counters see every line for seconds. They cannot name a transaction, but they say which mechanism dominates. The counter set has to be chosen so that different causes produce different counts. A set that only counts misses cannot tell a workload with too many lines from two cores fighting over one.
Counter | Increments on | What it tells you |
|---|---|---|
Misses by type: cold, capacity, conflict, coherence | Each miss, classified by why the line was absent | Cold: first touch. Capacity: working set too large. Conflict: too many lines per set. Coherence: another core's write took the line away. |
Hit-modified | A miss whose data came from another cache's M copy | Lines are moving between writers. Defined in Finding False Sharing. |
Inv sent (H) and Inv received (caches) | Each Inv | Cost of write sharing; a large gap between sent and received points at lost or filtered messages. |
Forwards | Each Fwd-GetS or Fwd-GetM from H | How often the newest data is in a cache, not memory. |
Retries and NACKs | Each rejected request | Contention at H or full resources; see Retries, NACKs and Credits. |
Directory evictions and back-invalidations | Each directory entry replaced, and each Inv it causes | The directory is too small for the sharing footprint. |
Pending-entry occupancy, average and maximum | Sampled each cycle at H | Whether H's transaction table is the bottleneck; maximum at capacity means requests are being held back. |
Classifying a miss needs a little state per line: whether this cache has ever held it, and whether it was last lost to an Inv or Fwd-GetM (coherence) or to its own eviction (capacity or conflict). Hit-modified needs only the response type. Finding False Sharing explains why hit-modified alone shows that a line moves, not which word; precise address samples supply the offsets.
Three illustrative workloads of 200 stores, alternating between C0 and C1, each core with a 2-line private cache (fully associative, so conflict misses are zero here): a false-sharing one (C0 writes offset 0 and C1 offset 8 of one line), a true-sharing one (both write offset 0) and a private one (each core cycles through three private lines). All three miss on every store. A naive counter set (accesses and misses) gives each a miss rate of 1.0 and flags them all. Hit-modified and the coherence-miss fraction separate them, and the offsets of the hit-modified misses separate true from false sharing.
from collections import Counter
CAP = 2 # lines per private cache, fully associative, LRU
def simulate(accesses):
"""Two private caches, MSI-style write permission. Returns an event log, one record per miss."""
cache = {0: [], 1: []} # LRU order, most recent last
state, ever, lost_to = {}, {0: set(), 1: set()}, {0: set(), 1: set()}
log = []
for core, line, offset in accesses: # every access is a store
other = 1 - core
if line in cache[core] and state.get((core, line)) == "M":
cache[core].remove(line); cache[core].append(line)
continue
kind = ("cold" if line not in ever[core] else
"coherence" if line in lost_to[core] else "capacity")
hitm = line in cache[other] and state.get((other, line)) == "M"
fwd = line in cache[other] # counted independently: the other cache holds the line
if line in cache[other]: # Fwd-GetM (M copy) or Inv to the other cache
cache[other].remove(line); lost_to[other].add(line)
log.append({"core": core, "line": line, "offset": offset, "kind": kind,
"hitm": hitm, "fwd": fwd})
if len(cache[core]) == CAP: # evict LRU (a PutM in the full protocol)
victim = cache[core].pop(0); lost_to[core].discard(victim)
cache[core].append(line); state[(core, line)] = "M"
ever[core].add(line); lost_to[core].discard(line)
return log
def counters(log, n_accesses):
c = Counter(r["kind"] for r in log)
c["miss"] = len(log); c["hitm"] = sum(r["hitm"] for r in log)
c["fwd"] = sum(r["fwd"] for r in log); c["access"] = n_accesses
return c
def naive_flag(c): # misses only: high miss rate means sharing trouble
return c["miss"] / c["access"] > 0.5
def diagnose(c, log):
if c["miss"] == 0 or c["hitm"] / c["miss"] < 0.5 or c["coherence"] / c["miss"] < 0.5:
return "not coherence-bound"
hot = Counter(r["line"] for r in log if r["hitm"]).most_common(1)[0][0]
writers = {}
for r in log:
if r["line"] == hot and r["hitm"]:
writers.setdefault(r["offset"], set()).add(r["core"])
return "true sharing" if any(len(w) > 1 for w in writers.values()) else "false-sharing candidate"
N = 200
false_sh = [(i % 2, 0, 8 * (i % 2)) for i in range(N)] # C0 offset 0, C1 offset 8, one line
true_sh = [(i % 2, 0, 0) for i in range(N)] # both write offset 0
private = [(i % 2, 10 + 3 * (i % 2) + (i // 2) % 3, 0) for i in range(N)] # 3 private lines each, CAP 2
results = {}
for name, w in [("false", false_sh), ("true", true_sh), ("private", private)]:
log = simulate(w)
c = counters(log, len(w))
results[name] = (c, naive_flag(c), diagnose(c, log))
cf, cp = results["false"][0], results["private"][0]
assert cf["miss"] == cp["miss"] == N # same miss count, same miss rate
assert results["false"][1] and results["private"][1] # naive counters flag both: cannot tell them apart
assert cf["coherence"] == N - 2 and cf["hitm"] == N - 1 and cf["fwd"] == N - 1
assert cp["fwd"] == 0 # private lines: never in the other cache
assert cp["capacity"] == N - 6 and cp["hitm"] == 0 and cp["coherence"] == 0
assert results["false"][2] == "false-sharing candidate"
assert results["true"][2] == "true sharing"
assert results["private"][2] == "not coherence-bound"
print(f"PASS: {N} misses each, hit-modified {cf['hitm']} vs {cp['hitm']}, only the false-sharing log is flagged")The false-sharing log has 2 cold misses and 198 coherence misses, 199 of them hit-modified (C0's first store finds no M copy anywhere); forwards, counted separately as misses that find the line in the other cache, are also 199. The private log has 6 cold and 194 capacity misses and no hit-modified or forwards at all. The naive flag is identical for both: that is the failing case, and it is why hit-modified and miss classification belong in the counter set.
# not-run: illustrative arithmetic
requests accepted at H = 0.05 per cycle (illustrative)
average time in table = 120 cycles, request to grant delivered (illustrative)
average occupancy = 0.05 x 120 = 6 entries (Little's law)
pending table size = 16 entries
average 6, maximum 16 -> bursts fill the table, requests are held back
average 15, maximum 16 -> the table is the bottleneck all the timeAverage occupancy equals arrival rate times average residence time, so a rising average with steady traffic means transactions are taking longer: more Inv rounds, slower memory or retries. A maximum pinned at the table size means admission is stalling requests, which shows up as latency the cache cannot explain. See MSHRs and Pending Entries for what an entry holds.
A: lines are moving between writers, so coherence is the cost; next, take precise address samples to see whether the writers touch the same offset (true sharing) or different offsets (false sharing). B: the misses are cold, capacity or conflict misses served from memory; next, compare capacity and conflict counts and the working-set size. Miss rate alone could not tell them apart.