# GATE2010-49

10.6k views

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} \text{nanoseconds}$, $20 \hspace{0.1cm} \text{nanoseconds}$ and $200 \hspace{0.1cm} \text{nanoseconds}$ for $L1$ cache, $L2$ cache and the main memory unit respectively. When there is a miss in both $L1$ cache and $L2$ cache, first a block is transferred from main memory to $L2$ cache, and then a block is transferred from $L2$ cache to $L1$ cache. What is the total time taken for these transfers?

1. $222 \hspace{0.1cm} \text{nanoseconds}$
2. $888 \hspace{0.1cm} \text{nanoseconds}$
3. $902 \hspace{0.1cm} \text{nanoseconds}$
4. $968 \hspace{0.1cm} \text{nanoseconds}$

edited
0
Does anyone knows what was the answer in official answer key? there seems to be a lot of different arguments.
1
In 2010 they didnt release answer keys
2
968 is the correct answer because as data line between L1 ,L2 , main memory=4 words

L2 block size  size=16 words . so we need to bring 16 words from main memory to L2 and then 16 words to L1 . for this

4 acces to main memory for loading 16 words of data into L2 =4*200=800

4 acces to L2 for storing 16 words of data into L2=4*20=80

4 acces to L2  for loading 16 words of data to L1=4*20=80

total=800+80+80+8=968
0

memory access time is what?

time to access one WORD or time to access one BLOCK ?

0

4 acces to L2  for loading 16 words of data to L1=4*20=80

Only 1 access is required

3

nice explanation given by kiran sir!

The transfer time should be $4*200 + 20 = 820$ ns. But this is not in option. So, I assume the following is what is meant by the question.

$L2$ block size being $16$ words and data width between memory and $L2$ being $4$ words, we require $4$ memory accesses(for read) and $4$ $L2$ accesses (for store). Now, we need to send the requested block to $L1$ which would require one more $L2$ access (for read) and one $L1$ access (for store). So, total time

$= 4 * (200 + 20) + (20 + 2)$

$= 880 + 22$

$= 902 \ ns$

Correct Answer: $C$

edited
2
VeryCorrect
0
@Arjun Sir shall we send (16 or 4 words) to L1 from L2.

I think we sud send 4 word as block size for L1=4 word and
processor here requested to L1 Cache.

Plz clarify sir .
10
What does time to store specify?
I reached the answer as follows

1) access L1 -miss -. 2ns
2)check in L2 -miss - 20ns
3)access main memory- a block of 16 words in main memory(assuming)- 200 *4 = 800 ns
4)now transfer the word received in L2 to l1 --  will take 4 cycles- 4*20 =80

now the tranfer is complete, time taken= 2+20+800+80 =902ns
0
Now it makes more sense that only one block should be transferred to L1 from L2 cache..
18
@ arjun sir, how to guess that when question means only access time for transfer or when it means access+store time as transfer time. No matter how many questions we solve, these things are alwys so ambiguous. :(. Disheartening
0
@Arjun sir, sir why do we require 4 memory access from main memory to L2? L1 cache size is 4 word so finally, the required block is with 4 words and that 4 words can be distinguished by word offset in main memory,  in the worst case that 4 words may be present in 4 different blocks of main memory. so L2 will have to access main memory 4 times and then it will be stored in L1.

so, is that the correct reason of 4 memory reference by l2?
1

The transfer time should be 4*200 + 20 = 820 ns.

Looks good to me.

0
Using 20ns as the store in L2 is almost senseless. Access time means how much time it takes to move from one location to another (request + response). Store and access time has no relation. But there's no other way to solve it, is there? :(
0

https://gateoverflow.in/user/sushmita  when he asks for the average access time we generally don't consider store but when we are asked the total time taken for the transfer of the missing data in L1 to be in its position we have to consider store time also

0
Even data width between L1 and L2 is also 4 words, why are we considering only one memory access for all 4 words. If Yes, even we should consider for L2 and L3, then access time from L3 to L1 would be 200 + 20 = 220ns.

Please correct me if i am wrong.
0
4
Before 2011 there were no official answer keys -- it was British raj for central level exams then ;)
1

This is a very confusing question .... this one also ... https://gateoverflow.in/2352/gate2010-48 ....

0
@arjun sir great explanation ,,,sir you remove lots of doubts regarding these types of questions
0
nice arjun sir dil khush ho gaya
0

As clearly stated in the Question - "a block is transferred from L2 cache to L1 cache". L2 block size is 16 words. So 4 access are required from L2 to fetch a block in L1.  And after that 4 store operations are required in L1 to store the block recently fetched.

4 * (200 +20) + 4( 20 + 2) = 968 ans.
1

@Sinchit

first a block is transferred from main memory to L2 cache, $\implies 880$ ns ($16$ Words are transferred)

and then a block is transferred from L2 cache to L1 cache. $\implies 22$ ns  ($4$ words are transferred)

NOTE :-

here we are taking $16$ Words because size of $L_2$ block is $16$ Words

So similarly when transferring Block from $L_2$ to $L_1$ we will transfer $4$ words since size of receiver's block i.e. $L_1$ is $4$ Words.

scene 1

• L2 block size is 16 words
• Data width between l2 and Main Memory is 4 words
$\Rightarrow$ We need 4 access to Read from Memory and 4 access to store to L2
To Read from MM require 200ns and To Store in L2 require 20 ns
Total Time spent : 220 ns

scene 2

• stored information from L2 is read and stored on L1
•  Read from L2 takes 20ns and store on L1 takes 2 ns
$\Rightarrow$  Total time spent in scene - 2 is  22ns

scene 1 and scene 2 can occur simultaneously which is depicted in the following figure So , Total time spent
(220 *4 ) + 22 = 902 ns

edited
1
you are right almost but i have one dout ... suppose L1 cache having only 2 blocks so what is need to transfer all 4 blocks from L2 to L1 ... ??
0
Why u want to transfer 4 blocks from L2 to L1.
0
As in question it is asked that's y we need to transfer from l2 to l1
0
@Gabbar ,

When L1 is 2 blocks then will we transfer 4B still  from l2 ? or is there any ways we can transfer 2Blocks alone ?
0
@pc sir great explanation ,,,sir you remove lots of doubts regarding these types of questions

Miss in L1 cache and L2 cache results in the:

(200+20) for one word to get from main memory to l2 cache
(20+2) for one word to get from L2 cache to L1 cache

So total Time Needed is:   (200+20)*4  + (20+2)*4   = 968

0
Transfer is done word by word or block by block ? Transfer time which is given for a block or for a word ?
0
this answer i more correct as i also get the same answer and answer given on geeks for geeks is also 968  0

@skeltro Any Reference for this formula?

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 first 16 words will be transferred from main memory to L2 cache( IF nothing is mentioned, the last level cache L2 & main memory page size considered to be equal.) then only 4 words will be transferred from L2 to L1 not the whole block of L2. Now the only confusion is "This whole process of transferring block is a 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

1)   200ns to access main memory and 20ns to store in the L2 cache.

2)   Point (1) will happen for 4 times because of data bus = 4 words, so 16 words will be transferred in 4 times.

3)   and after that 20ns to access or read L2 cache and 2ns to place or write it into L1 cache.

4*(200+20) + 20 + 2 = 902.

edited
Access time from main memory is 200. So total time to access is is 200+20 nanoseconds Similarly for L1 cache to access from L2 cache is 20+2 nanoseconds So total time is 4*(220 + 22) = 968 nanoseconds.

4
only the requested block will be sent from L2 to L1.

Time for transferring from main memory to L2 is 200ns . time for transferring from L2 to L1 is 20ns. Time needed to write into L1 is 2ns. The total time taken is 200 + 20 + 2 = 222ns.
0
In single time, data bus can carry only 4 words so for transfer 16 words (1 block) u have to 4 times access memory and L2 cache. Then 4*(200+20) = 880ns.

And in between L2 and L1 the block size is 4 word that would take (20 + 2)ns.

So totel time is 902ns.

## Related questions

1
15.3k views
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$ ... this transfer? $2 \hspace{0.1cm} nanoseconds$ $20 \hspace{0.1cm} nanoseconds$ $22 \hspace{0.1cm}nanoseconds$ $88 \hspace{0.1cm} nanoseconds$
A $5-$stage pipelined processor has Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Perform Operation (PO) and Write Operand (WO) stages. The IF, ID, OF and WO stages take $1$ clock cycle each for any instruction. The PO stage takes $1$ clock cycle for ADD and SUB instructions, ... $13$ $15$ $17$ $19$
Consider a complete undirected graph with vertex set $\{0, 1, 2, 3, 4\}$. Entry $W_{ij}$ in the matrix $W$ below is the weight of the edge $\{i, j\}$ ... What is the minimum possible weight of a path $P$ from vertex $1$ to vertex $2$ in this graph such that $P$ contains at most $3$ edges? $7$ $8$ $9$ $10$
A hash table of length $10$ uses open addressing with hash function $h(k) = k \: mod \: 10$, and linear probing. After inserting $6$ ... insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above? $10$ $20$ $30$ $40$