Пожалуйста, объясните согласованность кэша - PullRequest
Новая
       16

Пожалуйста, объясните согласованность кэша

0 голосов
/ 18 ноября 2018

Я недавно узнал о ложном совместном использовании, которое в моем понимании связано с попыткой ЦП создать согласованность кэша между различными ядрами.Однако разве следующий пример не демонстрирует, что нарушена когерентность кэша?

В приведенном ниже примере запускаются несколько потоков, которые увеличивают глобальную переменную x, и несколько потоков, которые присваивают значение x для y, и наблюдатель, которыйпроверяет, если у> х.Условие y> x никогда не должно выполняться, если между ядрами имеется согласованность памяти, поскольку y увеличивается только после увеличения x.Тем не менее, это условие происходит по результатам выполнения этой программы.Я тестировал его на Visual Studio как на 64, так и на 86, как отладка, так и выпуск с почти одинаковыми результатами.

Итак, согласованность памяти происходит только тогда, когда она плоха, и никогда, когда она хороша?:) Пожалуйста, объясните, как работает согласованность кэша и как он не работает.Если вы можете привести меня к книге, в которой объясняется тема, я буду вам благодарен.

edit: я добавил защиту везде, где это возможно, но при этом отсутствует согласованность памяти (предположительно из-за устаревшего кэша).Кроме того, я знаю, что в программе есть гонка данных, вот и весь смысл.Мой вопрос: почему существует гонка данных, если процессор поддерживает согласованность кэша (если он не поддерживал согласованность кэша, то что такое ложное совместное использование и как это происходит?).Спасибо. 

#include <intrin.h>
#include <windows.h>

#include <iostream>
#include <thread>
#include <atomic>
#include <list>
#include <chrono>
#include <ratio>

#define N 1000000

#define SEPARATE_CACHE_LINES 0
#define USE_ATOMIC 0

#pragma pack(1)
struct  
{
    __declspec (align(64)) volatile long x;
#if SEPARATE_CACHE_LINES
    __declspec (align(64))
#endif
        volatile long y;
} data;

volatile long &g_x = data.x;
volatile long &g_y = data.y;

int g_observed;
std::atomic<bool> g_start;

void Observer()
{
    while (!g_start);
    for (int i = 0;i < N;++i)
    {
        _mm_mfence();
        long y = g_y;
        _mm_mfence();
        long x = g_x;
        _mm_mfence();
        if (y > x)
        {
            ++g_observed;
        }
    }
}

void XIncreaser()
{
    while (!g_start);
    for (int i = 0;i < N;++i)
    {
#if USE_ATOMIC
        InterlockedAdd(&g_x,1);
#else
        _mm_mfence();
        int x = g_x+1;
        _mm_mfence();
        g_x = x;
        _mm_mfence();
#endif
    }
}

void YAssigner()
{
    while (!g_start);
    for (int i = 0;i < N;++i)
    {
#if USE_ATOMIC
        long x = g_x;
        InterlockedExchange(&g_y, x);
#else
        _mm_mfence();
        int x = g_x;
        _mm_mfence();
        g_y = x;
        _mm_mfence();
#endif
    }
}

int main()
{
    using namespace std::chrono;

    g_x = 0;
    g_y = 0;
    g_observed = 0;
    g_start = false;

    const int NAssigners = 4;
    const int NIncreasers = 4;

    std::list<std::thread> threads;

    for (int i = 0;i < NAssigners;++i)
    {
        threads.emplace_back(YAssigner);
    }
    for (int i = 0;i < NIncreasers;++i)
    {
        threads.emplace_back(XIncreaser);
    }
    threads.emplace_back(Observer);

    auto tic = high_resolution_clock::now();
    g_start = true;

    for (std::thread& t : threads)
    {
        t.join();
    }

    auto toc = high_resolution_clock::now();

    std::cout << "x = " << g_x << " y = " << g_y << " number of times y > x = " << g_observed << std::endl;
    std::cout << "&x = " << (int*)&g_x << " &y = " << (int*)&g_y << std::endl;
    std::chrono::duration<double> t = toc - tic;
    std::cout << "time elapsed = " << t.count() << std::endl;
    std::cout << "USE_ATOMIC = " << USE_ATOMIC << " SEPARATE_CACHE_LINES = " << SEPARATE_CACHE_LINES << std::endl;

    return 0;
}

Пример вывода: 

x = 1583672 y = 1583672 number of times y > x = 254
&x = 00007FF62BE95800 &y = 00007FF62BE95804
time elapsed = 0.187785
USE_ATOMIC = 0 SEPARATE_CACHE_LINES = 0

1 Ответ

0 голосов
/ 19 ноября 2018

Ложный обмен в основном связан с производительностью, а не слаженностью или порядком программы. Кэш процессора работает на уровне детализации, который обычно составляет 16, 32, 64, ... байтов. Это означает, что если два независимых элемента данных расположены близко друг к другу в памяти, они будут испытывать операции кеширования друг друга. В частности, если & a% CACHE_LINE_SIZE == & b% CACHE_LINE_SIZE, то они будут использовать общую строку кэша.

Например, если cpu0 & 1 сражаются за a, а cpu 2 & 3 сражаются за b, строка кэша, содержащая a & b, будет перемещаться между каждым из 4 кешей. Это эффект ложного совместного использования и приводит к значительному снижению производительности.

Ложное совместное использование происходит из-за того, что алгоритм когерентности в кешах требует постоянного представления памяти. Хороший способ проверить это - поместить два атомных счетчика в структуру, разнесенную на один или два k: 

struct a {
      long    a;
      long    pad[1024];
      long    b;
};

и найдите симпатичную небольшую функцию машинного языка для атомарного приращения. Затем обрежьте свободные потоки NCPU / 2, увеличивающие потоки a и NCPU / 2, увеличивающие b, пока они не достигнут большого числа. Затем повторите, комментируя массив pad. Сравните время.

Когда вы пытаетесь разобраться в деталях машины, четкость и точность - ваши друзья; C ++ и странные объявления атрибутов не являются.

...