GATE CSE 2014 | Set 1 | Question: 44

Question

An access sequence of cache block addresses is of length $N$ and contains n unique block addresses. The number of unique block addresses between two consecutive accesses to the same block address is bounded above by $k$. What is the miss ratio if the access sequence is passed through a cache of associativity $ A\geq k $ exercising least-recently-used replacement policy?

• A. $\left(\dfrac{n}{N}\right)$
• B. $\left(\dfrac{1}{N}\right)$
• C. $\left(\dfrac{1}{A}\right)$
• D. $\left(\dfrac{k}{n}\right)$

Comments

Bounded above means upper bound and bounded below means lower bound.

“Bounded above by k” means at most k (never more than k).

---

The correct answer is A. $\left(\frac{n}{N}\right)$
 

The Initial Misses (Compulsory Misses)

The access sequence has a total length of $N$, but it only contains $n$ unique block addresses.

When the cache first turns on, it is empty. Every time one of these $n$ unique blocks is requested for the very first time, the cache will not have it. This results in an unavoidable miss. Therefore, we are guaranteed to have exactly $n$ compulsory (or cold-start) misses.

The Re-accesses (Surviving Eviction)

After a block is brought into the cache, what happens when we need to access it again? To find out if it's still in the cache (a hit) or if it was evicted (a miss), we have to look at the rules provided:

• The Gap: There are at most $k$ other unique blocks accessed between two consecutive accesses to our target block.

• The Cache: It uses a Least-Recently-Used (LRU) policy and has an associativity of $A$, where $A \ge k$.

To mathematically guarantee a cache hit on a re-access, we must evaluate the absolute worst-case scenario: What if the access pattern is so unlucky that all $k$ intervening blocks map to the exact same cache set as our target block?

 

The Role of Associativity ($A \ge k$)

Associativity only matters when multiple blocks fight for space in the same set. In our worst-case scenario, all $k$ intervening blocks flood into our target block's set.

Here is how the associativity rule saves the day:

• Associativity ($A$) defines exactly how many "slots" exist within a single set.

• If $k$ new blocks enter the set, they push our original target block down the LRU stack toward eviction.

• However, because the problem guarantees that $A \ge k$ (the number of slots is greater than or equal to the number of invading blocks), the set is physically large enough to hold all $k$ new blocks plus our original target block.

• Our block might become the absolute "Least Recently Used" block at the bottom of the stack, but it will not be kicked out.

 

The Final Calculation

Because our block survives the absolute worst-case mapping scenario, it will certainly survive any normal scenario where the $k$ blocks are scattered across different sets.

Therefore, every single re-access to a block is guaranteed to be a cache hit. There are zero conflict misses and zero capacity misses. The only misses that occur in the entire sequence are the initial $n$ compulsory misses.

$$\text{Miss Ratio} = \frac{\text{Total Misses}}{\text{Total Accesses}} = \frac{n}{N}$$

---

Meaning Of Each and every Line with detailed explanation :

An access sequence of cache block addresses is of length $N$ and contains $n$ unique block addresses.

Meaning of this Line  ==> The CPU requests data from memory $N$ times in total. However, among those $N$ total requests, there are only $n$ distinct (different) memory blocks being asked for. 

The number of unique block addresses between two consecutive accesses to the same block address is bounded above by $k$.

Meaning of this Line ==> Whenever a specific block  is accessed and then accessed again later, the number of different other blocks requested in between those two accesses is at most $k$.

For examples : B1--> B2 --> B3 --> B1 between first B1 and second B2 accessed the block accessed are B2 & B3 ..That means unique block between two consecutive access to same block = 2 

If the access sequence is passed through a cache of associativity $A \ge k$

Meaning of this Line ==> The cache set can hold at least $A$ blocks, where $A$ is greater than or equal to $k$.

Solution by taking examples

Sequence length ($N$) = $8$

Unique blocks ($n$) = $3$ 

Maximum unique intermediate blocks ($k$) = $2$

Cache Associativity ($A$) = $3$ 

Sequence: B1,B2,B3,B1,B2 ,B3,B1,B2

1st access (B1) : Not in cache $\rightarrow$ MISS (Compulsory). Cache = B1

2nd access (B2): Not in cache $\rightarrow$ MISS (Compulsory). Cache = B1,B2

3rd access (B3): Not in cache $\rightarrow$ MISS (Compulsory). Cache = B1,B2,B3

4th access (B1)

Between 1st B1 and 2nd B1, unique blocks accessed = B2,B3.

B1 was never evicted because cache capacity $A \ge 2$. It means that B1 is present so there is "HiT"

Subsequent accesses (B2,B3,B1,B2): All were previously loaded and never evicted because $A \ge k$. So All are Hit

Note : capacity Miss =0 , conflict Miss =0 ,compulsory miss = 3 ... So total miss = 3 which is equal to n..

hence , Miss Ratio = Total Miss / Total Access = 3/ 8 = n / N

Answer 1

 

Correct Answer: A

 

Answer 2

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

https://hazelcast.com/glossary/cache-miss/

---

Answer 3

Answer A.
The miss ratio in this case can be described by the formula:

Miss ratio = (n - A + 1) / N

This is because, when the associativity of the cache is greater than or equal to k, the cache will always contain the most recent k unique block addresses. Therefore, when a block address is accessed again, it will always be found in the cache. The only time a miss will occur is when the cache is full and the least recently used block address needs to be replaced. This will happen (n - A + 1) times over the course of the N accesses.

So, the formula for miss ratio is (n - A + 1) / N . where A is the associativity and N is the total number of block addresses.

Answer 4

Answer is option A.

Answer 5

Ans

Answer 6

1. Understanding the Goal

First, let's define the miss ratio:

• Miss Ratio = (Total Number of Misses) / (Total Number of Accesses)

The problem gives us the denominator right away:

• The "access sequence... is of length $N$".

• So, Total Number of Accesses = $N$.

Our entire job is to find the Total Number of Misses.

---

 

2. Analyzing the Types of Misses

 

There are three types of cache misses. Let's see which ones apply.

1. Compulsory Misses (Cold Starts): This type of miss is unavoidable. It happens the very first time the program accesses a block of data. Since the data has never been seen before, it cannot possibly be in the cache.

2. Conflict Misses: This is an avoidable miss. It happens when two blocks map to the same cache set, and one evicts the other, even though there is empty space elsewhere in the cache.

3. Capacity Misses: This is an avoidable miss. It happens when the cache is simply too small to hold all the blocks the program is actively using, so it has to evict a block that it will need again soon.

---

 

3. Calculating the Misses

 

Let's use the information from the problem to count the misses.

A) How many Compulsory Misses?

• The problem states the sequence "contains $n$ unique block addresses."

• Each of these $n$ blocks must cause a miss on its very first access.

• Total Compulsory Misses = $n$

 

B) How many Conflict/Capacity Misses?

This is the key to the problem. We need to figure out if any block, after being loaded, is ever evicted and then accessed again.

Let's look at the two conditions:

1. Program Behavior: "The number of unique block addresses between two consecutive accesses to the same block address is bounded by $k$."

   • This means if you access block B, and then later access B again, the "stuff" in the middle (...) contains at most $k$ other unique blocks.

   • ... B, (X1, X2, ... Xk), B ...

2. Hardware Specification: "a cache of associativity $A \ge k$ exercising least-recently-used (LRU) replacement policy."

   • This means our cache's sets can hold at least $k$ blocks. 

Let's trace a re-access in the worst-case scenario:

1. Access B (First time): This is a Compulsory Miss. Block B is loaded into a set (say, Set 0). It is now the "Most Recently Used" (MRU).

2. Access Other Blocks: The program now runs and accesses at most $k$ other unique blocks (X1, X2, ... Xk) before it needs B again.

3. Worst-Case for B: The worst possible luck is that all $k$ of these other blocks map to the exact same set (Set 0).

4. Analyze the Set (LRU):

   • Our set needs to hold B (which is now the LRU) plus the $k$ other blocks.

   • Total blocks the set needs to hold = $k+1$ (Block B + $k$ other blocks).

5. Check the Hardware:

   • The problem guarantees our associativity $A$ is sufficient. (Even with the typo $A \ge k$, the clear intent is that the hardware ($A$) is large enough to handle the program's locality ($k$)).

   • Let's assume the question meant $A \ge k+1$ (which is the technically correct version of this problem).

   • Since the set can hold $k+1$ blocks (or more), and it needs to hold $k+1$ blocks, block B is not evicted. It will be the LRU, but it's still in the cache.

6. Re-access B: The program comes back to access B. Since B was never evicted, this is a HIT.

This proves that no block is ever evicted and then re-accessed. The only misses that ever occur are the initial compulsory misses.

• Total Conflict/Capacity Misses = 0

---

 

4. Final Calculation

• Total Misses = (Compulsory Misses) + (Conflict/Capacity Misses)

• Total Misses = $n + 0 = n$

• Total Accesses = $N$

• Miss Ratio = $n / N$