GATE CS 2008 Q35 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

The inclusion property in a multi-level cache hierarchy ($L_1$ and $L_2$) states that all data present in the $L_1$ cache must also be present in the $L_2$ cache ($L_1 \subseteq L_2$).

Let us evaluate each statement to determine if it is a necessary condition:

• Statement IV (The $L_2$ cache must be at least as large as the $L_1$ cache): This is necessary. If the capacity of $L_2$ is smaller than $L_1$, then $L_2$ cannot physically hold all the blocks that $L_1$ can hold when $L_1$ is fully utilized. Therefore, $Capacity(L_2) \ge Capacity(L_1)$ is a fundamental requirement.
• Statements I & II ($L_1$ / $L_2$ must be write-through): These are not necessary. Write policies (write-through vs. write-back) manage how updates are propagated to lower levels of the memory hierarchy. Inclusion can be maintained with write-back caches by tracking dirty states and coordinating write-backs during evictions.
• Statement III (The associativity of $L_2$ must be greater than that of $L_1$): This is not necessary. Although higher associativity in $L_2$ reduces conflict evictions, inclusion can still be strictly enforced with any associativity by using back-invalidation. When a block is evicted from $L_2$, an invalidation signal is sent to $L_1$ to evict the corresponding block if it exists there.

Thus, only statement IV is a necessary condition.