如何为此代码段执行内存阻塞
how to do memory blocking for this code snippet
我有这段代码，我正在尝试使用缓存一致性方法（例如具有缓存阻塞的时间和空间局部性）对其进行优化。 (https://www.intel.com/content/www/us/en/developer/articles/technical/cache-blocking-techniques.html)
void randFunction1(int *arrayb, int dimension)
{
int i, j;
for (i = 0; i < dimension; ++i)
for (j = 0; j < dimension; ++j) {
arrayb[j * dimension+ i] = arrayb[j * dimension+ i] || arrayb[i * dimension+ j];
}
}
这就是我对其进行优化的方式，但我被告知它似乎没有使用内存阻塞技术。
for (int i = 0; i < dimension; ++i){
int j = i;
for (; j < dimension; ++j)
{
//access 2 times
arrayb[j * dimension+ i] = arrayb[j * dimension+ i] || arrayb[i * dimension+ j];
arrayb[i * dimension+ j] = arrayb[i * dimension+ j] || arrayb[j * dimension + i];
}
}
有人能告诉我如何为这段示例代码使用缓存阻塞（对较小的图块使用局部性）吗？感谢您的帮助！
我认为您对缓存阻塞存在根本性的误解，误解了要求您执行的操作，或者要求您执行此操作的人不理解。我也不太愿意给你完整的答案，因为这有点像家庭作业问题的人为例子。
我们的想法是 block/tile/window 提升您正在操作的数据，因此您正在操作的数据在您对其进行操作时会保留在缓存中。要有效地做到这一点，您需要知道缓存的大小和对象的大小。你没有给我们足够的细节来了解这些答案，但我可以做一些假设来说明你如何使用上面的代码来做到这一点。
首先是数组在内存中的布局方式，以便我们稍后参考。说维度是 3.
这意味着我们有一个网格布局，其中 i 是第一个数字，j 是第二个数字，例如...
[0,0][0,1][0,2]
[1,0][1,1][1,2]
[2,0][2,1][2,2]
在内存中的真实情况如下：
[0,0][0,1][0,2][1,0][1,1][1,2][2,0][2,1][2,2]
我们也可以将其视为一维数组，其中：
[0,0][0,1][0,2][1,0][1,1][1,2][2,0][2,1][2,2]
[ 0 ][ 1 ][ 2 ][ 3 ][ 4 ][ 5 ][ 6 ][ 7 ][ 8 ]
如果我们的缓存行可以容纳 3 个这样的人，那么就会有 3 个 'blocks'。 0-2、3-5 和 6-8。如果我们按顺序访问它们，就会发生阻塞（假设数组的索引 0 的字节对齐正确......但让我们暂时保持简单 - 这可能已经处理好了）。也就是当我们访问0的时候，那么0、1、2就被加载到缓存中。接下来我们访问1，它已经存在了。然后2，已经在那里了。然后3，将3、4、5加载到缓存中等等。
让我们看一下原始代码。
arrayb[j * dimension+ i] = arrayb[j * dimension+ i] || arrayb[i * dimension+ j];
让我们只做几次迭代，但取出索引变量并用它们的值替换它们。我将使用 ^ 指向您访问的索引，并使用 |显示我们想象的缓存行的位置。
arrayb[0] = arrayb[0] || arrayb[0]
[ 0 ][ 1 ][ 2 ] | [ 3 ][ 4 ][ 5 ] | [ 6 ][ 7 ][ 8 ]
^
arrayb[3] = arrayb[3] || arrayb[1]
[ 0 ][ 1 ][ 2 ] | [ 3 ][ 4 ][ 5 ] | [ 6 ][ 7 ][ 8 ]
^ ^
arrayb[6] = arrayb[6] || arrayb[2]
[ 0 ][ 1 ][ 2 ] | [ 3 ][ 4 ][ 5 ] | [ 6 ][ 7 ][ 8 ]
^ ^
arrayb[1] = arrayb[1] || arrayb[3]
[ 0 ][ 1 ][ 2 ] | [ 3 ][ 4 ][ 5 ] | [ 6 ][ 7 ][ 8 ]
^ ^
所以你看到除了第一次迭代之外，你每次都越过缓存行，到处都是。
我想你注意到你正在执行的操作是逻辑或。这意味着你不必在循环中保留原来的操作顺序，因为你的答案是一样的。也就是说，先 arrayb[1] = arrayb[1] || arrayb[3] 还是先 arrayb[3] = arrayb[3] | arrayb[1] 都没有关系。
在您提出的解决方案中，您可能认为自己做得更好一些，因为您注意到在第二次和第四次迭代中我们访问相同索引的模式（只是翻转我们正在读取和写入的位置）但您没有完全不调整循环，所以实际上你只做了两倍的工作。
0 = 0 || 0
0 = 0 || 0
3 = 3 || 1
1 = 1 || 3
6 = 6 || 2
2 = 2 || 6
1 = 1 || 3
3 = 3 || 1
4 = 4 || 4
4 = 4 || 4
7 = 7 || 5
5 = 5 || 7
2 = 2 || 6
6 = 6 || 2
5 = 5 || 7
7 = 7 || 5
8 = 8 || 8
8 = 8 || 8
如果你修复了双重工作，你就成功了，但你并没有真的使用阻塞策略。老实说，你不能。这几乎就像这个问题被设计成非现实世界并且故意导致缓存问题。您的示例的问题在于您使用的是单个数组，该数组仅成对（两次）访问相同的内存位置。除了它们的交换，它们永远不会被重复使用。
您可以某种程度优化某些访问，但您将始终受制于跨越边界的多数集合。我认为这是你被要求做的，但这不是一个很好的示例问题。如果我们牢记数组中的内存实际上是如何被访问的，并且从未真正被重用，那么增加示例的大小会使它变得非常明显。
假设维度是 8，您的缓存大到足以容纳 16 个项目（x86_64 可以在缓存行中容纳 16 个整数）。那么最佳访问分组将是所有索引都落在 0-15、16-31、32-47 或 48-63 范围内的操作。没有那么多。
不跨越缓存行：
0 = 0 || 0
1 = 1 || 8
8 = 8 || 1
9 = 9 || 9
18 = 18 || 18
19 = 19 || 26
26 = 26 || 19
27 = 27 || 27
36 = 36 || 36
37 = 37 || 44
44 = 44 || 37
54 = 54 || 54
55 = 55 || 62
62 = 62 || 55
63 = 63 || 63
总是越过缓存行：
2 = 2 || 16
3 = 3 || 24
4 = 4 || 32
5 = 5 || 40
6 = 6 || 48
7 = 7 || 56
10 = 10 || 17
11 = 11 || 25
12 = 12 || 33
13 = 13 || 41
14 = 14 || 49
15 = 15 || 57
16 = 16 || 2
17 = 17 || 10
20 = 20 || 34
21 = 21 || 42
22 = 22 || 50
23 = 23 || 58
24 = 24 || 3
25 = 25 || 11
28 = 28 || 35
29 = 29 || 43
30 = 30 || 51
31 = 31 || 59
32 = 32 || 4
33 = 33 || 12
34 = 34 || 20
35 = 35 || 28
38 = 38 || 52
39 = 39 || 60
40 = 40 || 5
41 = 41 || 13
42 = 42 || 21
43 = 43 || 29
45 = 45 || 45
46 = 46 || 53
47 = 47 || 61
48 = 48 || 6
49 = 49 || 14
50 = 50 || 22
51 = 51 || 30
52 = 52 || 38
53 = 53 || 46
56 = 56 || 7
57 = 57 || 15
58 = 58 || 23
59 = 59 || 31
60 = 60 || 39
61 = 61 || 47
这真的很糟糕，因为超出的项目数量超过了适合缓存的项目数量。此时你唯一希望保存的是你注意到的模式，你可以在其中进行一半的内存访问，虽然聪明，但不是 blocking/tiling.
您提供的 link 对于说明高速缓存阻塞同样很糟糕。它没有很好地描述其循环中实际发生的事情，但至少它尝试了。
他们平铺内部循环以保持内存访问更本地化，我认为这是你被要求做的，但给出了它不能适用的问题。
你的老师本想给你 2 或 3 个数组，但不小心只给了你一个。它非常接近矩阵乘法，但缺少一个内部循环和另外两个数组。
我有这段代码，我正在尝试使用缓存一致性方法（例如具有缓存阻塞的时间和空间局部性）对其进行优化。 (https://www.intel.com/content/www/us/en/developer/articles/technical/cache-blocking-techniques.html)
void randFunction1(int *arrayb, int dimension)
{
int i, j;
for (i = 0; i < dimension; ++i)
for (j = 0; j < dimension; ++j) {
arrayb[j * dimension+ i] = arrayb[j * dimension+ i] || arrayb[i * dimension+ j];
}
}
这就是我对其进行优化的方式，但我被告知它似乎没有使用内存阻塞技术。
for (int i = 0; i < dimension; ++i){
int j = i;
for (; j < dimension; ++j)
{
//access 2 times
arrayb[j * dimension+ i] = arrayb[j * dimension+ i] || arrayb[i * dimension+ j];
arrayb[i * dimension+ j] = arrayb[i * dimension+ j] || arrayb[j * dimension + i];
}
}
有人能告诉我如何为这段示例代码使用缓存阻塞（对较小的图块使用局部性）吗？感谢您的帮助！
我认为您对缓存阻塞存在根本性的误解，误解了要求您执行的操作，或者要求您执行此操作的人不理解。我也不太愿意给你完整的答案，因为这有点像家庭作业问题的人为例子。
我们的想法是 block/tile/window 提升您正在操作的数据，因此您正在操作的数据在您对其进行操作时会保留在缓存中。要有效地做到这一点，您需要知道缓存的大小和对象的大小。你没有给我们足够的细节来了解这些答案，但我可以做一些假设来说明你如何使用上面的代码来做到这一点。
首先是数组在内存中的布局方式，以便我们稍后参考。说维度是 3.
这意味着我们有一个网格布局，其中 i 是第一个数字，j 是第二个数字，例如...
[0,0][0,1][0,2]
[1,0][1,1][1,2]
[2,0][2,1][2,2]
在内存中的真实情况如下：
[0,0][0,1][0,2][1,0][1,1][1,2][2,0][2,1][2,2]
我们也可以将其视为一维数组，其中：
[0,0][0,1][0,2][1,0][1,1][1,2][2,0][2,1][2,2]
[ 0 ][ 1 ][ 2 ][ 3 ][ 4 ][ 5 ][ 6 ][ 7 ][ 8 ]
如果我们的缓存行可以容纳 3 个这样的人，那么就会有 3 个 'blocks'。 0-2、3-5 和 6-8。如果我们按顺序访问它们，就会发生阻塞（假设数组的索引 0 的字节对齐正确......但让我们暂时保持简单 - 这可能已经处理好了）。也就是当我们访问0的时候，那么0、1、2就被加载到缓存中。接下来我们访问1，它已经存在了。然后2，已经在那里了。然后3，将3、4、5加载到缓存中等等。
让我们看一下原始代码。
arrayb[j * dimension+ i] = arrayb[j * dimension+ i] || arrayb[i * dimension+ j];
让我们只做几次迭代，但取出索引变量并用它们的值替换它们。我将使用 ^ 指向您访问的索引，并使用 |显示我们想象的缓存行的位置。
arrayb[0] = arrayb[0] || arrayb[0]
[ 0 ][ 1 ][ 2 ] | [ 3 ][ 4 ][ 5 ] | [ 6 ][ 7 ][ 8 ]
^
arrayb[3] = arrayb[3] || arrayb[1]
[ 0 ][ 1 ][ 2 ] | [ 3 ][ 4 ][ 5 ] | [ 6 ][ 7 ][ 8 ]
^ ^
arrayb[6] = arrayb[6] || arrayb[2]
[ 0 ][ 1 ][ 2 ] | [ 3 ][ 4 ][ 5 ] | [ 6 ][ 7 ][ 8 ]
^ ^
arrayb[1] = arrayb[1] || arrayb[3]
[ 0 ][ 1 ][ 2 ] | [ 3 ][ 4 ][ 5 ] | [ 6 ][ 7 ][ 8 ]
^ ^
所以你看到除了第一次迭代之外，你每次都越过缓存行，到处都是。
我想你注意到你正在执行的操作是逻辑或。这意味着你不必在循环中保留原来的操作顺序，因为你的答案是一样的。也就是说，先 arrayb[1] = arrayb[1] || arrayb[3] 还是先 arrayb[3] = arrayb[3] | arrayb[1] 都没有关系。
在您提出的解决方案中，您可能认为自己做得更好一些，因为您注意到在第二次和第四次迭代中我们访问相同索引的模式（只是翻转我们正在读取和写入的位置）但您没有完全不调整循环，所以实际上你只做了两倍的工作。
0 = 0 || 0
0 = 0 || 0
3 = 3 || 1
1 = 1 || 3
6 = 6 || 2
2 = 2 || 6
1 = 1 || 3
3 = 3 || 1
4 = 4 || 4
4 = 4 || 4
7 = 7 || 5
5 = 5 || 7
2 = 2 || 6
6 = 6 || 2
5 = 5 || 7
7 = 7 || 5
8 = 8 || 8
8 = 8 || 8
如果你修复了双重工作，你就成功了，但你并没有真的使用阻塞策略。老实说，你不能。这几乎就像这个问题被设计成非现实世界并且故意导致缓存问题。您的示例的问题在于您使用的是单个数组，该数组仅成对（两次）访问相同的内存位置。除了它们的交换，它们永远不会被重复使用。
您可以某种程度优化某些访问，但您将始终受制于跨越边界的多数集合。我认为这是你被要求做的，但这不是一个很好的示例问题。如果我们牢记数组中的内存实际上是如何被访问的，并且从未真正被重用，那么增加示例的大小会使它变得非常明显。
假设维度是 8，您的缓存大到足以容纳 16 个项目（x86_64 可以在缓存行中容纳 16 个整数）。那么最佳访问分组将是所有索引都落在 0-15、16-31、32-47 或 48-63 范围内的操作。没有那么多。
不跨越缓存行：
0 = 0 || 0
1 = 1 || 8
8 = 8 || 1
9 = 9 || 9
18 = 18 || 18
19 = 19 || 26
26 = 26 || 19
27 = 27 || 27
36 = 36 || 36
37 = 37 || 44
44 = 44 || 37
54 = 54 || 54
55 = 55 || 62
62 = 62 || 55
63 = 63 || 63
总是越过缓存行：
2 = 2 || 16
3 = 3 || 24
4 = 4 || 32
5 = 5 || 40
6 = 6 || 48
7 = 7 || 56
10 = 10 || 17
11 = 11 || 25
12 = 12 || 33
13 = 13 || 41
14 = 14 || 49
15 = 15 || 57
16 = 16 || 2
17 = 17 || 10
20 = 20 || 34
21 = 21 || 42
22 = 22 || 50
23 = 23 || 58
24 = 24 || 3
25 = 25 || 11
28 = 28 || 35
29 = 29 || 43
30 = 30 || 51
31 = 31 || 59
32 = 32 || 4
33 = 33 || 12
34 = 34 || 20
35 = 35 || 28
38 = 38 || 52
39 = 39 || 60
40 = 40 || 5
41 = 41 || 13
42 = 42 || 21
43 = 43 || 29
45 = 45 || 45
46 = 46 || 53
47 = 47 || 61
48 = 48 || 6
49 = 49 || 14
50 = 50 || 22
51 = 51 || 30
52 = 52 || 38
53 = 53 || 46
56 = 56 || 7
57 = 57 || 15
58 = 58 || 23
59 = 59 || 31
60 = 60 || 39
61 = 61 || 47
这真的很糟糕，因为超出的项目数量超过了适合缓存的项目数量。此时你唯一希望保存的是你注意到的模式，你可以在其中进行一半的内存访问，虽然聪明，但不是 blocking/tiling.
您提供的 link 对于说明高速缓存阻塞同样很糟糕。它没有很好地描述其循环中实际发生的事情，但至少它尝试了。
他们平铺内部循环以保持内存访问更本地化，我认为这是你被要求做的，但给出了它不能适用的问题。
你的老师本想给你 2 或 3 个数组，但不小心只给了你一个。它非常接近矩阵乘法，但缺少一个内部循环和另外两个数组。