4 2 1 Cache Coherence

[Music] welcome back to this course on multi-core systems the topic of this and the next few lessons is cache coherence how do we ensure that shared data that is stored in multiple local caches is consistent that all processes see the same value in this lesson I will first illustrate the cache coherence problem and then give some properties that a coherent memory system must fulfill I inform you of the literature this lesson is based on it's based on section 5.2 of the textbook by Hennessey and Patterson caching instructions and data is needed to help to reduce the average access latency as well as the memory bandwidth requirements however caching shared data causes a problem this problem is called the cache coherence problem basically it means if there are multiple cache copies of the same data how do we ensure that all copies are the same that all copies are coherent note that we distinguish between private data and shared data private data is data used by a single court in this case there is or should be no cache coherence problem since there is only a single copy of the data shared data on the other hand is data used by multiple cores all courts want to have their own copy of this data and this causes the code in the cache coherence problem in general shared memory architectures class both shared and private data and do not distinguish between the two let me now illustrate the cache coherence problem here we have an SMP with 4 processors and their private caches and in memory there is a data item D has the value 70 now processor P zéro reads the value of D since D is not in its cache it will incur a cache miss and fetch the from memory now processor p3 also reads D D is also not in the private cache of d3 therefore it also fetches a D from memory into its private cache notice now that there are three copies of d one in memory one in the private cache of p0 and one in the private cache of p3 now p3 writes a new value let's say 24 - d let's assume we have right back caches so we write the new value only to the cache of p3 now there are still three copies of T but they are no longer coherent they are no longer the same so when P Zero again reads D it will read the old value 17 it finds in its local cache this is clearly wrong since D has gotten a new value 42 before but why do we need cache coherence well we needed to communicate in a shared memory system to illustrate this here we have a simple shared memory program containing two threats T 1 and T 2 both threats access to shared variables a and flag and initially as indicated at the top both a and flag or set to zero threat T 1 first sets a and then sets flag and threat T 2 stays in an idle loop until the flag is set to 1 then T 2 prints the value of a clearly it was the programmers intention that this program should print the value 1 he though in a very difficult way but consider now what may happen when this program is executed on this SNP let's assume threat t1 is executed on processor p0 and t2 on p1 initially flag is set to 0 in the central shared memory first processor p1 reads flag because it's not in its cache it will fetch the flag from memory test it and observe that it is zero so according to the program it should stay in its loop then p0 writes the value 1 to flag depending on whether the cache is right back or right through it will only write flag to cache or also to memory let's assume it's right back so it only so flag is only written to the cache of p0 as shown here now P 1 again reads flag now it's a cache hit and P 1 will read its own copy of the flag so it will still observe the value and keep looping keep spinning as illustrated by the circled arrow here in fact it will loop forever because without cache coherence P once cache copy of flag will never change before we look at solutions for the cache coherence problem let's try to define what a coherent memory system actually is a memory system is coherent if and only if all processes at any time have a consistent view of the last globally written value to each memory location actually this definition contains two different aspects of memory system behavior the first aspect called coherence defines what values can be returned by a read it defines the memory behavior with respect to a single location the second aspect called consistency determines when written value will be returned by a read it defines the memory behavior of reads and writes to different locations consistency will be covered in a separate lesson let's focus on coherence first a memory system is coherent if it fulfils three properties the first is that the program order or threat order must be preserved this means that a read by a processor that follows a right by the same processor with no reads in between with no rights in between by another processor returns the value written obviously we expect this to be true since it's also true in unicorns the second the second property defines what it means to have a coherent view of memory if a process appeal rights X and then another processor P prime reads X then the read will return the value written provided the read and write are sufficiently separated in time it doesn't specify how long separated in time but just sufficiently at a certain time the write should become visible finally the third property is called write serialization it means that the writes it means that rights to the same memory location or observed by all processes in the same order so if X first 100 is written to X and then 200 and then all process should observe the change of X first 100 and then to 200 and not in a different order this concludes this lesson thank you for watching in the next lesson I will describe different of cache coherence protocols stay tuned [Music]

Channel: Prof. Dr. Ben H. Juurlink

Views: 12,367

Rating: 4.9629631 out of 5

Keywords: computer architecture, embedded system

Id: BNH-3TwmVN0

Length: 9min 0sec (540 seconds)

Published: Mon Oct 22 2018