Кэш-линии, ложное совместное использование и выравнивание - программирование
Подтвердить что ты не робот

Кэш-линии, ложное совместное использование и выравнивание

Я написал следующую короткую программу на С++, чтобы воспроизвести эффект ложного обмена, описанный Herb Sutter:

Скажем, мы хотим выполнить общее количество операций WORKLOAD integer, и мы хотим, чтобы они были равномерно распределены по числу (PARALLEL) потоков. Для целей этого теста каждый поток будет увеличивать свою собственную выделенную переменную из массива целых чисел, поэтому процесс может быть идеально параллелизуемым.

void thread_func(int* ptr)
{
    for (unsigned i = 0; i < WORKLOAD / PARALLEL; ++i)
    {
        (*ptr)++;
    }
}

int main()
{
    int arr[PARALLEL * PADDING];
    thread threads[PARALLEL];

    for (unsigned i = 0; i < PARALLEL; ++i)
    {
        threads[i] = thread(thread_func, &(arr[i * PADDING]));
    }
    for (auto& th : threads)
    {
        th.join();
    }
    return 0;
}

Я думаю, что эту идею легко понять. Если вы установили

#define PADDING 16

каждый поток будет работать в отдельной строке кэша (если длина строки кэша должна быть 64 байта). Таким образом, результатом будет линейное увеличение ускорения до PARALLEL > # core. Если, с другой стороны, PADDING устанавливается на любое значение ниже 16, следует столкнуться с серьезным соперничеством, поскольку, по крайней мере, два потока теперь могут работать в одной и той же строке кэша, которая, однако, защищена встроенным аппаратным мьютексом. Мы ожидаем, что наше ускорение не только будет сублинейным в этом случае, но даже всегда будет < 1, из-за невидимого конвоя.

Теперь мои первые попытки почти оправдали эти ожидания, но минимальная ценность PADDING, необходимая для избежания ложного обмена, составляла около 8, а не 16. Я был довольно озадачен примерно через полчаса, пока не пришел к очевидному выводу, что там не гарантирует, что мой массив будет выровнен точно до начала строки кэша внутри основной памяти. Фактическое выравнивание может варьироваться в зависимости от многих условий, включая размер массива.

В этом примере нам, конечно, не нужно, чтобы массив был выровнен по-особому, потому что мы можем просто оставить PADDING на 16, и все будет хорошо. Но можно представить случаи, когда это действительно имеет значение, независимо от того, выстроена ли определенная структура в строке кэша или нет. Следовательно, я добавил несколько строк кода, чтобы получить некоторую информацию о фактическом выравнивании моего массива.

int main()
{
    int arr[PARALLEL * 16];
    thread threads[PARALLEL];
    int offset = 0;

    while (reinterpret_cast<int>(&arr[offset]) % 64) ++offset;
    for (unsigned i = 0; i < PARALLEL; ++i)
    {
        threads[i] = thread(thread_func, &(arr[i * 16 + offset]));
    }
    for (auto& th : threads)
    {
        th.join();
    }
    return 0;
}

Несмотря на то, что в этом случае это решение получилось мне хорошо, я не уверен, что это будет хороший подход в целом. Итак, вот мой вопрос:

Есть ли какой-либо общий способ иметь объекты в памяти, выровненные по линиям кэша, отличные от того, что я сделал в приведенном выше примере?

(используя g++ MinGW Win32 x86 v.4.8.1 posix dwarf rev3)

4b9b3361

Ответ 1

Вы должны иметь возможность запросить требуемое выравнивание от компилятора:

alignas(64) int arr[PARALELL * PADDING]; // align the array to a 64 byte line