We help IT Professionals succeed at work.

Virtual memory latencies

Kaizoki
Kaizoki asked
on
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.
Comment
Watch Question

Awarded 2010
Top Expert 2013

Commented:
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?

Author

Commented:
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.
Awarded 2010
Top Expert 2013

Commented:
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.

Author

Commented:
Ok thanks, that helps. But best case is still 10ns right? And the first data access would be the cache.
Awarded 2010
Top Expert 2013
Commented:
Yes. If the data is in the cache, then there is no need to check the TLB for the location in main memory.

Author

Commented:
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.
Awarded 2010
Top Expert 2013

Commented:
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.