The supplementary memory system that temporarily stores frequently used instructions and data for quicker processing by CPU of a computer.
Main memory consists of up to 2n addressable words, with each word having a unique n-bit address. there are M = 2n/K fixed length of blocks in main memory.
where K - words
The cache consists of m blocks called lines. The length of a line, not including tag and control bits, is the line size.
As there are more blocks in main memory than lines in cache, an individual line cannot be uniquely and permanently dedicated to a particular block. Thus, each line includes a tag that identifies which particular block is currently being stored. The cache connects to the processor via data, control, and address lines.
When a cache hit occurs, the data and address buffers are disabled and communication is only between processor and cache, with no system bus traffic. When a cache miss occurs, the desired address is loaded onto the system bus and the data are returned through the data buffer to both the cache and the processor.
- Key elements of Cache design
- Cache address
- Cache size
- Line size
- No of caches
- Mapping function
- Replacement algorithm
- Write policy
A logical cache or virtual cache stores data using virtual addresses whereas physical cache stores data using main memory physical addresses.
The access of logical cache is faster than physical cache.
An algorithm is needed for mapping main memory blocks into cache lines as there are fewer cache lines than main memory blocks. The mapping techniques used are direct, associative and set associative.
The direct mapping maps each block of main memory into only one possible cache line. It is expressed as
i = j modulo m
where
i - cache line number
j - block number of main memory
m - no of lines in cache
In direct mapping,
Address length = (s + w) bits
Number of addressable units = 2s+w words or bytes
Block size = line size = 2w words or bytes
Number of blocks in main memory =
2s+w
2w = 2s
Number of lines in cache = m = 2r
Size of cache = 2r+w words or bytes
Size of tag = (s - r) bits
The disadvantage of the direct mapping is that there is a fixed cache location for any given block.
The occurrence of continuous swapping of blocks in the cache and hit ratio is low is known as thrashing.
Recycling of discarded data using victim cache will lower the miss penalty. Victim cache is an approach to reduce the conflict misses of direct mapped caches without affecting its fast access time. Victim cache is a fully associative cache, whose size is typically 4 to 16 cache lines.
Associative mapping overcomes the disadvantage of direct mapping by permitting each main memory block to be loaded into any line of the cache.
In the associative mapping,
Number of lines in cache = undetermined
Size of tag = s bits
The disadvantage of associative mapping is the complex circuitry required to examine the tags of all cache lines in parallel.
The set associative mapping exhibits the strengths of both the direct and associative approaches while reducing their disadvantages. The cache consists of number sets, each of which consists of a number of lines.
In the set associative mapping,
Number of lines in set = k
Number of sets = v = 2d
Number of lines in cache = m = kv = k * 2d
Size of cache = k * 2d+w words or bytes
Size of tag = (s - d) bits
In the extreme case of v = m, k = 1, the set-associative technique reduces to direct mapping, and for v = 1, k = m, it reduces to associative mapping.
Replacement Algorithms are used to replace the existing block with new blocks in the cache once the cache is filled.
Most commonly used algorithms
- Least recently used (LRU)
- First in first out (FIFO)
- Least frequently used (LFU)
The write through is a technique by which all write operations are made to main memory as well as to the cache, ensuring that main memory is always valid. This technique generates substantial memory traffic and may create a bottleneck.
The write back is a technique by which updates are made only in the cache. When an update occurs, a dirty bit, or use bit, associated with the line is set. Then, when a block is replaced, it is written back to main memory if and only if the dirty bit is set.