Finding the appropriate stride for TLB misses in an array in a code snippet

Question

Assume the system has a 32-entry TLB with a 8KB page size. What should MAX and stride be set to in order achieve a TLB miss upon pretty much every access to the array "data" ?

int value=0;
int data[MAX];
for (int j;j <1000; j++)
{
 for (int i =0, i<MAX; i+=stride)
 {
   value=value+data[i];
 }
}

This is a practice final exam which has answer but I don't get it. Final answers are : stride=2k MAX=33*stride

Any complete answer which will help me figure out how to find number of TLB misses in such type of questions is really appreciated.

There must be more information about the TLB that you haven't shared with us. Page size, number of entries, associativity, etc... — Greg Prisament

user2357112 supports Monica user2357112 supports Monica · Accepted Answer · 2013-12-11T08:43:42

stride=2k

This part of the solution is because ints are 4 bytes on the system in question. Since pages are 8KB, a stride of 2048 ints will place each access on a different page.

MAX=33*stride

Since the stride length is the page size, this sets an array length of 33 pages. Assuming the 32-entry TLB is full-LRU, that means that between accesses to a given page, all 32 other pages in the array are accessed, enough to evict the page from the TLB and cause a page fault when its turn comes again.

Finding the appropriate stride for TLB misses in an array in a code snippet

1 Answers