GATE2010-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 \hspace{0.1cm} nanoseconds$, $20 \hspace{0.1cm} nanoseconds$ and $200 \hspace{0.1cm} 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 \hspace{0.1cm} nanoseconds$
• B. $20 \hspace{0.1cm} nanoseconds$
• C. $22 \hspace{0.1cm}nanoseconds$
• D. $88 \hspace{0.1cm} nanoseconds$

Comments

A block to access in L2 cache requires 20 nanoseconds, and 2 seconds to place in L1-cache.

The block size in L1 cache is 4 words and there are total 16 words, so total time is 4*(20+2) = 88.

---

your answer seems right out of a textbook,even though there are 16 words since we have the offset bits wont we get the correct 4words in the first try itself instead of four tries

---

I think read and write could be done parallelly. It should be done parallelly because there is no bus delay and there is no buffer in picture(It could be there in side memory but it is not mentioned explicitly). So I think answer should be 20 ns.

---

https://www.geeksforgeeks.org/gate-gate-cs-2010-question-48/

---

There is a confusion here.i am getting 2+ 4*20=82

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

@arjun sir wrt to ur 2-bit offset comment;;;suppose 01 is the offset means  we have to read 4-7 th word of L2 cache..but suppose our required info. is stored starting from 6th word then @time how we set offset???plz clarify Thanks

---

But question says that a block is transferred from l2 to l1, shouldn't that mean a block of size 16 is transferred to l1?

---

arjun sir word is the smallest unit of access or block?? its so confusing

---

A block to access in L2 cache requires 20 nanoseconds, and 2 seconds to place in L1-cache.

The block size in L1 cache is 4 words and there are total 16 words, so total time is 4*(20+2) = 88.

---

Arjun Sir ,

So here the memory access time of 20ns for L2 means that the memory block is copied from cache L2 into L1 cache and then the L1 cache making the desired word available on the data bus in these 20ns, right ?

---

When there is a miss in L1 cache and a hit in L2 cache, a block is transferred from L2 cache to L1 cache.

First CPU accesses L1 cache for a particular word so this would take 2 ns , since it is miss, a block is transferred from L2 cache, for doing this L2 cache is accessed which takes 20ns.

So totally 2+20 = 22ns.

Is this justification correct? 

---

@arjun sir

Ideally the answer should be 20 ns ?how

---

@arjun sir
everything is done through
PC MDR and MAR so ideally answer b 22ns.
ref : http://stackoverflow.com/questions/12630151/can-multiple-cores-simultaneously-read-the-same-ram-location

---

Anyone Please tag this question as BARC2017 .

Here in GO we dont have much questions in in this tag.

---

But i want to ask can we transfer partial memory block?Like l2 is of 16 words ,so can we transfer partial block also of 4 bytes?

---

@Rahul At any level of memory hierarchy, the requester decides the block size. So, you should not say 'partial block'. Rather it is different block sizes at different levels.

---

Sir in ques:- https://gateoverflow.in/35154/write-back-and-write-through

the sizes of L1 and Main memory are different but still we transferred data block in terms  of size of Main memory and not L1.

we transferred 16 word entire block from main memory to cache and not based on cache word.

and in https://gateoverflow.in/130202/co-memory-organization, entire 2 word block is transferred from l2 to l1 on miss and 4word block from memory to L2 in case of miss.So why in these two questions requester's size not coming into picture in case of miss?

I am not able to get the point that in these two above links we are transferring data based on word size of L2 cache and not L1.But in this question we are  transferring based on L1 size.

Please clear confusion here Sir

---

@arjun sir why it is not like this :

2ns(miss in L1)+20ns(access to L2)+2ns(to store a block in L1)

i.e 24ns

---

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?

We know miss occured so no need to take L₁ aceess time 1st.

---

Yeah, I also think that answer should be 20 ns only because the question has asked only transfer time in case of miss in L1.

---

@arjun sir block in L2 of size 16 word, so don't we have to transfer all four of them? 4 word at a time as given in diagram?

---

Nowhere in the question, it is mentioned that L1 is requesting. Rather question says, "a block is transferred from L2 cache to L1 cache". Which means 16W from L2 are transferred to L1 (Since L1 has the capacity of only 4 words, therefore a total of 4 such transfers would take place)

---

garbagecontent exactly, that makes more sense. 

---

@Arjun 

Sir, I have a doubt

When L1 makes a request for 4 words(on a miss) does L2  transfer 16 words(1 block) out of which 4 words are discarded and other 4 words are accepted by L1 . Is this how it happens ?

---

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

Answer 2

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 3

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

what happens for parallel transfer?

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

A block to access in L2 cache requires 20 nanoseconds, and 2 seconds to place in L1-cache. The block size in L1 cache is 4 words and there are total 16 words, so total time is 4*(20+2) = 88.

Comments

See when L1 access L2, it is L1 block size that is in use, not L2. Otherwise when L2 access main memory, a page frame is fetched? Also, when CPU access L1, only a word is taken from L1- not L1 block.

---

Sir,This comment is very useful.I need to ask one thing.

If we have different block size in L1 and L2.Say

L1= 1 word block size with Access Time=2ns and L2=4 word block size with access time as 4 ns.

Now when there is a miss in L1,we will goto L2 and search one entire block to look for one particular word as asked by L1  and then if it is found,it will be transferred to the L1 cache. So basically we accessed one complete L2 block with 4*2=8ns  but just to transfer it to L1,it is 1 word time as L1 block size is 1 word and i.e what is asked in the question