Screen Version

School of Computer Science & Engineering
University of New South Wales
 Advanced Operating Systems 
 COMP9242 2002/S2 

Hardware cache coherency

• Ensure consistency of all caches and RAM.

Write-invalidate protocols:

 Ensure that:

• only a single cached copy of the data exist at the time of a store,
• dirty lines will propagate to memory prior to being read into any other cache.

Write-update protocols:

 Update all cached copies at the time of a store.

• Note: Similar (software) protocols are used in distributed systems.

Write-through invalidate protocol

Two versions:

1. All stores write through the cache.
   • RAM is always consistent with cache.
   • No dirty cache lines ever.
2. Cache snoops bus for write cycles and invalidates any copies.

Normal bus arbitration resolves race conditions.

• Can cache spin locks, Decker works...
• Cannot use write-back caching.
• Need bus cycle for each store ==> limited scalability.

Write-once protocol

Works with write-back caches:

• First store to clean line writes through cache.
• Store to uncached line allocates in cache.
• Further stores to same line only write to cache.
• Cache snoops bus for write cycles and invalidates any copies.

Normal bus arbitration resolves race conditions.

• Introduces new state for a cache line: reserved.

Write-once state diagram:

• Note: Store miss can occur from any state, not only invalid:
• The line may have held different valid or dirty data.

MESI protocol

Named after initials of states: Modified-Exclusive-Shared-Invalid.

• Like write-once, except that a load miss on a line which is
  not in any cache goes directly to the exclusive state.

• Snoop load hits require cache to assert it has the line.

Used in many modern SMP architectures.

Write-invalidate protocols:

• Based on the assumption that shared data is likely to remain shared.

• Basic protocol similar to MESI, but:
  • stores to shared data update all copies,
  • updating cache assert share status,
  • move to exclusive state if no other CPU holds copy.

• MIPS R4000 update protocol includes additional modified-shared state, which updates other caches but not RAM.

Wastes bus cycles if lines cease to be shared.

H/W cache coherency issues

• On miss may read data from other cache (faster).

• Some architectures (MIPS R4000) offer choice of protocols.
  • Must chose most appropriate one for application.

• Cache coherency is based on cache lines.
  • Potential of false sharing.

• H/W coherency generally restricted to physical caches.
  • No problem with L2 cache.
  • Use inclusion property for L1 cache: .