Virtual memory system, page table and TLB

Question

I was banging my head to solve this problem, couldn't even proceed one step, the question is like:

Consider the following C program:

int X[N];
int i;
int step = M; // M is some predefined constant
for (i = 0; i < N; i += step) X[i] = X[i] + 1;

If this program is run on a machine with a 4-KB page size and 64-entry TLB, what values of M and N will cause a TLB miss for every execution of the inner loop?

Can anyone please give me some hints how do I solve it?

Answer 1

It is simple. First you must understand what does TLB does exactly ? The hint is that it is a cache which will aid to translate virtual address to physical address. So you know that the page size is 4 Kbytes. So if there is an array lets say of infinite length. You are accessing it from 0 to infinity in a for loop. The first access of the array X[0] will cause a TLB miss and load the first TLB. then for next 4095 accesses, it will not be missed because it is present in the TLB(remember this is because the Page size is 4096 = 4KB). So then the next address is X[4096] which will cause a TLB miss. Thus you see that for every 4096 address increments you will have a TLB miss. So we are sure that M = 4096/sizeof(int).

Now you also know that you have 64-entry TLB cache. So after 64 entries of TLB are loaded, you will have a full TLB. To load the 65th entry, you will have to remove the first entry. (note that there can be different replacement mechanisms. we are assuming it here to be some simple mechanism). So after the 65th entry is loaded the first entry when accessing X[0] has been removed. So if you try to access now X[0] there will be a TLB miss replacing the entry required for X[4096] and so on. So you need the size of 64 * 4096 = 256 KBytes, to fully utilize the TLB cache. However you want to have a TLB cache miss for every step. So for 64 entry TLB cache you need array size which will be equivalent to 65 entries. Thus N = 65 * 4096 / sizeof(int).

Hope this gives some hints !