Cache Memory Flashcards
Explain the Storage Hierarchy
This is a pyramid with the fastest memory on top and the slowest on the bottom. Also the higher up the pyramid, the more it costs and the less capacity there is.
What is Direct Mapping?
A memory block J can only be placed in one place I in the cache. It is easy to look up and the translation is simple.
What is Associative Mapping?
It is a mapping technique where it is allowed to write blocks anywhere in cache (we are free to choose where)
Explain the (k-way) Set Associative Mapping
The cache gets divided into v=2^d sets, each containing k (= C/v) lines. Each block in memory will be allowed to be located into only one of these sets.
In Set Associative Mapping, give some special values for k
If k == 1 -> direct caching
If k == C -> associative caching
K is usually very small and sufficient to reduce trashing
Replacement Algorithms: what and why?
These are algorithms to determine where to replace a value in cache. We need this because with associative cache, we can chose where to put a block. This algorithm must be very efficient in hardware.
Optimal -> replace lines that are less likely needed in the future -> not implementable
What is the Random Replacement Algorithm?
It is a simple algorithm. There is no work at hit. It is not very intelligent and susceptible to thrashing.
It is provable the worst case algorithm in certain contexts
What is the FIFO Replacement Algorithm?
We replace the oldest line first because we have the assumption that those are requested least frequently in the future. For the implementation only one pointer is required. There is less thrashing.
- Replace oldest line
- oldest = least requested in future
- one pointer required
- less trashing
What is the LRU algorithm?
- Replace least recently used line
- Best algorithm in certain context
- Very effective against trashing
- Does not use frequency info
- Sensitive to scan sequence
What are the two Pseudo-LRU’s and why are they used?
Goal: Performance of LRU + simplicity of FIFO
2 variants:
- tree based
- Most recently used
Memory Updates: what and why
What: keeping cache and main memory synchronized
Why: when cache gets updated, there can be discrepancies
-> problematic, other components access directly
What are the 2 techniques for memory updates?
Write through:
- simplest but least efficient
- every update in cache gets pushed to memory
- causes extra traffic in data bus
Write back:
- flag modified cache parts with an update bit
- block out of cache -> check update bits and update memory
What is benchmarking?
Repeatedly request elements from an array A with fixed stride 2^k
Repeat this for different arrays whose size is doubled each time
Measure the average access-time for different array size and stride values
What is locality of reference?
Locality of reference refers to the tendency of the computer program to access the same set of memory locations for a particular time period. On an abstract level there are two types of localities: spatial & temporal locality
What is spatial locality?
This type of optimization assumes that if a memory location has been accessed it is highly likely that a nearby/consecutive memory location will be accessed as well and hence we bring in the nearby memory references too in a nearby memory location for faster access.
