C语言 缓存使用情况、空间局部性和延迟

Question

我正在学习有关空间局部性的缓存操作。(到目前为止，我的参考资料是Lin和Snyder的并行编程原理，本教程，当然还有维基百科。

以以下示例为例，使用 gcc 编译，在 Windows 7 专业版上运行，使用英特尔酷睿 2 双核 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("%dn", 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 = %6dn", count);
    return 0;
}

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

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

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

Answer 1

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

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

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

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

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

在我看来，每个内核运行一个线程通常会使您受益，并将利用系统升级。运行单个线程可以避免少量的同步开销，但将来始终会限制程序。