Вся программа была сведена к простому тесту:
const int loops = 1e10;
int j[4] = { 1, 2, 3, 4 };
time_t time = std::time(nullptr);
for (int i = 0; i < loops; i++) j[i % 4] += 2;
std::cout << std::time(nullptr) - time << std::endl;
int k[4] = { 1, 2, 3, 4 };
omp_set_num_threads(4);
time = std::time(nullptr);
#pragma omp parallel for
for (int i = 0; i < loops; i++) k[omp_get_thread_num()] += 2;
std::cout << std::time(nullptr) - time << std::endl;
В первом случае прохождение цикла занимает около 3 секунд, во втором случае результат непостоянен и может составлять от 4 до 9 секунд. Оба цикла работают быстрее при включенной некоторой оптимизации (например, в пользу скорости и оптимизации всей программы), но второй цикл все же значительно медленнее. Я попытался добавить барьер в конце цикла и явно указать массив как shared
, но это не помогло. Единственный случай, когда мне удалось ускорить параллельный цикл, — сделать циклы пустыми. В чем может быть проблема?
Windows 10 x64, процессор Intel Core i5 10300H (4 ядра)
@Bathsheba она присутствует в коде, что с ней не так?
Несколько подозреваемых в качестве указателя: i) 1e10 выходит за пределы диапазона int, ii) компиляторы часто оптимизируют эти циклы for, вам нужно использовать volatile int, iii) метод измерения не отражает фактическое время процессора.
k[omp_get_thread_num()]
в вашем коде вызывает ложное совместное использование, поскольку строка кеша, содержащая массив k
, отправляется туда и обратно между кешами системы. Если вы измените определение массива на 4 * 16 целых чисел и вместо этого используете k[omp_get_thread_num() * 16]
, проблема должна исчезнуть.
@MichaelKlemm Кажется, это работает. Но как мне тогда использовать параллельный цикл for, если я хочу, чтобы обрабатывался каждый элемент, а не каждый 16-й?
Пусть каждый поток обрабатывает 16 элементов соседний за раз.
@n.1.8e9-где-мой-шарем. Почему 16? Откуда это число?
Типичный размер строки кэша составляет 64 байта.
@Kaiyakha: "Почему 16? Откуда это число?" -- Предполагая sizeof(int)==4
, вы можете хранить 16 целых чисел в одной строке кэша (при условии, что размер строки кэша равен 64 байтам).
Да, 16 исходит из количества 4-байтовых целочисленных значений, которые могут быть сохранены в каждой 64-байтовой строке кэша.
Обратите внимание, что хотя выполнение *16
в этом коде должно работать на большинстве машин, это не переносимо. Во-первых, нет гарантии, что строка кэша будет 64-байтной (несмотря на то, что это распространено). Более того, sizeof(int)
не обязательно равно 4 (но опять же это очень распространено). alignas(std::hardware_destructive_interference_size)
помогите исправить. Наконец, хотя и то, и другое может быть в порядке, этого недостаточно для обеспечения отсутствия ложного совместного использования: насколько я знаю, некоторые процессоры загружают строки кэша по блокам, например процессор Intel, который загружает 128 байт данных. См.: stackoverflow.com/a/52158819/12939557 .
Как уже указывалось в различных комментариях, суть вашей проблемы в ложный обмен. Действительно, ваш пример — типичный случай, когда можно поэкспериментировать. Однако в вашем коде также есть немало проблем, таких как:
loops
, так и во всех ваших таблицах j
и k
;i%4
и добавил пункт schedule( static, 1)
. Это неправильный способ сделать это, но только для того, чтобы получить ожидаемые результаты без использования правильного предложения reduction
.Затем я переписал ваш пример, а также дополнил его тем, что, по моему мнению, является лучшим решением проблемы ложного обмена: с помощью предложения reduction
.
#include <iostream>
#include <omp.h>
int main() {
const long long loops = 1e10;
long long j[4] = { 1, 2, 3, 4 };
double time = omp_get_wtime();
for ( long long i = 0; i < loops; i++ ) {
j[i % 4] += 2;
}
std::cout << "sequential: " << omp_get_wtime() - time << std::endl;
time = omp_get_wtime();
long long k[4] = { 1, 2, 3, 4 };
#pragma omp parallel for num_threads( 4 ) schedule( static, 1 )
for ( long long i = 0; i < loops; i++ ) {
k[i%4] += 2;
}
std::cout << "false sharing: " << omp_get_wtime() - time << std::endl;
time = omp_get_wtime();
long long l[4] = { 1, 2, 3, 4 };
#pragma omp parallel for num_threads( 4 ) reduction( +: l[0:4] )
for ( long long i = 0; i < loops; i++ ) {
l[i%4] += 2;
}
std::cout << "reduction: " << omp_get_wtime() - time << std::endl;
bool a = j[0]==k[0] && j[1]==k[1] && j[2]==k[2] && j[3]==k[3];
bool b = j[0]==l[0] && j[1]==l[1] && j[2]==l[2] && j[3]==l[3];
std::cout << "sanity check: " << a << " " << b << std::endl;
return 0;
}
Компиляция и запуск без оптимизаций дает на моем ноутбуке:
$ g++ -O0 -fopenmp false.cc
$ ./a.out
sequential: 15.5384
false sharing: 47.1417
reduction: 4.7565
sanity check: 1 1
Что говорит само за себя в отношении улучшения, которое приносит пункт reduction
.
Теперь включение оптимизаций из компилятора дает более смягченную картину:
$ g++ -O3 -fopenmp false.cc
$ ./a.out
sequential: 4.8414
false sharing: 4.10714
reduction: 2.10953
sanity check: 1 1
Во всяком случае, это показывает, что в настоящее время компиляторы довольно хорошо избегают большей части ложного совместного использования. Действительно, с вашим начальным (ошибочным) k[omp_get_thread_num()]
не было разницы во времени с предложением reduction
и без него, что показывает, что компилятор смог избежать проблемы.
Спасибо за ответ! Как насчет использования (static, 8)
расписания? Теоретически каждый поток тогда работает с непрерывным блоком памяти размером 64 байта каждый (предполагая, что long long
составляет 8 байтов, я опускаю тот факт, что его размер может варьироваться для простоты). Этот должен работать? Я спрашиваю, потому что в моем случае это не так.
schedule( static, 1 )
, который я добавил, не имеет ничего общего с предотвращением ложного обмена. Это было сделано только для того, чтобы каждый поток обращался только к элементам массива k
, которые соответствовали его собственному рангу. Без него расписание по умолчанию было бы (с моим компилятором) простым static
со смежными фрагментами индексов размером loops/4
. Тогда каждый поток получил бы доступ ко всем возможным индексам k
для увеличения. В этом случае нужно было бы защитить эти обращения между потоками с помощью atomic
или critical
, что по существу повторно сериализует параллельный цикл.
В вашем случае, если ваш фактический код значительно не отличается от вашего фрагмента, предложение reduction
- это путь.
Техника измерения всегда вызывает подозрение номер один.