Cache coherence

• Concerns different processors accessing the same address/cache block
• Cache coherence protocols:
  • Snooping protocols: each local cache controller monitors a shared bus for memory requests to ensure all caches have a consistent view by updating/invalidate cache blocks
    • Snoopy-cache protocols are not used in NUMA architectures because the latency of a message increases with the number of processor nodes
  • cc-NUMA: directory-based cache coherence…

MSI

• 3 states:
  • Modified: cache block is modified by the local core
  • Shared: appears and its data is consistent in other cores
  • Invalid: does not present in the cache or is invalidated by a bus request, must be fetched again
• State machine for each cache block:
  • N.B. deterministic finite-state automaton is a 5-tuple: (Q, sigma, delta, S, F)
    • Q: set of possible states
    • Sigma: alphabet
    • Delta: transition function, a mapping from Q * sigma to Q
    • S: start state
    • F: set of accepting states
  • Q = {M, S, I}
  • Sigma:
    • PrRd (processor read)
    • PrWr (processor write)
    • BusRd: when read miss occurs, place a read request and expect the data to be returned
    • BusRdX: when write miss occurs, place a readX request, which returns the cache block and invalidates the cache block in the caches of other cores
    • …

  • Start state: I

MESI

Additional exclusive state…

MOESI

Additional owned state…

False sharing

2 threads on 2 cores read/write 2 different variables, but those 2 variables may both lie in the same cache line => need to keep broadcasting the changes despite not sharing the data!

Cache consistency

• Concerns different processors accessing different addresses/cache blocks
  • To reorder or avoid blocking instructions => improve performance

Consistency models

• Sequential consistency
  • RR requirements:
    • For example: read a pointer, then read the value at this pointer address
• TSO: batch write requests
  • Relaxed WR order: a Read request may complete before a preceding Write request has become visible to all other processors