Consider the following C program define M define N int XN

Consider the following C program:
#define M ...
#define N ...
int X[N];
for (int i=0; i<N; i+=M)
X[i] = X[i] + 1;
This program runs on a machine with 64-bit integers, 8-KB pages and 16-entry
Translation Lookaside Buffer (TLB). Assuming a Least Recently Used (LRU) page
replacement algorithm, what values of M and N potentially cause eviction of all TLB
entries? Explain.

Solution

TLB can be defined as similar to a cache which helps in translating Virtual Address to a Physical Address.

Suppose the array in consideration is of infinite length, and so we are accessing it from 0 to infinity in a for loop.

The page size provided in question is 8KB.

The first access of the array X[0] will cause a TLB miss and load the first TLB and then for next 8191 accesses, it will not be missed because it is present in the TLB as the Page size is 8192 = 8KB.

So the next address is X[8192] which will cause a TLB miss.

Therefore, for every 8192 address increments we will have a TLB miss.

And hence, the value for M can be calculated as below:

M = 8192/sizeof(int)= 8192/4= 2048.

---------------------------------------------------------------------------------------------------------------------------------------------------------------------

Now, we know that we have a 16-entry TLB, so after 16 entries of TLB are loaded, we will have a full TLB. To load the 17^th entry, we need to remove the first entry.

So after the 17^th 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[8192] and so on.

So we need the size of 16 * 8192 = 128KB, to fully utilize the TLB cache.

However to get a TLB miss for every step, for 16 entry TLB cache we need an array size which will be equivalent to 17 entries.

Thus,

N = 17 * 8192 / sizeof(int)= 34816