c - cpu缓存访问时间分析

Question

我有以下程序，是我在 stackoverflow 上的其他人的帮助下编写的，用于理解缓存行和 CPU 缓存。我在下面发布了计算结果。

    1     450.0  440.0
    2     420.0  230.0
    4     400.0  110.0
    8     390.0   60.0
   16     380.0   30.0
   32     320.0   10.0
   64     180.0   10.0
  128      60.0    0.0
  256      40.0   10.0
  512      10.0    0.0
 1024      10.0    0.0

我使用下面发布的 gnuplot 绘制了一个图表。

我有以下问题。

1. 我的毫秒计时计算是否正确？ 440ms 好像很多时间？

2. 从图 cache_access_1(红线)我们可以得出结论缓存行的大小是 32 位(而不是 64 位？)

3. 在代码的 for 循环之间清除缓存？如果是，我该如何以编程方式执行此操作？

4. 如您所见，我在上面的结果中有一些 0.0 值。？这说明什么？也是测量的粒度粗糙？

请回复。

#include <stdio.h>
#include <sys/time.h>
#include <time.h>
#include <unistd.h>
#include <stdlib.h>

#define MAX_SIZE (512*1024*1024)

int main()
{
    clock_t start, end;
    double cpu_time;
    int i = 0;
    int k = 0;
    int count = 0;

    /*
     * MAX_SIZE array is too big for stack.This is an unfortunate rough edge of the way the stack works. 
     * It lives in a fixed-size buffer, set by the program executable's configuration according to the 
     * operating system, but its actual size is seldom checked against the available space.
     */

    /*int arr[MAX_SIZE];*/

    int *arr = (int*)malloc(MAX_SIZE * sizeof(int));

    /*cpu clock ticks count start*/

    for(k = 0; k < 3; k++)
    {
        start = clock();
        count = 0;

        for (i = 0; i < MAX_SIZE; i++)
        { 
            arr[i] += 3;
            /*count++;*/
        }

        /*cpu clock ticks count stop*/
        end = clock();

        cpu_time = ((double) (end - start)) / CLOCKS_PER_SEC;

        printf("cpu time for loop 1 (k : %4d) %.1f ms.\n",k,(cpu_time*1000));
    }

    printf("\n");
    for (k = 1 ; k <= 1024 ; k <<= 1)
    {
        /*cpu clock ticks count start*/
        start = clock();
        count = 0;

        for (i = 0; i < MAX_SIZE; i += k) 
        {
            /*count++;*/
            arr[i] += 3;
        }

        /*cpu clock ticks count stop*/
        end = clock();

        cpu_time = ((double) (end - start)) / CLOCKS_PER_SEC;

        printf("cpu time for loop 2 (k : %4d) %.1f ms.\n",k,(cpu_time*1000));
    }
    printf("\n");

    /* Third loop, performing the same operations as loop 2, 
       but only touching 16KB of memory
     */
    for (k = 1 ; k <= 1024 ; k <<= 1)
    {
        /*cpu clock ticks count start*/
        start = clock();
        count = 0;

        for (i = 0; i < MAX_SIZE; i += k) 
        {
            count++;
            arr[i & 0xfff] += 3;
        }

        /*cpu clock ticks count stop*/
        end = clock();

        cpu_time = ((double) (end - start)) / CLOCKS_PER_SEC;

        printf("cpu time for loop 3 (k : %4d) %.1f ms.\n",k,(cpu_time*1000));
    }

    return 0;
}

Answer 1

既然你在Linux上，我就从那个角度来回答。我还将在写作时考虑到 Intel(即 x86-64)架构。

1. 440 毫秒可能是准确的。查看结果的更好方法是每个元素或访问的时间。请注意，增加 k 会减少访问的元素数量。现在，缓存访问 2 显示了 0.9ns/访问的相当稳定的结果。这个时间大致相当于每次访问 1 - 3 个周期(取决于 CPU 的时钟速率)。所以尺寸 1 - 16(也许 32)是准确的。
2. 否(尽管我首先假设您指的是 32 字节还是 64 字节)。您应该问问自己，“缓存行大小”是什么样的？如果您访问小于缓存行，那么您将错过并随后命中一次或多次。如果大于或等于缓存行大小，则每次访问都会丢失。在 k=32 及以上时，访问 1 的访问时间相对恒定，每次访问 20ns。在 k=1-16 时，总体访问时间是恒定的，这表明缓存未命中的数量大致相同。所以我会得出结论，缓存行大小为 64 字节。
3. 是的，至少对于只存储 ~16KB 的最后一个循环。如何？要么接触很多其他数据，比如另一个 GB 数组。或者调用像x86的WBINVD这样的指令，写入内存，然后使所有缓存内容失效；但是，它要求您处于内核模式。
4. 如您所述，超过 32 号时，时间徘徊在 10 毫秒左右，这表明您的计时粒度。您需要增加所需的时间(这样 10 毫秒的粒度就足够了)或切换到不同的计时机制，这正是评论所讨论的内容。我喜欢使用指令 rdtsc(读取时间戳计数器(即循环计数))，但这可能比上面的建议更成问题。将代码切换到 rdtsc 基本上需要切换时钟、clock_t 和 CLOCKS_PER_SEC。但是，如果您的线程迁移，您仍然可能面临时钟漂移，但这是一个有趣的测试，所以我不会担心这个问题。

更多注意事项:一致步幅(如 2 的幂)的问题在于处理器喜欢通过预取来隐藏缓存未命中惩罚。您可以在 BIOS 中禁用许多机器上的预取器(请参阅 "Changing the Prefetcher for Intel Processors" )。

页面错误也可能会影响您的结果。您正在分配 500M 整数或大约 2GB 的存储空间。循环 1 尝试访问内存以便操作系统分配页面，但是如果您没有那么多可用内存(不仅仅是总内存，因为操作系统等占用了一些空间)那么您的结果将会出现偏差。此外，操作系统可能会开始回收一些空间，因此您将始终在某些访问中出现页面错误。

与之前相关，TLB也会对结果产生一些影响。硬件在转换后备缓冲区 (TLB) 中保留从虚拟地址到物理地址的映射的小型缓存。每页内存(在 Intel 上为 4KB)需要一个 TLB 条目。所以你的实验将需要 2GB/4KB => ~500,000 个条目。大多数 TLB 保存的条目少于 1000 个，因此测量值也会因该未命中而出现偏差。幸运的是，它只是每 4KB 或 1024 个整数执行一次。 malloc 可能正在为您分配“大”或“巨大”页面，了解更多详细信息 - Huge Pages in Linux .

另一个实验是重复第三个循环，但更改您正在使用的掩码，以便您可以观察每个缓存级别(L1、L2，也许是 L3，很少是 L4)的大小。您可能还会发现不同的缓存级别使用不同的缓存行大小。