gpt4 book ai didi

在嵌套循环中访问数组时缓存未命中

转载 作者:行者123 更新时间:2023-12-02 02:24:21 24 4
gpt4 key购买 nike

所以我的教授向我提出了这个问题,我无法弄清楚为什么 vector2vector1 更快并且缓存未命中更少。

假设下面的代码是有效的可编译 C 代码。

vector 2:

void incrementVector2(INT4* v, int n) {
for (int k = 0; k < 100; ++k) {
for (int i = 0; i < n; ++i) {
v[i] = v[i] + 1;
}
}
}

vector 1:

void incrementVector1(INT4* v, int n) {
for (int i = 0; i < n; ++i) {
for (int k = 0; k < 100; ++k) {
v[i] = v[i] + 1;
}
}
}

注意: INT4 表示整数大小为 4 字节。

就 CPU 规范而言:缓存大小 = 12288KB,行大小 = 64B,并且仅考虑与主内存交互的单个缓存。

问题

为什么 vector2 的运行时间比 vector1 更快?为什么 vector1 的缓存未命中次数比 vector2 多?

我和几个同学为此研究了一段时间,但无法弄清楚。我们认为这可能是由于 vector2 具有更好的空间位置性,因为内部循环不断地访问数组,而在 vector1 中,只有一个元素一次访问?我们不确定这是否正确,也不确定如何将缓存行引入其中。

最佳答案

We thought it could be due to the fact that vector2 has better spatiallocatlity, since the array is been accessed by the inner loopconstantly, while in vector1, only one element is accessed at a time?

嗯,两个代码具有相同的访问模式,以步长 1 迭代数组 v。缓存空间局部性方面两个代码是相同的。然而,第二个代码:

void incrementVector1(INT4* v, int n) {
for (int i = 0; i < n; ++i) {
for (int k = 0; k < 100; ++k) {
v[i] = v[i] + 1;
}
}
}

具有更好的时间局部性,因为您访问同一元素 100 次,而在:

void incrementVector2(INT4* v, int n) {
for (int k = 0; k < 100; ++k) {
for (int i = 0; i < n; ++i) {
v[i] = v[i] + 1;
}
}
}

在每“n”次迭代中您只能访问一次。

所以要么你犯了一个错误,你的老师正在玩某种奇怪的游戏,要么我错过了一些明显的东西。

关于在嵌套循环中访问数组时缓存未命中,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/65926332/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com