Learning Goal:

To examine the role of spatial locality in the performance of a function.

Introduction:

A program with good spatial locality has a memory access pattern that references locations near each other with respect to their addresses. Given the nature of caching programs, programs with higher degrees of spatial locality tend to have lower miss rates and therefore, higher performance.

Let's consider a set of functions that access the elements of an array. A function may visit each element of an array sequentially, known as a stride$-1$ reference pattern, or it may visit every kth element of a contiguous array, known as a stride$-$k reference pattern.

Part A $-$ Determining the stride of an array$-$based function