Параллельный цикл OpenMP намного медленнее, чем обычный цикл

Вся программа была сведена к простому тесту:

    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 06.04.2022 15:24

@Bathsheba она присутствует в коде, что с ней не так?

Kaiyakha 06.04.2022 15:25

Несколько подозреваемых в качестве указателя: i) 1e10 выходит за пределы диапазона int, ii) компиляторы часто оптимизируют эти циклы for, вам нужно использовать volatile int, iii) метод измерения не отражает фактическое время процессора.

haleyk 06.04.2022 15:28

k[omp_get_thread_num()] в вашем коде вызывает ложное совместное использование, поскольку строка кеша, содержащая массив k, отправляется туда и обратно между кешами системы. Если вы измените определение массива на 4 * 16 целых чисел и вместо этого используете k[omp_get_thread_num() * 16], проблема должна исчезнуть.

Michael Klemm 06.04.2022 15:31

@MichaelKlemm Кажется, это работает. Но как мне тогда использовать параллельный цикл for, если я хочу, чтобы обрабатывался каждый элемент, а не каждый 16-й?

Kaiyakha 06.04.2022 15:42

Пусть каждый поток обрабатывает 16 элементов соседний за раз.

n. 1.8e9-where's-my-share m. 06.04.2022 15:50

@n.1.8e9-где-мой-шарем. Почему 16? Откуда это число?

Kaiyakha 06.04.2022 15:53

Типичный размер строки кэша составляет 64 байта.

n. 1.8e9-where's-my-share m. 06.04.2022 16:05

@Kaiyakha: "Почему 16? Откуда это число?" -- Предполагая sizeof(int)==4, вы можете хранить 16 целых чисел в одной строке кэша (при условии, что размер строки кэша равен 64 байтам).

Andreas Wenzel 06.04.2022 16:24

Да, 16 исходит из количества 4-байтовых целочисленных значений, которые могут быть сохранены в каждой 64-байтовой строке кэша.

Michael Klemm 06.04.2022 17:32

Обратите внимание, что хотя выполнение *16 в этом коде должно работать на большинстве машин, это не переносимо. Во-первых, нет гарантии, что строка кэша будет 64-байтной (несмотря на то, что это распространено). Более того, sizeof(int) не обязательно равно 4 (но опять же это очень распространено). alignas(std::hardware_destructive_interference_size) помогите исправить. Наконец, хотя и то, и другое может быть в порядке, этого недостаточно для обеспечения отсутствия ложного совместного использования: насколько я знаю, некоторые процессоры загружают строки кэша по блокам, например процессор Intel, который загружает 128 байт данных. См.: stackoverflow.com/a/52158819/12939557 .

Jérôme Richard 06.04.2022 18:44
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
2
11
64
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Как уже указывалось в различных комментариях, суть вашей проблемы в ложный обмен. Действительно, ваш пример — типичный случай, когда можно поэкспериментировать. Однако в вашем коде также есть немало проблем, таких как:

  • Скорее всего, вы увидите переполнение как в вашей переменной 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 байтов, я опускаю тот факт, что его размер может варьироваться для простоты). Этот должен работать? Я спрашиваю, потому что в моем случае это не так.

Kaiyakha 07.04.2022 11:49

schedule( static, 1 ), который я добавил, не имеет ничего общего с предотвращением ложного обмена. Это было сделано только для того, чтобы каждый поток обращался только к элементам массива k, которые соответствовали его собственному рангу. Без него расписание по умолчанию было бы (с моим компилятором) простым static со смежными фрагментами индексов размером loops/4. Тогда каждый поток получил бы доступ ко всем возможным индексам k для увеличения. В этом случае нужно было бы защитить эти обращения между потоками с помощью atomic или critical, что по существу повторно сериализует параллельный цикл.

Gilles 07.04.2022 14:07

В вашем случае, если ваш фактический код значительно не отличается от вашего фрагмента, предложение reduction - это путь.

Gilles 07.04.2022 14:08

Другие вопросы по теме