Multilevel Cache Organisation

Cache is a type of random access memory (RAM) used by the CPU to reduce the average time required to access data from memory. Multilevel caches are one of the techniques used to improve cache performance by reducing the miss penalty. The miss penalty refers to the additional time needed to retrieve data from the main memory when a cache miss occurs.

Effective Access Time = Hit rate * Cache access time + Miss rate * Lower level access time

Here,

• Hit Rate: The probability or percentage of finding data in the cache.
• Miss Rate: The probability or percentage of not finding data in the cache. (Miss Rate = 1 - Hit Rate)
• Cache Access Time: The time required to access data directly from the cache.
• Lower-Level Memory Access Time: The time required to access data from lower-level memory, such as main memory or secondary storage.

To understand this better, let us consider an example where the CPU makes 10 memory references to access the required information. We will analyze this scenario under the following three cases of system design:

Case 1 : System Design without Cache Memory 

Here the CPU directly communicates with the main memory and no caches are involved. In this case, the CPU needs to access the main memory 10 times to access the desired information.

• All memory references go directly to main memory.
• Each memory access takes 100 ns.
• Total time = 10 × 100 ns = 1000 ns

Case 2 : System Design with Cache Memory

Here the CPU at first checks whether the desired data is present in the Cache Memory or not i.e. whether there is a hit in cache or miss in the cache.

Assume: 6 cache hits, 4 cache misses (i.e., 6 accesses are served by L1, 4 go to main memory) 

• Access times:
  • L1 hits → 6 × 1 ns = 6 ns
  • Misses → 4 × (1 ns + 100 ns) = 4 × 101 ns = 404 ns

(1 ns to check L1, then 100 ns for main memory fetch)

• Total time = 6 ns + 404 ns = 410 ns

Case 3 : System Design with Multilevel Cache Memory 

Here the Cache performance is optimized further by introducing multilevel Caches. As shown in the below figure, we are considering 2 level Cache Design. It is clear that here the Miss Penalty is reduced considerably than that in the previous case thereby improving the Performance of Cache Memory. 

Average access Time For Multilevel Cache:(T_avg) 

T_avg = H₁ * C₁ + (1 - H₁) * (H₂ * C₂ +(1 - H₂) *M ) 

where 
H1 is the Hit rate in the L1 caches. 
H2 is the Hit rate in the L2 cache. 
C1 is the Time to access information in the L1 caches. 
C2 is the Miss penalty to transfer information from the L2 cache to an L1 cache. 
M is the Miss penalty to transfer information from the main memory to the L2 cache. 

Assume: 6 L1 hits , 3 L1 misses that hit in L2 ,1 full miss (goes to main memory)

• Access times:
  • L1 hits → 6 × 1 ns = 6 ns
  • L2 hits → 3 × (1 ns + 5 ns) = 3 × 6 ns = 18 ns
  • Main memory → 1 × (1 ns + 5 ns + 100 ns) = 106 ns

• Total time = 6 ns + 18 ns + 106 ns = 130 ns

NOTE : 
We can observe from the above 3 cases that we are trying to decrease the number of Main Memory References and thus decreasing the Miss Penalty in order to improve the overall System Performance. Also, it is important to note that in the Multilevel Cache Design, L1 Cache is attached to the CPU and it is small in size but fast. Although, L2 Cache is attached to the Primary Cache i.e. L1 Cache and it is larger in size and slower but still faster than the Main Memory.

EXAMPLE

Find the Average memory access time for a processor with a 2 ns clock cycle time, a miss rate of 0.04 misses per instruction, a missed penalty of 25 clock cycles, and a cache access time (including hit detection) of 1 clock cycle. Also, assume that the read and write miss penalties are the same and ignore other write stalls. 

Solution :

Average Memory access time(AMAT)= Hit Time + Miss Rate * Miss Penalty. 
Hit Time = 1 clock cycle (Hit time = Hit rate * access time) but here Hit time is directly given so, 
Miss rate = 0.04 
Miss Penalty= 25 clock cycle (this is the time taken by the above level of memory after the hit) 
so, AMAT= 1 + 0.04 * 25 
AMAT= 2 clock cycle 
according to question 1 clock cycle = 2 ns 
AMAT = 4ns 

Advantages of Multilevel Cache Organization

• Reduced access time: By having multiple levels of cache, the access time to frequently accessed data is greatly reduced. This is because the data is first searched for in the smallest, fastest cache level and if not found, it is searched for in the next larger, slower cache level.

• Improved system performance: With faster access times, system performance is improved as the CPU spends less time waiting for data to be fetched from memory.

• Lower cost: By having multiple levels of cache, the total amount of cache required can be minimized. This is because the faster, smaller cache levels are more expensive per unit of memory than the larger, slower cache levels.

• Energy efficiency: Since the data is first searched for in the smallest cache level, it is more likely that the data will be found there, and this reduces the power consumption of the system.

Disadvantages of Multilevel Cache Organization

• Complexity: The addition of multiple levels of cache increases the complexity of the cache hierarchy and the overall system. This complexity can make it more difficult to design, debug and maintain the system.

• Higher latency for cache misses: If the data is not found in any of the cache levels, it will have to be fetched from the main memory, which has a higher latency. This delay can be especially noticeable in systems with deep cache hierarchies.

• Higher cost: While having multiple levels of cache can reduce the overall amount of cache required, it can also increase the cost of the system due to the additional cache hardware required.

• Cache coherence issues: As the number of cache levels increases, it becomes more difficult to maintain cache coherence between the various levels. This can result in inconsistent data being read from the cache, which can cause problems with the overall system operation.