Clicky

Assume we have a simple system with a CPU (including an on-chip TLB), a single cache and main memory. The latencies for the TLB, cache and main memory are 1, 10 and 100 ns, respectively. These times include time for accessing any element 'on the way' to the given element.
o      What is the 'worst' case time for accessing program data? Explain your answer.
o      What is the 'best' case time for access program data? Explain your answer.
o      Which of these cases (best or worst) would you expect for the first data access in a given program? Why?

I just wanted to make sure my thinking process was correct. I think the 'worst' case is 111 ns, while the 'best' case is 1 ns.

asked 12/04/2011 09:26

Kaizoki's gravatar image

Kaizoki ♦♦


7 Answers:
It depends on how the system is set up. Does it check the cache and then do a TLB lookup on a cache miss or does it do the TLB lookup every time and then grab the data from whichever place it was?

The TLB doesn't contain any data, just addresses. So you'll never get 1 ns since the actual data will be in either the cache or main memory and so you'll have to wait for one of them.

I'm guessing your system is the second one so you look up in the TLB first.

The third part of the question is fairly easy. Did you get it?
link

answered

TommySzalapski's gravatar image

TommySzalapski

I guess so, so the worst case would be a cache miss and then getting the data from the main memory(latency=110ns). While best case is finding the data in the cache, making the latency 10ns.
link

answered 2011-12-05 at 06:20:38

Kaizoki's gravatar image

Kaizoki

Well, to get the data from main memory, you still need to look it up in the TLB so worst case should still be 111.
link

answered 2011-12-05 at 06:49:32

TommySzalapski's gravatar image

TommySzalapski

Ok thanks, that helps. But best case is still 10ns right? And the first data access would be the cache.
link

answered 2011-12-05 at 06:53:23

Kaizoki's gravatar image

Kaizoki

Yes. If the data is in the cache, then there is no need to check the TLB for the location in main memory.
link

answered 2011-12-05 at 08:20:56

TommySzalapski's gravatar image

TommySzalapski

The correct answer is :

o       In the worst case, the PPN is not cached at the TLB and the relevant part of the page table is not in the cache. If we have to go to main memory, that takes 100 ns. In addition, once the PA has been computed, if the data is not in the cache, we have to go to main memory again.
Time = 100ns + 100ns = 200ns

o       In the best case, the PPN is cached in the TLB and we can get it in 1 ns. Once we have computed the PA, if the data itself is in the cache, we can get it in 10ns.
Time = 1ns + 10ns = 11ns.

o      The worst case. This is because in order for information to be cached either in the TLB or the cache, it must have been seen already. The first data access starts with a completely cold TLB and cache.
link

answered 2011-12-05 at 08:21:45

Kaizoki's gravatar image

Kaizoki

Ah, that was a bit more advanced than I expected. I thought this was for a first semester OS class but it looks higher level than that. In the future, please include what the question is coming from so we can know the level of complexity that we should expect. Very sorry that my solution was not correct.
link

answered 2011-12-17 at 14:24:58

TommySzalapski's gravatar image

TommySzalapski

Your answer
[hide preview]

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Tags:

×2
×7
×10
×1
×2
×1

Asked: 12/04/2011 09:26

Seen: 230 times

Last updated: 12/05/2011 12:33