缓存使用、空间局部性和延迟

Question

我正在学习关于空间局部性的缓存操作。 (到目前为止，我的引用资料是 Lin 和 Snyder 的 Principles of Parallel Programming，this tutorial，当然还有维基百科。)

以下面的示例为例，使用 gcc 编译，在 Windows 7 Professional 上运行，使用 Intel Core2 Duo CPU (L7500)。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
    int *array;
    int length;
    int count;
    int range;
    int i;

    // generate an array of a million integers between 0 and 99
    length = 1000000;
    range = 100;
    array = calloc(length, sizeof(int));
    srand(time(NULL));
    for(i = 0; i < length; i++)
    {
        array[i] = rand() % range;
        // printf("%d\n", array[i]);
    }

    // count the number of occurrences of 3 in the array
    count=0;
    for(i=0; i<length; i++)
    {
        if(array[i]==3)
        {
            count++;
        }
    }
    printf("count = %6d\n", count);

    return 0;
}

现在在例程的后半部分，将读取整个整数数组，因此 CPU 应根据空间局部性提前将它们加载到缓存中。但是在循环期间的任何时候，有多少数组可以/应该/应该加载到缓存中？一次一个缓存行(64 字节/每个 4 字节 int = 16 个整数)，它的大块，还是一口气整个数组？

此外，据我了解，将数据从 RAM 加载到缓存(或根据教科书，从非本地内存到本地内存)所涉及的延迟可能比实际运行例程所需的时间要长得多。真的吗？

现在假设我们将此代码移至多处理器/多核机器，代码的计数部分更改为在 4、8、16 等并行线程(使用 pthreads)中运行，计算数组的单独部分，然后在最后将私有(private)计数加在一起。这是否会导致多次单独出现 RAM 到缓存延迟，从而使并行版本的运行速度比串行版本慢？

Answer 1

是的，内存速度和延迟确实支配着许多算法，有必要尽可能高效地使用内存缓存来加快这些速度。

并行运行可能会影响您的性能，但通常不会。弄清楚这一点需要大量的测试和调整。

例如，将四核芯片连接到一组 RAM。如果算法需要最大速度的内存读取并且计算总是快于 RAM 速度，则并行运行将不会获得任何好处，并且可能会减慢速度。

但是如果你有一个双插槽系统，每个 CPU 都会有自己的 RAM，算法会加快。

或者，系统可能会从 1 组 RAM 升级到 4 组，并从单 channel 切换到四 channel RAM 配置。届时，RAM 速度可能会超过计算速度，四核将从运行更多线程中获益。

在我看来，每个核心运行一个线程通常会使您受益，并且会利用系统升级。运行单个线程可能会避免少量的同步开销，但在未来总是会限制程序。