Cache Inclusion Assume you have an L2 cache that is direct-mapped with 4 sets

/ Exams & Certification / By

Cache Inclusion Assume you have an L2 cache that is direct-mapped with 4 sets. Assume L1 cache is fully-associate with capacity of 2 blocks and it uses LRU policy If you know that blocks A, B, C and D map to sets 0, 1, 2 and 3 in L2 Cache. If you know the current state of both L1 and L2 cache is as following: Set 0 LRU t 1 Set 2 DIC Set 3 L1 Cache L2 Cache .If our next access is for block E that maps to set 3 in L2 cache, fill/describe the state of the caches after the access, if we use: Inclusive L2 Cache Non-Inclusive L2 Cache

The Correct Answer and Explanation is :

Here’s the step-by-step explanation for the given scenario:

Assumptions:

  1. L2 Cache: Direct-mapped with 4 sets (Set 0 to Set 3).
  2. L1 Cache: Fully associative with a capacity of 2 blocks and uses LRU replacement.
  3. Current State:
  • L1 Cache: Contains A and B (most recently used first order assumed as A, B).
  • L2 Cache:
    • Set 0: Contains A.
    • Set 1: Contains B.
    • Set 2: Contains C.
    • Set 3: Contains D.
  1. Block E maps to Set 3 in L2 Cache.

Access: Block E (maps to Set 3 in L2)

Case 1: Inclusive L2 Cache

  • Rule: L1 cache must contain only blocks also present in L2 cache.
  • Access flow:
  1. Block E replaces D in Set 3 of L2 (due to direct mapping).
  2. Since D is removed from L2, it must also be invalidated in L1 (inclusive property).
  3. Block E is loaded into L1.
  4. L1 now updates based on LRU replacement:
    • Since A and B are in L1 and the capacity is 2, the least recently used block (B) is evicted to accommodate E.
  • Final State:
  • L1 Cache: A, E (most recent first).
  • L2 Cache:
    • Set 0: A.
    • Set 1: B.
    • Set 2: C.
    • Set 3: E.

Case 2: Non-Inclusive L2 Cache

  • Rule: L1 and L2 are independent; L1 may contain blocks not present in L2.
  • Access flow:
  1. Block E replaces D in Set 3 of L2 (due to direct mapping).
  2. No invalidation occurs in L1 (non-inclusive property allows D to remain in L1).
  3. Block E is loaded into L1. Based on LRU, B (least recently used in L1) is evicted.
  • Final State:
  • L1 Cache: A, E (most recent first).
  • L2 Cache:
    • Set 0: A.
    • Set 1: B.
    • Set 2: C.
    • Set 3: E.

Key Difference:

  • Inclusive L2 Cache: Blocks evicted from L2 are invalidated in L1.
  • Non-Inclusive L2 Cache: No invalidation in L1 occurs when blocks are evicted from L2.

Related Posts

Scroll to Top