Opt System Support and Virtual Memory

Question

Consider now a machine with 16-bit virtual addresses and 16-bit physical addresses. The memory is byte-addressable. This machine has a linear (i.e., single-level) page table with a page size of 4 Kbytes.

Consider the following C code to be executed on this machine:

int A[1024*512]; // A 2 Mbytes array

int sum = 0;

for (int i = 0; i < 512; i++) {

sum = sum + A[i*1024];

}

Here, array A starts at virtual address 0, and each integer element of array A occupies 4 bytes. The size of array A is 2 Mbytes (because (1024 X 512) elements X 4 bytes per element = 1024 X 2048bytes = 2 Mbytes).

1. How many bits in a virtual memory address should be used for the page offset? Give your answer in a base 10 number (and only write down the number)
2. Assume the machine does not have a translation lookaside buffer (TLB). To execute the code, how many accesses to the page table are required? Give your answer in a base 10 number (and only write down the number)
3. We now want to add a TLB to speed up virtual memory address translation. What is the minimum number of TLB entries required to ensure no TLB misses for the above code when accessing array A?Give your answer in a base 10 number (and only write down the number).

Answer 1

The whole problem comes down to one number, which is the page size, so let us start there. A page is 4 Kbytes and the memory is byte addressable, so one page holds

4 × 1024 = 4096 bytes = 2¹² bytes

The page offset is the part of the address that picks out a single byte inside a page, so it needs exactly enough bits to count 4096 different positions. That is 12 bits, and the remaining high bits of the address are the page number.

For the second part, look at what the loop is actually touching. Each int is 4 bytes, so the element A[i*1024] sits at byte address

i × 1024 × 4 = i × 4096

If you notice, 4096 is exactly one page, so the stride between consecutive accesses is one full page. The first access is at byte 0 which is page 0, the next at byte 4096 which is page 1, then page 2, and so on. The loop runs i from 0 to 511, so it touches 512 different pages with one access each. With no TLB every one of those accesses has to consult the page table first, so the answer is 512 page table accesses.

The third part follows from that same observation. The code needs 512 different translations, so for all of them to be held at once the TLB would need 512 entries. I do want to be straight with you about one subtlety, because it is the kind of thing that trips people up on this problem. On a single cold run through this loop each page is touched exactly once, so the first touch of every page is a compulsory miss no matter how large you make the TLB. What the question is really getting at is how many translations have to fit simultaneously so that nothing gets evicted, and that number is 512.

One last thing worth pointing out, and it is not your mistake. The problem says 16 bit virtual addresses, which gives only 2¹⁶ = 65536 bytes, or 64 Kbytes of address space, and then puts a 2 Mbyte array inside it. Addressing 2 Mbytes actually takes 21 bits. So the numbers in the problem do not fit together. It does not change any of the three answers, since all three depend only on the page size and the stride, but it is a real inconsistency and worth raising with your instructor if it comes up.