Ложное разделение по нескольким ядрам
Произойдет ли ложный обмен в следующей программе?
объем памяти
- 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
Решение
В вашем коде есть некоторая ложная информация 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],
Другие решения
Других решений пока нет …