C语言 了解空间和时间位置



我正在为我的架构期末考试做准备,遇到了以下代码行:

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

问题是:"此代码片段如何演示时间和空间局部性的示例?一定要考虑 数据和指令的内存参考。

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

我不确定这段代码如何在短时间内引用同一位置?

如前所述,变量i的访问非常频繁,请在示例中使用以下代码行:

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

在此示例中,abc都可能引用指向不同内存位置的数组类型(即使连续,仍然不同(;但是,每次引用变量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在相邻引用之间具有时间上的接近性。

我希望这能有所帮助。

我不确定这段代码如何引用同一位置 在短时间内。

除了 txtechhelp 的答案之外,构成 for 循环的指令也存储在内存中。 每次执行这些指令时,都会从内存/缓存中"获取"。由于这些指令中的每一个都在很短的时间内执行 N+1 次,这证明了时间局部性。

最新更新