Ложное разделение по нескольким ядрам

Question

Произойдет ли ложное совместное использование в следующей программе?

Память

• 1 массив разделен на 4 равные области: [A1, A2, B1, B2]
• Весь массив может помещаться в кэш L1 в самой программе.
• Каждый регион дополняется кратным 64 байтам.

Шаги

1. thread 1 write to region A1 and A2 while thread 2 write to region B1 and B2.
2. barrier
3. thread 1 read B1 and write to A1 while thread 2 read B2 and write to A2.
4. barrier
5. Go to step 1.

Тест

#include <vector>
#include <iostream>
#include <stdint.h>
int main() {
    int N = 64;
    std::vector<std::int32_t> x(N, 0);
    #pragma omp parallel
    {
        for (int i = 0; i < 1000; ++i) {
            #pragma omp for
            for (int j = 0; j < 2; ++j) {
                for (int k = 0; k < (N / 2); ++k) {
                    x[j*N/2 + k] += 1;
                }
            }
            #pragma omp for
            for (int j = 0; j < 2; ++j) {
                for (int k = 0; k < (N/4); ++k) {
                    x[j*N/4 + k] += x[N/2 + j*N/4 + k] - 1;
                }
            }
        }
    }
    for (auto i : x ) std::cout << i << " ";
    std::cout << "\n";
}

Результат

32 elements of 500500 (1000 * 1001 / 2)
32 elements of 1000

Answer 1

В вашем коде присутствует некоторая ложная доля, поскольку x не гарантирует выравнивание по строке кэша.Заполнение не обязательно достаточно.В вашем примере N действительно маленький, что может быть проблемой.Обратите внимание, что в вашем примере N наибольшая нагрузка, вероятно, будет связана с разделением рабочих мест и управлением потоками.Если N достаточно большой, то есть array-size / number-of-threads >> cache-line-size, ложное совместное использование не является актуальной проблемой.

Чередование записей в A2 из разных потоков в вашем коде также не оптимально с точки зрения использования кэша, ноэто не ложная проблема совместного использования.

Обратите внимание, вам не нужно разбивать циклы.Если вы обращаетесь к индексу в памяти непрерывно в цикле, один цикл - это нормально, например,

#pragma omp for
for (int j = 0; j < N; ++j)
    x[j] += 1;

Если вы действительно осторожны, вы можете добавить schedule(static), тогда у вас есть гарантия равномерного распределения слов.

Помните, что ложное совместное использование является проблемой производительности, а не проблемой корректности, и имеет значение только в том случае, если это происходит часто.Типичные плохие паттерны - это записи в vector[my_thread_index].