Cache Coherence

Introduction

Cache coherence is related to a multiprocessor system. Cache coherence defines what values can be returned by a read operation generated by a processor i.e, how do other processors see a memory update?

A Multiprocessor system should ensure all cached copies of a block are coherent.

Let’s understand the cache coherence problem through example.

Recommended Topic, Microinstruction in Computer Architecture

Schemes for enforcing cache coherence

Following schemes are considered for enforcing cache coherence. 

(i) Write-invalidate (ii) Write-update (iii) Write-once

Write-invalidate

In the write-invalidate scheme, a write to shared data X on block B by processor P1 - 

1. Invalidates all other cached copies of B (but not MM copy,(Figure a)). However, for write-through, X in the main memory will be modified (Figure. b).

2. A subsequent request for B, by other processor than P2, is treated as miss.

Write-update

To overcome the cache coherence problem, in the write-update scheme an updation in block B of processor Pi’s cache, updates all cached copies of B and MM (main memory) copy.

Write update scheme requires high bandwidth as it requires broadcasting as each write is followed by an update and consecutive writes to the same block, with no read, require multiple write broadcast.

Let’s visualize through the below figures.

Write-once

The principle of the write-once scheme is

1. If a block B in cache Ci at processor Pi is written for the first time, All cached copies of B are declared invalid (I) and the MM copy is updated. 
2. If next time B is updated in Ci, no invalidation message is generated. MM write follows - write-back policy. 
3. When Pj tries to access B, B is supplied to Cj from Ci. MM copy is also updated.

For small-scale multiprocessors, we adopt a hardware solution for cache coherence. Two major hardware-based coherence solutions are

 (i) Snoopy protocol, and (ii) Directory-based protocol.

Snoopy protocol

Snoopy protocol is effective in a system with the broadcast network (like a bus).

The following figures describe snoopy protocol-based system with two processors P1/P2

A snoopy protocol-based system can adopt any one of the following techniques.

 Write-update or write-broadcast (WU) Write-invalidate (WI) Competitive-update (CU)

Directory-based protocol

In snoopy, the update is done through broadcasting. Broadcasting demands heavy network bandwidth. In a system with a large number of processors (CMPs), broadcasting is expensive. A directory-based protocol Issues coherence commands only to cached copies affected by an update. 

A directory consists of a set of vectors (sharing vectors)

Also See, Shift Registers in Digital Electronics

FAQs

1. What is multiprocessing?
   In terms of the operating system, the concept of multiprocessing simply put is the execution of many concurrent (simultaneously running) processes in a system where each process is running on a separate CPU or a core.
    
2. What are the various strategies that can be used to ensure cache coherence?
   To solve the cache coherence problem there are both software and hardware-based approaches to achieve cache coherence. In a software based approach, a compiler-based cache coherence mechanism is used in which we optimize the program to avoid cache coherence issues by treating potential shared variables which may cause cache coherence issues separately. While in a hardware-based approach, mainly Directory-based cache coherence protocols and Snoopy protocols can be utilised to keep the caches in sync.