full associative cache
- A cache structure in which a block can be placed in any location in the cache
- To find a given block in a fully associative cache, all the entries in the cache must be searched because a block can be placed in any on
set associative cache
- A cache that has a fixed number of locations (at least two) where each block can be placed
- Each block in the memory maps to a unique set in the cache given by the index field, and a block can be placed in any element of that set
least recently used (LRU)
- a replacement scheme in which the block replaced is the one that has been unused for the longest time
- implemented by keeping track of when each element in a set was used relative to the other elements in the set
average memory access time (AMAT) definition
- way to examine alternative cache designs to capture the fact that the time to access data for both hits and misses affects performance
If the clock rate is increased without changing the memory system, the fraction of execution time due to cache misses _____ relative to total execution time
- increases
- can actually slow down performance
set associative
- the amount of sets in a cache
- ex. two-way set associative means two blocks per slot in the cache
- set size * number of slots = size of cache in blocks
increasing the set associativity usually ___ the miss rate but ___ the hit time
- decreases, increases
- because more items per set as you increase, takes more time to find a specific item
multilevel cache
- A memory hierarchy with multiple levels of caches, rather than just a cache and main memory
- primary cache of a multilevel cache is often smaller
- secondary is much larger than in a single-level cache, since the access time is less critical
The second-level cache in a multi-level cache is typically used to reduce the multi-level cache’s _____.
- miss penalty
- The goal of a second-level cache is to reduce the number of accesses to memory, which incur large miss penalties
global miss rate
The fraction of references that miss in all levels of a multilevel cache
local miss rate
- the fraction of references to one level of a cache that miss
- used in multilevel hierarchies
First-level caches are more concerned about _____.
Second-level caches are more concerned about _____.
- hit time, miss rate
- primary is smaller than secondary so focuses on being fast
- secondary is larger, its access time is less critical, but still want misses to be fast
average memory access time (AMAT) formula
- AMAT = hit rate * hit time + (1 - hit rate) * miss time
OR - AMAT = hit time + (miss rate * miss penalty)
loads/stores move between the ___ and the __ in the memory hierarchy
register file, cache
the operating system moves between __ and the ___ in the memory hierarchy
OS, disk
true structure of memory hierarchy
- upper level is two separate memories, lower level is unified memory
- separates by the instruction fetch and register file
- the first part is the instruction memory (IF) cache and the second part is the data memory (MEM) cache
three rules of memory hierarchy
- Lowest level in memory hierarchy stores all information long-term
- A level above is a subset of information from the level below where the level above cannot satisfy a processor memory access
- When processor stores (writes) information into the top level, that change must eventually propagate down the levels to maintain rule 1
reduce compulsory misses (2 ways)
- for static, make cache block size larger reducing number of blocks used by a program
- while dynamic, while processor is busy making accesses that hit within one block
reduce conflict misses (1 way)
- Give each set k block storage locations
- Zero conflict misses until number of in demand blocks at an index exceeds k
reduce capacity misses (2 ways)
- for hardware, increase cache capacity
- for software, reduce size of data structure temporal and/or spatial locality or machine program
how is a block found?
- Use content addressed memory (CAM) strategy
- Use tag as a key and have comparator circuit for every block storage location in that set, search simultaneously
where can a block be placed?
In direct mapped cache:
- In one specific block based on modular arithmetic
In set associative cache:
- A block can be placed in any one of the k block storage locations provided by the set
least recently used (LRU)
- when access a set, update block usage recency ranking
- a lot of times programs are the same locality for a while and then shift
not recently used (NRU)
- a approximation of the LRU that is simple and efficient
- add “recently used” bit to each cache block
- clear all recently used bits periodically, then set recently used bit each time a block is accessed
- when need to replace, choose the block with the lowest Keep Priority value using this table
