6
$\begingroup$

Following question was asked in one of entrance exams for a graduation programme. Please help me try to solve it :

A computer system has an L1 cache, an L2 cache, and a main memory unity 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 main memory unit respectively.

cache-image

  1. 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

  1. 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?

(A) 222 nanoseconds (B) 888 nanoseconds (C) 902 nanoseconds (D) 968 nanoseconds

First thing that came to my mind was, how to calculate the transfer time using the given access time. During a miss, a block of data is moved from main memory to cache. Then CPU will access it. So, wouldn't be access time > transfer time ?

Then I thought, lets assume access time = transfer time & do the calculation.

Now first question. The question already states there is a miss in L1, so I will not consider L1 access time. Since there is a miss in L1 & hit in L2, a entire block from L2 has to be moved to L1. L2 block size is 16 words, but data bus size is 4 words.

So we have to move 4 words * 4 times.

To transfer 4 word it takes 20 ns. To transfer 4 words, its 80ns. Isn't it the time transferred from L2 to L1 ? The question does not say anything about accessing L1 after moving the data. But 80ns is not in the option !

Similar case with second question also.

Time to move main memory to L2 = 4 words * 4 times = 4 * 200 = 800ns

Time to move L2 to L1 = 80ns [earlier calculation]

So total time taken is 880ns. Which is again not in the option.

Either I am doing a very big mistake or options are wrong or question isn't framed correctly. If I am doing anything wrong, please give me some hint & I will try to work on this exercise again.

Improve this question
$\endgroup$
3
  • $\begingroup$ Integer arithmetic is on graduate entry exams? Oh dear. $\endgroup$
    – Raphael
    Commented Apr 14, 2013 at 11:46
  • $\begingroup$ ^yes. And still most of us like me don't get it right it :P $\endgroup$
    – avi
    Commented Apr 14, 2013 at 12:45
  • 3
    $\begingroup$ Even if you don't get it right, I maintain it will say nothing about your ability to pursue a PhD in computer science. $\endgroup$
    – Raphael
    Commented Apr 14, 2013 at 13:32

3 Answers 3

Reset to default
3
$\begingroup$

In order to find that any cache does not contain the value at the requested address you have to access it.

That means you have to add up the access times of all contributing levels.

Some of the options seem to suggest one might think that whole blocks from, say, L2 cache are transferred upwards to L1 cache; as far as I know, that is not what happens: transfer volume is determined by the block size of the requesting level.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I did not get you. So only 4 words (L1 cache size) will be transferred from L2 to L1 ? $\endgroup$
    – avi
    Commented Apr 14, 2013 at 12:44
  • 1
    $\begingroup$ @avi As far as I know, yes. Why would you load more? Right now, we even only need one out of these four. Even if data locality is maintained, it's arguably better to spread the latency out over more statements, as it yields a more predictable performance profile and isolated accesses are not punished that much. $\endgroup$
    – Raphael
    Commented Apr 14, 2013 at 13:34
  • $\begingroup$ I think you can remove words 'as far I know', I just thought for a moment & checked & you are absolutely right. I have prepared my notes from various credible sources & I have mentioned it. Somehow I forgot it while solving this. The size is always decided by source. So, for question 1, it will be (20+2) ns, even though we are moving only 4 words. $\endgroup$
    – avi
    Commented Apr 14, 2013 at 14:45
  • 1
    $\begingroup$ @avi I think my answer covers this already. :) (Glad I could help. I use cautious phrasing because one could very well build a processor for either option; insofar, the question is ill-posed, asking for best-practice as opposed to scientific fact.) $\endgroup$
    – Raphael
    Commented Apr 14, 2013 at 15:57
  • 1
    $\begingroup$ @avi See my first comment. For more detail, I suggest you ask a computer engineer. As I said, there is no conceptual reason against building a CPU that acts as you say. $\endgroup$
    – Raphael
    Commented Apr 14, 2013 at 16:24
6
$\begingroup$

I guess you got the access time wrong. Access time means time to locate a data on a memory. So, whoever accesses the memory (be it CPU or some other device) it will be the same.

Coming to first question here. A block is transferred from L2 to L1. And L1 block size being 4 words and data bandwidth being 4 bytes, it requires 1 L2 access (for read) and 1 L1 access (for store). So, time = 20+2 = 22 ns.

For the second question, L2 block size being 16 words and bandwidth between memory and L2 being 4 words, we require 4 memory access (for read) and 4 L2 access (for store). Now, we need to send the requested block to L1 which would require 1 more L2 access (for read) and 1 L1 access (for store). So, total time

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

= 880 + 22

= 902 ns

Improve this answer
$\endgroup$
2
  • $\begingroup$ I don't think this is correct. See the comments under the accepted answer. Nowhere does it say that the "data bandwidth is 4 words". $\endgroup$
    – Wandering Logic
    Commented Jun 19, 2014 at 19:49
  • 2
    $\begingroup$ I'm sorry- I got that wrong. I have corrected the answer as 22ns and 902 ns. But the bandwidth is 4 words only as shown in the diagram on question. $\endgroup$
    – Arjun Suresh
    Commented Oct 29, 2014 at 18:16
0
$\begingroup$

answer for 1 question :

to transfer the block from l2 to l1 , generally it takes 20+2 ns to transfer 4 words : here why only words means we have a databus with capacity 4 words, so due to miss l1 and hit l2 , we have to transfer a block of l2 which contains 16 words.. so here we have to access the l2 an l1 4 times. so 4(20+2)..

similarly answer for the 2 question :

main memory to l2 and l2 to l1 so 4(200+20) + 4(20+2)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.