Cache coherence.html (4255B)
1 <?xml version="1.0" encoding="UTF-8"?> 2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 <html><head><link rel="stylesheet" href="sitewide.css" /><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/><meta name="exporter-version" content="Evernote Mac 6.13.1 (455785)"/><meta name="altitude" content="0.008051681332290173"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2017-12-20 8:52:44 PM +0000"/><meta name="latitude" content="52.37351596501021"/><meta name="longitude" content="4.836192148060309"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2017-12-20 9:33:06 PM +0000"/><title>Cache coherence</title></head><body><div>copies of shared data may be in several caches</div><div>when any processor writes to a shared variable its cache, other caches with a copy of that variable have to be informed of the change — cache coherence</div><div>whenever a block is in a shared state, the memory owns it</div><div><br/></div><div><b>Write-through protocol</b></div><div>two ways:</div><div><ul><li>update protocol — broadcast written data to caches of all processors in the system, each processor updates contents of affected cache</li><li>invalidation protocol — broadcast invalidation requests to all processors in the system</li></ul><div><br/></div></div><div><b>Write-back protocol</b></div><div>based on concept of ownership of a block of data in the memory</div><div>creates less traffic because writes only happen in cache (unlike write-through)</div><div><br/></div><div><ul><li>at the start, memory owns all blocks and retains ownership if a block is read<br/></li><li>writing to a new block: </li><ul><li>the requesting processor must become an exclusive owner of the block</li><li>all copies must be invalidated with a broadcast request</li></ul><li>reading a modified block</li><ul><li>it’s sent by the current owner to the processor and the memory, ending up with two copies in two caches and the memory</li><li>subsequent requests for the same block are serviced by the memory module.</li></ul><li>writing to a modified block</li><ul><li>current owner sends data to requesting processor, which becomes owner</li><li>old owner invalidates its cached copy</li><li>contents of memory are <u>not</u> updated, next request for the block is serviced by the new owner</li></ul></ul></div><div><br/></div><div><b>Snoopy caches</b></div><div>all transactions in a single-bus system occur through requests/responses on bus</div><div>snooping is observing all transactions on the bus through a controller circuit</div><div>if a processor broadcasts a read request for a block owned by a processor, the memory is not allowed to respond</div><div>the owner of the block snoops on the bus and sees the request, and asserts a signal on the bus that effectively tells the memory “hell nah bitch I got this”</div><div>then the owner broadcasts a copy of the block on the bus, marks its copy as unmodified, and the response is accepted by the processor that issued the read request.</div><div>the memory also reacquires ownership of the block and updates its copy (and its shared because there’s two copies in caches of two processors)</div><div>further requests are serviced by the memory.</div><div><br/></div><div>if two processors have copies and both try to write to the same cache at the same time:</div><div><ol><li>One of the processors gets to use the bus first, broadcasts an invalidation request, and becomes the owner</li><li>The other processor snoops and invalidates its copy</li><li>When other processor gets to use the bus, it broadcasts a read-exclusive request (read + invalidation request)</li><li>Owner snoops the read-exclusive request, provides a data response, and invalidates its copy (other processor becomes new owner)</li></ol><div><br/></div></div><div>an alternative in large shared-memory multiprocessors is directory-based cache coherence, where there are directories in each memory module which indicate which nodes can have copies of a given block</div><div>if a block is modified, the directory identifies node that is current owner</div><div><br/></div></body></html>