Cache Basics

CACHE  BASICS

Basic Ideas

The cache is a small mirror-image of a portion (several "lines") of main memory. cache is faster than main memory ==> so maximize its utilization

 cache is more expensive than main memory ==> so it is much smaller

Locality of reference

The principle that the instruction currently being fetched/executed is very close in memory to the instruction to be fetched/executed next. The same idea applies to the data value currently being accessed (read/written) in memory.

If we keep the most active segments of program and data in the cache, overall execution speed for the program will be optimized. Our strategy for cache utilization should maximize the number of cache read/write operations, in comparison with the number of main memory read/write operations.

Example

A line is an adjacent series of bytes in main memory (that is, their addresses are contiguous). Suppose a line is 16 bytes in size. For example, suppose we have a 2¹²= 4K-byte cache with 2⁸ = 256 16-byte lines; a 2²⁴ = 16M-byte main memory, which is 2¹² = 4K times the size of the cache; and a 400-line program, which will not all fit into the cache at once.

Each active cache line is established as a copy of a corresponding memory line during execution. Whenever a memory write takes place in the cache, the "Valid" bit is reset (marking that line "Invalid"), which means that it is no longer an exact image of its corresponding line in memory.

Cache Dynamics

When a memory read (or fetch) is issued by the CPU:

1.     If the line with that memory address is in the cache (this is called a cache hit), the data is read from the cache to the MDR.

2.     If the line with that memory address is not in the cache (this is called a miss), the cache is updated by replacing one of its active lines by the line with that memory address, and then the data is read from the cache to the MDR.

When a memory write is issued by the CPU:

1.     If the line with that memory address is in the cache, the data is written from the MDR to the cache, and the line is marked "invalid" (since it no longer is an image of the corresponding memory line

2.     If the line with that memory address is not in the cache, the cache is updated by replacing one of its active lines by the line with that memory address. The data is then written from the MDR to the cache and the line is marked "invalid."

Cache updating is done in the following way.

1.     A candidate line is chosen for replacement using an algorithm that tries to minimize the number of cache updates throughout the life of the program run. Two algorithms have been popular in recent architectures:

-  Choose the line that has been least recently used - "LRU" for short (e.g., the PowerPC)

-  Choose the line randomly (e.g., the 68040)

2.     If the candidate line is "invalid," write out a copy of that line to main memory (thus bringing the memory up to date with all recent writes to that line in the cache).

3.     Replace the candidate line by the new line in the cache.