GATE CSE 2010 | Question: 48

Question

A computer system has an $L1$ cache, an $L2$ cache, and a main memory unit connected as shown below. The block size in $L1$ cache is $4$ words. The block size in $L2$ cache is $16$ words. The memory access times are $2$ nanoseconds, $20$ nanoseconds and $200$ nanoseconds for $L1$ cache, $L2$ cache and the main memory unit respectively.

 

When there is a miss in $L1$ cache and a hit in $L2$ cache, a block is transferred from $L2$ cache to $L1$ cache. What is the time taken for this transfer?

• A. $2$ nanoseconds
• B. $20$ nanoseconds
• C. $22$ nanoseconds
• D. $88$ nanoseconds

Comments

this was just a basic question and asking for memory access time when we have to jsut see when there is miss in L1 and L2 hit

so if miss in L1  need 4 words and Hit in L2 16 words total 20 words we need to access to get the data and also 2 nano seconds memory access time

therefore it is 22ns and i dont understand why there coaching gave 88ns how it is even possible the data is already in block how do we even need this much time to access

---

Easy explanation

The CPU look for required words in L1 cache 

Accessing L1 Cache takes $2\text{ ns}$.

The requested data is not in L1 (L1 Miss).

Since it missed in L1, the system sends the request down to L2 Cache.

Accessing L2 Cache takes $20\text{ ns}$.

The data is found (L2 Hit).

L1 Cache stores data in units called blocks. Its block size is $4\text{ words}$.

Therefore, L1 needs to fetch a full block of $4\text{ words}$ from L2 Cache.

The Data Bus connecting L1 and L2 Cache is $4\text{ words}$ wide.

Since the bus width matches the L1 block size ($4\text{ words}$), all 4 words are transferred across the bus in a single transfer cycle.

Reading this block from L2 Cache takes its standard access time of $20\text{ ns}$.

$$Total \ time = L1 \ access \  time + L2 \ access \  time $$

$$Total \ time = 2 ns + 20 ns = 22 ns $$

 

---

The confusion stems from where you draw the finish line.

• If you believe the transfer is only complete when the data is fully settled inside L1's memory cells, you get 22 ns.

• If you define transfer as the time it takes for L2 to deliver the data to the bus connecting them, you get 20 ns.

Answer 1

Ideally the answer should be $20$ ns as it is the time to transfer a block from $L2$ to $L1$ and this time only is asked in question. But there is confusion regarding access time of $L2$ as this means the time to read data from $L2$ till CPU but here we need the time till $L1$ only. So, I assume the following is what is meant by the question.

A block is transferred from $L2$ to $L1$. And $L1$ block size being $4$ words (since $L1$ is requesting we need to consider $L1$ block size and not $L2$ block size) and data width being $4$ bytes, it requires one $L2$ access (for read) and one $L1$ access (for store). So, time $= 20+2 = 22$ ns.

Correct Answer: $C$

Comments

Yes then answer could be 88. Made Easy PYQ book has given ans as 88. As data bus is of 4 word nd we're sending 4 blocks, still answer would have been 80.

This question deserves to be left aside, is of absolutely no use at all..

Did BARC 2017 provide key to this?

---

In case of miss at lower level cache, it is not possible to transfer specific 4 words from higher level cache block to lower level cache block. So we must transfer the whole 16 word block and it requires 4 access at both the ends. Leaving us with answer 88 ns.

---

@Arjun 

sir i read your explanation and other explanation …..both explanation answer oriented  not conceptual oriented

so plz explain in detail way 

Answer 2

The size to transfer a block is always decided by source(Do not confuse yourself by looking "a block is transferred from L2 cache to L1 cache). In this case only 4 words will be transferred from L2 to L1 not whole block of L2. Now the only confusion is "This whole process of transferring block is concurrent process or serial?".

If nothing is mentioned in the question then take serial transfer of block(in computer science we always strive for Worst case) so 20ns to access or read L2 cache and 2ns to place or write it into L1 cache. so answer would be 22ns.

Comments

They clearly mentioned that L1 is a miss, so we don’t need to consider the 2ns time.

---

@Pranavpurkar no I think he meant not concurrent transfer otherwise 20ns would be the answer by serially it means 20ns to access or read L2 cache first and then 2ns to place or write it into L1 cache.

---

see cache memory tranfer whole block that we know right so if there is miss in l1 and hit in l2 then we have to move the block of l2 in l1 so the correct ans is 88 but why the correct ans according to them is 22 ???

 

Answer 3

This question statement and diagram depicts that it is based on parallel hierarchy means direct access to L1,L2 or main memory is possible in it.

Since L1 miss

20 ns is required to access L2 and reading a block of size 16B.Since L1 is requesting which has block size of 4 B .only 4B transfer to L1 from L2 is required which takes an access of L1 to store block in it.

Thus L2 access (reading a block) + L1 (storing a block since it is parallel hierarchy by default it will not be copied to L1)

thus 20ns + 2ns = 22ns

Ans C

Comments

 (storing a block since it is parallel hierarchy by default it will not be copied to L1)
 

@Ravi_1511 please explain bit more about this.

 

---

How do we know the given memory organisation is parallel or hierarchical?

Answer 4

Any per my knowledge. Any read/write operation occurs in this sequence

1. Read the data from the source.

2. Write the data to the destination.

Now 2 ns is the time to access the L1 cache. And 20 ns to access the L2 cache. The data bus is 4 words wide. Also any block transfers as a whole.

So consider the following sequence.

1. Read from L2 -->20 ns.

2. Write to L1 -->2 ns. (4 words written).

3. Read from L2 -->20 ns.

4. Write to L1 -->2 ns. (4 words wasted).

5. Read from L2 -->20 ns.

6. Write to L1 -->2 ns. (4 words wasted).

7. Read from L2 -->20 ns.

8. Write to L1 -->2 ns. (4 words wasted).

So in total 20+2+20+2+20+2+20+2=88 ns.

Therefore it must take 88 ns to transfer a block from L2 to L1 cache.

Answer 5

….…………………………………………………………………...

Answer 6

The block size of L2 is 16 words and of L1 is 4 words.The data bus between L1 and L2 can carry 4 words. 

It means that L2 needs to be accessed 4 times.

4*(Read access L2 + store it in L1) = 4*(20+2) = 4 * (22)  =  88 ns.

Answer is (D).