CODEWITHSUNDEEP
ccache-locality
Carlos Romero
Carlos Romero

Reputation: 181

Understanding spatial and temporal locality

I was studying for my architecture final and came across the following lines of code: 

for(i = 0; i <= N ;i++){
   a[i] = b[i] + c[i]; 
}

The question is: "How does this code snippet demonstrate examples of temporal and spatial locality? Be sure to consider memory references for both data and instructions."

In terms of spatial locality I believe the code demonstrates it by accessing contiguous memory locations (a[0] then a[i] etc). However, my confusion comes with temporal locality. I'm not sure how this snippet of code references the same location within a small period of time? Any sort of help would be greatly appreciated.

Upvotes: 3

Views: 1542

Answers (2)

MFisherKDX
MFisherKDX

Reputation: 2866

I'm not sure how this snippet of code references the same location within a small period of time.

In addition to txtechhelp's answer, the instructions that make up that for loop are also stored in memory. These instructions are "fetched" from memory/cache each time they are executed. Since each of these instructions is executed N+1 times in a very short time frame, this demonstrates temporal locality.

Upvotes: 0

txtechhelp
txtechhelp

Reputation: 6777

I'm not sure how this snippet of code references the same location within a small period of time?

As has been commented, the variable i is accessed quite frequently, take the following line of code in your example:

a[i] = b[i] + c[i];

In this example, a, b and c all presumably refer to array types pointing to different memory locations (even if contiguous, still different); however, the variable i is read each time it is referenced to then determine the location of the array to reference.

Think of it this way:

get i from memory and store value in register x.
get value of b + [value in register x] from memory, store in register b.
get i from memory and store value in register y
get value of c + [value in register y] from memory, store in register c.
get i from memory and store value in register z
add value of [register b] to value in [register c] and store in memory location a + [value in register z]

An optimizing compiler would likely see this temporal locality and instead do something similar to the following:

get i from memory and store value in register i.
get value of b + [value in register i] from memory, store in register b.
get value of c + [value in register i] from memory, store in register c.
add value of [register b] to value in [register c] and store in memory location a + [value in register i]

It is in this way that i has a temporal proximity between adjacent references.

I hope that can help.

Upvotes: 3

Related Questions