3

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.

Carlos Romero
  • 181
  • 1
  • 13
  • The code doesn't *reference the same location within a small period of time*, because it only "references" each location once, unless `a == b || a == c || b == c`. – Weather Vane May 03 '18 at 22:29
  • 3
    The variable `i` is accessed a lot in a small amount of time. – JGroven May 03 '18 at 22:32
  • @JGroven the question is about *`a[0]` then `a[i]` etc.* although your point does consider *Be sure to consider memory references for both data and instructions* – Weather Vane May 03 '18 at 22:33
  • 2
    @WeatherVane that's just OP's explanation of spatial locality, not the question. The question is about spatial and temporal locality. – JGroven May 03 '18 at 22:35
  • 1
    I edited previous comment as you typed. – Weather Vane May 03 '18 at 22:36
  • @WeatherVane thanks for the explanation. So basically you are saying this code doesn't demonstrate temporal locality at all? If so, a trick question! – Carlos Romero May 03 '18 at 22:44
  • Well, @JGroven pointed out the continuous use of the control variable `i` although that might not be implemented in a memory location, but in a processor register. – Weather Vane May 03 '18 at 22:46
  • I think *instructions* is the key word here ... you have several instructions inside that for loop ... – MFisherKDX May 03 '18 at 22:47

2 Answers2

3

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.

txtechhelp
  • 6,625
  • 1
  • 30
  • 39
  • This is sub-question but if there is no compiler optimization here, how would you optimize OP code to improve temporal locality? –  May 03 '18 at 23:00
  • 1
    @GRC it depends on the specifics of the code in this case (especially since this is just an academic question), but the most likely optimization I would do is something similar to the following: `while (N-- >= 0) { *a++ = *b++ + *c++; }` .. but that makes certain assumptions of the code itself. – txtechhelp May 03 '18 at 23:14
0

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.

MFisherKDX
  • 2,840
  • 3
  • 14
  • 25