Cache Coherence: Copyback / Invaldiate Protocol

Copyback / Write Invalidate Model

The HASE Copyback / Write Invalidate protocol model (shown in the figure) is based on the Write Invalidate protocol described in section 8.9 of Michael J. Flynn's book on "Computer Architecture" (ISBN 0-86720-204-1). It uses direct mapped caches in a system containing four processors (numbered 1-4 because the memory is assigned as 0 in the model), each with its own cache, and a main memory, all interconnected by a bus.

The Memory simply contains data values. The processors are modelled as arrays containing sequences of read and write requests to locations in the memory address space, e.g.

R 0 0

R 9 0

W 1 475

W 1 541

Z 0 0

Both read and write requests require a data field, because of the way the processor is modelled. At the start of the simulation, each processor sends its first request to its cache and, when it receives a response, issues the next request in the succeeding clock period. When it encounters a request which is not r, R, w or W, this is treated as an end-of-list marker and the processor then increments a global nodes_done variable. nodes_done is monitored by the Bus in each clock period and when it reaches 4, the Bus stops the simulation. If the user omits an end-of-list marker, the simulation will eventually be stopped by a time-out.

The caches each contain 8 lines, each of which contains the following fields:

Valid

Modified

Address

Data

The caches send and receive packets to/from their respective processors and to/from the Bus. The actions that occur in response to a processor packet depend on whether it is a read or write request, whether the request gets a hit or a miss, and the current state of the line to which the request is mapped. Many of the actions involve the exchange of packets between the cache and the Bus. Bus packets contain the following fields:

Packet Type	IV	Invalidate
	MA	Memory Read Acknowledge
	MR	Memory Read Request
	MW	Memory Write Request
	RR	Read Request
	WR	Write Request
Address
Data
Source	Number of the originating cache

Read Requests

Outcome	State	Action
Read Hit Unmodified	RH	Supply data to processor; state remains unchanged
Read Hit Modified	RH	Supply data to processor; state remains unchanged
Read Miss Umodified	RM	1. Send Read Request (RR) to Bus 2. Wait one clock cycle; if another cache has a modified value, it writes the value to memory during this cycle and sets itself Valid 3. Issue Memory Read (MR) 4. When memory replies (MA), write data to and supply to processor
Read Miss Modified	RMM	1. Write existing data to memory (MW) 2. Proceed as for Read Miss Unmodified

Write Requests

Outcome	State	Action
Write Hit Unmodified	WH	1. Send Invalidate packet to Bus 2. Write data to cache 3. Set state to Modified when Invalidate (IV) packet has been sent
Write Hit Modified	WHM	Write data to cache; state remains unchanged
Write Miss Unmodified	WM 1. Send Write Request (WR) to Bus 2. Wait one clock cycle: (a) if another cache has a Modified value, it writes the value to memory during this cycle and sets itself Invalid (b) if other caches have Valid but Unmodified copies, they set them to Invalid 3. issue Memory Read (MR) 4. when memory replies, write data to cache
Write Miss Modified	WMM	1. Write existing data to memory (MW) 2. Proceed as for Write Miss Unmodified

Bus Packets

When a cache receives a packet from the Bus, it first checks to see if the address in the packet matches a valid address in one of its lines. If not, it takes no action; if it does match, the actions are as follows:

IV Set state to Invalid

MA Write data to cache and (for read requests) send to processor

RR If state is Modified, send MW request to Bus to write value back to memory; set state to Valid & Unmodified

WR If state is Modified, send MW request to Bus to write value back to memory; set to Invalid & Unmodified
If state is Unmodified, set to Invalid & Unmodified

If a read or write request is pending when an IV, RR or WR packet is processed (i.e. the cache is waiting for a turn on the Bus), the cache must recheck its entries for a hit or miss.

The Bus

The Bus has five pairs of inputs and outputs, one pair for each of the caches and one for the Memory. Access to the Bus is controlled by a request/grant mechanism, together with a round-robin priority system. Each cache can make requests to take ownership of the bus but, at any one time, only one request can be granted. Whilst a particular cache has ownership of the Bus, it can send packets to and receive packets from the Memory. Because the Memory only sends packets in response to cache requests, it does not need Bus ownership. Likewise, when a packet sends out Read or Write requests to check for the presence of a modified copy in another cache of the data it requires, a responding cache (there can only be one) does not need Bus ownership.

The processor array files included in the model contain a series of Read and Write requests which demonstrate several of the protocol actions. Users of the model are invited to observe the simulation play-back to see their effects.

HASE Project
Institute for Computing Systems Architecture,
School of Informatics, University of Edinburgh
Last change 15/11/2010

IV	Set state to Invalid
MA	Write data to cache and (for read requests) send to processor
RR	If state is Modified, send MW request to Bus to write value back to memory; set state to Valid & Unmodified
WR	If state is Modified, send MW request to Bus to write value back to memory; set to Invalid & Unmodified If state is Unmodified, set to Invalid & Unmodified