c - 了解空间和时间局部性

Question

我在为我的架构期末学习时遇到了以下代码行:

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

问题是:“这个代码片段如何展示时间和空间局部性的例子？一定要考虑数据和指令的内存引用。”

就空间局部性而言，我相信代码通过访问连续的内存位置(a[0] 然后 a[i] 等)来演示它。但是，我的困惑来自时间局部性。我不确定这段代码如何在短时间内引用同一位置？任何形式的帮助将不胜感激。

Answer 1

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

如前所述，变量 i 被频繁访问，在您的示例中采用以下代码行:

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

在这个例子中，a、b 和 c 都可能指的是指向不同内存位置的数组类型(即使是连续的，仍然不同的);但是，每次引用变量 i 时都会读取，然后确定要引用的数组的位置。

这样想:

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]

优化编译器可能会看到这个时间局部性，而是执行类似于以下的操作:

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]

正是通过这种方式，i 在相邻引用之间具有时间上的接近度。

希望对您有所帮助。