c++ - CPU 缓存临界跨度测试根据访问类型给出意外结果

Question

灵感来自 this recent question on SO and the answers given ，这让我觉得很无知，我决定花点时间了解一下 CPU 缓存 并编写了一个小程序来验证我是否正确地完成了这一切(很可能不是，恐怕)。我先写下假设 这是我期望的基础，所以如果这些是错误的，你可能会阻止我。根据我所阅读的内容，一般来说:

安 n -way关联缓存分为s集合，每个包含 n行，每行具有固定大小 L ;

每个主存地址A可以映射到 n 中的任何一个 的缓存行一 放;

地址A的集合可以通过将地址空间拆分为一个缓存行大小的槽，然后计算索引A 来找到被映射。的槽( I = A / L )，最后进行模运算将索引映射到目标集 T ( T = I % s );

高速缓存读取未命中比高速缓存写入未命中导致更高的延迟，因为 CPU 在等待获取主内存线时不太可能停顿并保持空闲状态。

我的第一个问题是: 这些假设正确吗？

假设它们是，我尝试使用这些概念，以便我可以实际看到它们对程序产生具体影响。我写了一个简单的测试，分配了一个 B 的内存缓冲区。字节并使用 重复访问该缓冲区的位置固定增量 给定步骤 从缓冲区开始 (这意味着如果 B 是 14 并且步长是 3，我只会重复访问位置 0、3、6、9 和 12 - 如果 B 是 13、14 或 15，则同样如此):

int index = 0;
for (int i = 0; i < REPS; i++)
{
    index += STEP;
    if (index >= B) { index = 0; }
    buffer[index] = ...; // Do something here!
}

由于上述假设，我的期望是:

设置时STEP等于 临界步幅 (即缓存行的大小乘以缓存中的集合数，或 L * s )，性能应该是 明显更糟比当 STEP例如，设置为 ( L * s) + 1 ，因为我们将仅访问映射到同一集合的内存位置，从而迫使缓存线更频繁地从该集合中逐出并导致更高的缓存未命中率；

当STEP等于临界步幅，性能不应该受到影响按尺寸B缓冲区，只要它不是太小(否则会访问的位置太少，缓存未命中会更少)；否则，性能应该会受到影响 来自 B ，因为使用更大的缓冲区，我们更有可能访问映射到不同集合的位置(特别是如果 STEP 不是 2 的倍数)；

读取和写入 时的性能损失应该更糟每个缓冲区位置比只写时到这些位置:写入内存位置不应该需要等待获取相应的行，因此访问映射到同一组的内存位置的事实(再次，通过使用临界步幅作为 STEP )应该有一个轻微影响。

所以我用了 RightMark Memory Analyzer找出我的 L1 CPU 数据缓存的参数，在我的程序中调整大小，然后尝试一下。这就是我编写主循环的方式( onlyWriteToCache 是一个可以从命令行设置的标志):

    ...
    for (int i = 0; i < REPS; i++)
    {
        ...
        if (onlyWriteToCache)
        {
            buffer[index] = (char)(index % 255);
        }
        else
        {
            buffer[index] = (char)(buffer[index] % 255);
        }
    }

结果简而言之:

预期 1) 和 2) 得到确认；

预期 3) 是 不是 确认的。

这个事实让我震惊，让我觉得有些事情我没有做对。当 B是 256 MB 和 STEP等于临界步幅，测试(在 GCC 4.7.1 上使用 -O3 编译)表明:

周期的只写版本遭受平均 ~6x 性能损失(6.234s vs 1.078s)；

循环的读写版本遭受平均 ~1.3x 性能损失(6.671s 对 5.25s)。

所以我的第二个问题是: 为什么会有这种差异？ 我预计读取和写入时的性能损失会高于仅写入时的性能损失。

为了完整起见，下面是我为做测试而编写的程序，其中常量反射(reflect)了我机器的硬件参数:L1 8 路关联的大小 数据缓存 是 32 KB，大小为 L每个缓存行的大小为 64 字节，总共有 64 组(CPU 有一个单独的相同大小和相同行大小的 L1 8 路指令缓存)。

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <iterator>
#include <algorithm>

using namespace std;

// Auxiliary functions

constexpr int pow(int base, int exp)
{
    return ((exp == 0) ? 1 : base * pow(base, exp - 1));
}

int main(int argc, char* argv[])
{
    //======================================================================
    // Define behavior from command-line arguments
    //======================================================================

    bool useCriticalStep = false;
    bool onlyWriteToCache = true;
    size_t BUFFER_SIZE = pow(2, 28);
    size_t REPS = pow(2, 27);

    if (argc > 0)
    {
        for (int i = 1; i < argc; i++)
        {
            string option = argv[i];
            if (option == "-c")
            {
                useCriticalStep = true;
            }
            else if (option == "-r")
            {
                onlyWriteToCache = false;
            }
            else if (option[1] == 's')
            {
                string encodedSizeInMB = option.substr(2);
                size_t sizeInMB = atoi(encodedSizeInMB.c_str());
                BUFFER_SIZE = sizeInMB * pow(2, 20);
            }
            else if (option[1] == 'f')
            {
                string encodedNumOfReps = option.substr(2);
                size_t millionsOfReps = atoi(encodedNumOfReps.c_str());
                REPS = millionsOfReps * pow(10, 6);
            }
        }
    }

    //======================================================================
    // Machine parameters
    //======================================================================

    constexpr int CACHE_SIZE = pow(2, 15);
    constexpr int CACHE_LINE_SIZE = 64;
    constexpr int CACHE_LINES_PER_SET = 8;
    constexpr int SET_SIZE = CACHE_LINE_SIZE * CACHE_LINES_PER_SET;
    constexpr int NUM_OF_SETS = CACHE_SIZE / SET_SIZE;

    //======================================================================
    // Print out the machine parameters
    //======================================================================

    cout << "CACHE SIZE: " << CACHE_SIZE / 1024 << " KB" << endl;
    cout << "CACHE LINE SIZE: " << CACHE_LINE_SIZE << " bytes" << endl;
    cout << "CACHE LINES PER SET: " << CACHE_LINES_PER_SET << endl;
    cout << "SET SIZE: " << SET_SIZE << " bytes" << endl;
    cout << "NUMBER OF SETS: " << NUM_OF_SETS << endl;

    fill_n(ostream_iterator<char>(cout), 30, '='); cout << endl;

    //======================================================================
    // Test parameters
    //======================================================================

    const int STEP = NUM_OF_SETS * CACHE_LINE_SIZE + (useCriticalStep ? 0 : 1);

    //======================================================================
    // Print out the machine parameters
    //======================================================================

    cout << "BUFFER SIZE: " << BUFFER_SIZE / pow(2, 20) << " MB" << endl;
    cout << "STEP SIZE: " << STEP << " bytes" << endl;
    cout << "NUMBER OF REPS: " << REPS << endl;

    fill_n(ostream_iterator<char>(cout), 30, '='); cout << endl;

    //======================================================================
    // Start the test
    //======================================================================

    char* buffer = new char[BUFFER_SIZE];

    clock_t t1 = clock();

    int index = 0;
    for (size_t i = 0; i < REPS; i++)
    {
        index += STEP;
        if (index >= BUFFER_SIZE)
        {
            index = 0;
        }

        if (onlyWriteToCache)
        {
            buffer[index] = (char)(index % 255);
        }
        else
        {
            buffer[index] = (char)(buffer[index] % 255);
        }
    }

    clock_t t2 = clock();

    //======================================================================
    // Print the execution time (in clock ticks) and cleanup resources
    //======================================================================

    float executionTime = (float)(t2 - t1) / CLOCKS_PER_SEC;
    cout << "EXECUTION TIME: " << executionTime << "s" << endl;

    delete[] buffer;
}

如果您设法通读了这个长问题，在此先感谢您。

Answer 1

关于您的期望数字 3，您是对的。正如您所料。请查收 "What every Programmer should know about memory"更多细节。这是一个很好的系列文章，解释了内存层次结构。

那么为什么很难确认数字 3:有两个主要原因。一个是内存分配，另一个是虚拟-物理地址转换。

内存分配

没有严格保证分配的内存区域的实际物理地址是什么。当你想测试 CPU 缓存时，我总是建议使用 posix_memalign强制分配到特定边界。否则你可能会看到一些奇怪的行为。

地址翻译

我提到的文章很好地解释了地址转换的工作方式。为了验证您的假设，您必须尝试确定预期的行为。最简单的方法如下:

实验

分配一组k int 形式的大内存区域(大约 512MB)数组并将它们全部对齐到 4096b 的页面边界。现在迭代内存区域中的所有元素并递增地添加 k 的更多区域。到你的实验。测量时间并通过读取的元素数量进行标准化。

代码可能如下所示:

#define N 10000000
for(size_t i=0; i < k; ++i) {

   size_t sum=0;
   clock_t t1= clock();
   for(size_t j=0; j < N; ++j) {
       for(size_t u=0; u<i; ++u) {
           sum += data[u][j];
       }
   }

   clock_t t2= clock();

}

那么会发生什么。所有大内存区域都对齐到 4k，并且基于之前的假设，同一行的所有元素都将映射到同一个缓存集。当循环中投影的内存区域数量大于缓存的关联性时，所有访问都将导致缓存未命中，并且每个元素的平均处理时间将增加。

更新

写入的处理方式取决于缓存线的使用方式和 CPU。现代 CPU 应用 MESI处理写入缓存行的协议(protocol)，以确保所有各方对内存(缓存一致性)有相同的看法。通常，在写入缓存行之前，必须先读取缓存行，然后再写回。是否识别回写取决于您访问数据的方式。如果您再次重新读取缓存行，您可能不会注意到差异。

然而，虽然程序员通常不会影响数据在 CPU 缓存中的存储方式，但与写入略有不同。可以执行所谓的流式写入，这些写入不会污染缓存，而是直接写入内存。这些写入也称为 non-temporal写道。