3

这些优化中哪一个更好，在什么情况下？为什么？

直觉上，我感觉循环平铺通常会是更好的优化。

下面的例子呢？假设一个缓存在任何时候只能存储大约 20 个元素。

Original Loop:
for(int i = 0; i < 10; i++)
{
    for(int j = 0; j < 1000; j++)
    {
        a[i] += a[i]*b[j];
    }
}

Loop Interchange:
for(int i = 0; i < 1000; i++)
{
    for(int j = 0; j < 10; j++)
    {
        a[j] += a[j]*b[i];
    }
}

Loop Tiling:
for(int k = 0; k < 1000; k += 20)
{
    for(int i = 0; i < 10; i++)
    {
        for(int j = k; j < min(1000, k+20); j++)
        {
            a[i] += a[i]*b[j];
        }
    }
}
4

1 回答 1

2

您在问题中公开的前两个案例大致相同。在以下两种情况下，情况会真正改变：

情况1：

for(int i = 0; i < 10; i++)
{
    for(int j = 0; j < 1000; j++)
    {
        b[i] += a[i]*a[j];
    }
}

在这里，您正在访问矩阵“a”，如下所示： a[0]*a[0], a[0]*a 1 , a[0]*a[2],.... 在大多数架构中，矩阵结构存储在内存中，如：a[0]*a[0]、a 1 *a[0]、a[2]*a[0]（第一行的第一列，然后是第一列的第二列，... .)。想象一下，您的缓存只能存储 5 个元素，而您的矩阵是 6x6。将存储在缓存中的第一个“包”元素将是 a[0]*a[0] 到 a[4]*a[0]。您的第一次访问不会导致缓存未命中，因此 a[0][0] 存储在缓存中，但第二次是！0未存储在缓存中！然后操作系统将缓存元素包 a 0到4。然后你进行第三次访问： a[0]*a[2] 再次超出缓存。另一个缓存未命中！

正如你所知道的，案例 1 不是解决问题的好方法。它会导致大量缓存未命中，我们可以避免更改以下代码：

案例二：

for(int i = 0; i < 10; i++)
    {
        for(int j = 0; j < 1000; j++)
        {
            b[i] += a[i]*a[j];
        }
    }

在这里，如您所见，我们正在访问存储在内存中的矩阵。因此，它比案例 1 更好（更快）。

关于您发布的关于循环平铺、循环平铺和循环展开的第三个代码是在大多数情况下编译器自动执行的优化。 这是stackoverflow中的一篇非常有趣的帖子，解释了这两种技术；

希望能帮助到你！（对不起我的英语，我不是母语人士）

于 2013-09-26T20:29:28.180 回答