Mapping functions.html (2860B)
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.006018927320837975"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2017-12-17 7:24:46 PM +0000"/><meta name="latitude" content="52.37352693909417"/><meta name="longitude" content="4.836185782601543"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2017-12-17 8:44:26 PM +0000"/><title>Mapping functions</title></head><body><div>consider (with 16-bit addressable memory):</div><div>cache — 128 blocks of 16 words each = 2048 words (2K)</div><div>main memory — 4096 blocks of 16 words each = 64K words</div><div>valid bit — 0 when power first turned on. set to 1 when a memory block is loaded into a location. the processor only fetches data from a cache block if the valid bit is 1.</div><div>cache flushing — forcing all dirty blocks to be written back to memory</div><div><br/></div><div>Direct mapping:</div><div><ul><li>block <span style="font-style: italic;">j</span> of main memory is block <span style="font-style: italic;">j</span> modulo 128 of cache</li><ul><li>e.g. block 0, 128, 256… of memory is stored in cache block 0</li><li>e.g. block 1, 129, 257… of memory is stored in cache block 1</li><li>etc.</li></ul><li>replacement algorithm is trivial — placement of block is determined by its memory address (three fields tag, block, word)</li></ul><div><br/></div></div><div>Associative mapping:</div><div><ul><li>a main memory block can be placed into any cache block position</li><li>12 tag bits identify a memory block in the cache</li><li>new block replaces an existing block only if cache is full</li><li>more efficient use of space, but higher complexity because of need for parallel tag search (associative search)</li></ul><div><br/></div></div><div>Set-associative mapping</div><div><ul><li>blocks of cache are grouped into sets, mapping allows block of main memory to be in any block of a specific set</li><li>gets rid of problem of contention because of a few choices for block placement</li><li>hardware cost reduced because smaller associative search</li></ul><div><br/></div></div><div><b>Replacement algorithms</b></div><div>LRU replacement algorithm</div><div><ul><li>overwrite least recently used block (the one that’s gone the longest without being referenced)</li><li>cache controller must track references to all blocks</li><li><br/></li></ul><div><br/></div></div><div>Random algorithm — quite effective in practice</div><div><br/></div><div><br/></div></body></html>