Caching technology and techniques.

Cache Levels
  High speed memory - usually static ram.

  Level 1 - part of CPU
    16 to 64 KB
    Spit cache - instructions and data is separate cache units.

  Level 2 - external to CPU but on high speed local bus
    512 KB to 1 MB.
    Unified cache.

  Level 3 - on PCI or standard bus, static ram with no waits
    EDO and SDRAM make this less common.

Cache mapping
  When a main memory byte is accessed,
    All consecutive bytes in the line holding that byte are duplicated 
      in the appropriate cache line.

    Address of main memory segment holding that line is also stored in 
      cache.

  Because of segment ids, caches are designed for specific memory sizes.


Direct Cache
  Lines in main memory are mapped to identical line in cache.
    Any line zero from any segment will go into line zero of cache.
    Only one line zero can be in the cache at a time.

  Segment id of line being buffered in cache is also recorded in cache.

  Easy to implement.

  Poor performance in systems using virtual memory.

  Line = int( mem@ % size of cache / line size ).

  Tag (segment id) = int( mem@ / cache size ).
    Tag size is just the bits to hold the segment id,


Direct cache access
  Parse the main memory address to be accessed.
  Determine which cache line is being accessed
  Determine segment id of line of interest.
  If cache line is in use (valid flag - for initial access).
    If current tag in cache line matches tag of main memory.
      Use data in cache line. (Hit).

    Else
      Swap out current line. (Miss).

  Else
    Fetch line from main memory into cache. (Miss).

Associative cache features
  Any line from memory can be placed by any line in cache.
    This means that there can be several line 0s in the cache.

  Tag must be big enough to contain both the segment id and line id.

  All tags must be searched in parallel.

  Not practical.


Set associative
  A compromise that takes advantage of both direct and associative
  caching.

  Composed of 2, 4 or 6 direct caches, each containing a slot for
  each line.

  6 way has only about a 13% advantage over 4 way.

  Calculate line id.

  Check specific cache line in each sub-cache for matching segment id.
     If found (hit)
       Use that cached line. 

     Else if not found (miss)
       Check specific cache line in other sub-caches for empty slot.
       If empty line found.
         Use that cache line.

       Else 
         Swap out existing line.


Selecting slots
  In associative and set-associative, if no lines available a choice must 
    be made.

  Choice algorithms.
    First In First Out (FIFO) - oldest line replaced, Cached line time 
      stamped when first loaded into cache.

    Least Frequently Used (LFU or LU) - least used.
      Counter relative to other lines (constant update).

    Least Recently Used (LRU) - oldest access time.
      Time stamped when ever accessed.


When to refresh main memory
  When data is changed in cache,
    it needs to be mirrored in main memory.

  Two policies.
    Write through
      Change in cached data immediately copied to main memory.
      Easy to implement.
      Requires more main memory access (defeats caching).

    Write delayed
      Write data when line needed by different segment access.
      Less secure - ex. NMI may cause loss of cached data.
      Complicates virtual memory machines.

  Some systems will skip caching if memory access is a write and not
    already cached.