Cache Coherence

Cache Coherence

1. Informal definition

   • A system is coherent if it returns the last written value of a data item.

2. Important concepts

   • Coherence
     • Ensures the use of the most current data. There are three requirements for coherence: (1) - program order preservation; (2) - coherent view of memory; (3) - serialization notion. In order to enforce coherence, one can keep track of the status of any sharing of a data block associating status bits to that block.
       • Requirements for coherence
         • (3) - serialization notion;
           • writes to the same location are serialized, i.e., two writes to the same location by any two processors are seen in the same order by all processors. Consider the following. If the value 1 and then value 2 are written to a location, processors can never read the value of the location as 2 and then later read it as 1.
         • (2) - coherent view of memory;
           • A read by the processor P1 to location X, following a write by processor P2 to X, returns the written value, if the write/read are sufficiently separated in time and no other writes to X occur between the two accesses
         • (1) - program order preservation;
           • A read by the processor P to the location X, following a write by processor P to location X, with no writes of X by another processor between the write/read by P, always returns the value written by P;
       • Most current data
       • keep track of a shared data block
       • status bit for the shared data block
   • Consistency
     • Synchronizes the reads and writes between processors. Most of the time, the programmer is responsible to synchronize the reads and writes.
       • Programmer maintains consistency
       • synchronizes reads and writes between processors
     • Ex. Possible consistency problem

3. Cache Coherence protocols

   • It is a hardware-based solution for multiprocessors to maintain cache coherence. There are basically two: the snooping and the directory-based.
   • Snooping
     • Each cache has a copy of both memory block data and “share status” of a block, e.g., shared/non-shared. As caches also share the memory bus, they snoop on the memory traffic to check if they have copies of the “in-transit” block. Snooping can be based on the write invalidate protocol, and the write update, also known as write broadcast protocol.
       • each cache has a copy of
         • Memory block data
         • share status of the block
       • Caches share the memory bus
       • Snooping memory traffic
         • Checks if there are copies of the block
       • Snooping protocols
         • Write invalidade
         • write broadcast (or write update)
     • Snooping protocols
       • Write invalidate
         • Writing in a shared block invalidates the other block copies in the other caches. Thus, when trying to access an invalid block, there is a cache miss, and the correct/most updated data comes from the “dirty” cache block. Finally, the protocol handles the memory update, following the write back approach. Writing in non-shared blocks do not cause any problem, since there is no possibility of coherence loss within non-shared blocks.
           • invalidates other blocks
           • cache miss
           • "dirty" cache block
           • writing in non-shared blocks
             • no possibility of soherence loss
           • What about the write through approach? The memory would always be coherent if following the write through approach. In that case, when trying to access/read an invalid block, it would not require a write in memory, i.e., read misses do not cause writes in the memory. It is always a fetch from the memory. However, a read miss in the write back would cause a memory write if the block to be replaced is with the dirty bit status active.
         • Ex. of write invalidade
           • Reasoning
             • Let’s assume that neither cache initially holds the data block from memory location X and that the value of X in memory is equal to 0. This is illustrated in Fig. 8.3. The illustration shows the value of processor and memory after both processor activity and bus activity have been completed. Blank stands for “no activity” or no “copy cached”. As processor A reads X, there is a cache miss and this is communicated in the bus. The data block from memory is then cached. In the same way as processor A, processor B reads memory location X, and that cache miss is also communicated through the bus. Data is cached. Next, processor A writes the value “1” in the memory location X. The new data goes only to its cache at this moment. Remember this is following the write back approach. And, considering that memory location X was shared, there is a “invalidation for X” communicated in the bus. Finally, processor B reads X again, but this time there was an “invalid X” noticed due to the last processor
         • Implementation
           • Block invalidation
             • Reasoning
               • Access to memory bus
                 • Processor sends the block address through the bus to invalidade it.
                 • Other processors snooping the bus
                   • watching if they have that block in their caches, i.e., by checking the address and invalidating the block
           • Serialized writes
             • Reasoning
               • The mechanism relies on serialized writes. The need to get access to the bus, as an exclusive resource, forces the serialization of the writes.
           • Write protocols
             • Reasoning
               • Write Through
                 • In the write through cache, all written data are always sent to the memory. Then, the most recent value of a data item can always be fetched from memory.
               • Write Back
                 • In the write back cache, if a block is clean (shared), the protocol simply acts like the write through approach. Otherwise, if the block is dirty (modified/exclusive), the protocol simply sends the dirty block in response to the read request and aborts the memory read/fetch operation
               • When locating a data item on a cache miss, write through or write back based caches can be used.
           • Simple protocol with 3 states
             • States
               • 1 - Invalid
                 • this is considered as if the block is not present in the cache
               • 2 - Shared
                 • this is considered when the block is present in one or more local/private caches (potentially shared). But, not necessarily in the processor’s cache which requested the data
               • 3 - Modified (or exclusive)
                 • this is considered when the block was updated in the local/private cache. Here, the most up-to-date information is present only in one cache. But, not necessarily in the processor’s cache which requested the data.
             • Finite-state machine
               • The finite-state machine controller is usually implemented in each core.
               • Tables of state transitions
       • Write update (write broadcast)
         • The write update protocol updates all the cached copies of a data item when that item is written. Then, it must broadcast all writes to shared cache lines, which consumes considerably more bandwidth than the write invalidate protocol.
           • Broadcast all writes to shared cache lines.
           • Consumes considerably more bandwidth
             • Thus, most of the recent multiprocessors implement write invalidate
       • Comparison between write invalidate and write update protocols
         • Points in favor of the write invalidate protocol
           • 1. - multiple writing of the same word without intervening readings require multiple broadcasts in the write update protocol, but just one initial block invalidation in write invalidate.
             • writing multiple words without readings in the middle
           • 2. - Each word written in a cache block requires a write broadcast in the write update protocol, although only the first write of any word within the block needs to generate an invalidation. The write invalidate protocol acts on cache blocks, while the write update protocol must act on individual words;
             • Write invalidade acts on cache blocks
             • Write update acts on individual words
           • 3. - The write invalidate protocol tends to generate less traffic in the memory bus. Remember that the memory bus can be seen as a bottleneck in SMP
             • Write update generates more traffic in the memory bus
             • OBS.: memory bus can be seen as a bottleneck in SMP (Symmetric multiprocessors)
         • Point in favor of write update protocol
           • 1. -The delay between writing a word on a processor and reading the value written on another processor is smaller in the write update protocol, as the written data is updated immediately in the reader’s cache
             • Delay between writing a word and reading that word from other processor is smaller in write update
               • the written data is updated immediately in the reader’s cache
   • Directory based
     • It is an alternative to snooping-based coherence protocol. A directory keeps the state of every block that may be cached. The information in the directory includes: which cache have copies of the block, whether it is dirty, block status (shared, uncached, modified).
     • Implementation
       • Distribute the directories along with the memory
       • Each directory is responsible for tracking caches that share the memory addresses of the memory portion in the node
       • OBS.: The state diagrams are the same of those used in the snooping implementation.
       • Message passing between nodes
         • Each processor keeps information on which processors have each memory block
           • field with an associated bit for each system processor for each memory block
         • Rather than snooping on the bus.
         • Needs to know which node has the block to make the invalidation

4. Is there any cache coherence problem wrt multicomputers based on message passing?

   • Reasoning
     • As long as the definition of multicomputers is: “processors with independent memories and address spaces”, there is no other computer writing on its memory, only itself. Thus, there is no problem. Although, inside each computer, the problems with cache coherence are still present

Bilder und Dateien der Mindmap