|
|
|
|
|
|
|
Now a miss to E1 creates a reference R1 - 4, which will make the caches inconsistent, as the new line will replace R2 - 1 in L2 and R1 - 3 in L1. |
|
|
|
|
|
|
|
|
Logical inclusion can be achieved in two ways: |
|
|
|
|
|
|
|
|
1. By actively forcing the contents of the two cache levels to be the same. |
|
|
|
|
|
|
|
|
2. By passively assuring the same contents by choosing consistent parameters/policies for both cache levels. |
|
|
|
|
|
|
|
|
When logical inclusion is required, it probably is necessary to do both active and passive inclusion. Attention to the requirements for passive inclusion eliminates the possibility of thrashing lines between the cache levels. Some active control is useful to insure consistent line replacement. |
|
|
|
|
|
|
|
|
Assuming LRU replacement in both levels, passive inclusion will be violated if and only if we do not provide L2 entries for all L1 entries. Obviously, L2 must be at least as large as L1. Let us define the following: |
|
|
|
|
| | |
|
|
|
|
set size * number of sets |
|
|
|
| | | |
|
|
|
|
(line size * assoc) * number of sets, |
|
|
|
|
|
|
|
|
|
|
where set size = (line size * assoc). |
|
|
|
|
|
|
|
|
The crucial requirement for passive inclusion is that the number of L2 sets has to be greater than or equal to the number of L1 sets, irrespective of L2 associativity. (Assume that the L2 line size is at least as large as L1.) If this were not true, multiple L1 sets would depend on a single L2 set for backing store. Hence, references to a given L1 set can affect the backing store for another L1 set. |
|
|
|
|
|
|
|
|
Another requirement is that the L2 associativity be no less than that of L1, irrespective of the number of sets. For a L1 associativity greater than L2's, there will be many L2 entries backing for a given L1 set. Each L2 entry can hold many lines that can go into the L1 set. Therefore, it is possible to have many references to an L1 set such that each would hit in the same L2 entry. Since the L2 associativity is lower, it will have to replace valid L1 lines before L1 starts to replace. |
|
|
|
|
|
|
|
|
Let us formalize these constraints: If |
|
|
|
|
|
