添加2个长向量的缓存优化

Question

给定2个长向量2000个元素，每个元素将被添加到具有32字节高速缓存线(单级高速缓存)和CPU的机器上。我们必须将这两个向量相加，这样总和就会进入一个新的向量。

例如c[0]=a[0]+b[0], c[1]=a[1]+b[1], c[2]=a[2]+b[2]......... c[1999]=a[1999]+b[1999]

我知道当c[0]=a[0]+b[0]完成时，我们将在缓存中有a[0]to a[31], b[0]to b[31], c[0]to c[31]。因此，我们将在每第32个元素处获得一个缓存未命中。有人问我：

你能对它进行更多的优化以获得更好的性能(超过我上面所说的。由于局部性，缓存未命中只有32个元素)？

我相信这里面还有一些我不知道的东西。

Answer 1

假设现代超标量CPU具有无序执行，您可以使用一种称为software pipelining的技术来帮助降低缓存未命中的成本。例如。

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

变成：

ai = a[0];
bi = b[0];
ci = ai + bi;
ai = a[1];
bi = b[1];
for (i = 0; i < N - 2; ++i)
{
    c[i] = ci;           // note that within this loop the order of operations has
    ci = ai + bi;        // been reversed - instead of load-add-store we now have
    ai = a[i + 2];       // store-add-load - this reduces serial dependencies
    bi = b[i + 2];
}
c[i] = ci;
ci = ai + bi;
c[i + 1] = ci;

通常，整个高速缓存未命中会耗费100秒的周期(DRAM延迟)，因此在这种简单的情况下，加载/存储和运算的重叠只会造成很小的差异，但对于复杂的示例，软件流水线有时可能是有用的。

话虽如此，大多数现代CPU现在都有自动(硬件)预取，因此软件流水线已经变得不像以前那么有用了。此外，许多显式优化现在都是由优秀的编译器自动处理的。