Будет ли этот std::vector push_back в параллельной области OpenMP приводить к ложному разделению?

Пример кода ниже - это упрощенная версия моего рабочего кода. В этом коде запись в общую переменную выполняется только в последней строке, где std::vector::push_back называется.

std::vector<struct FortyByteStruct> results;

#pragma omp parallel for num_threads(8)
for (int i = 0; i < 250; i++)
{
    struct FortyByteStruct result = some_heavy_work(i);

    #pragma omp critical
    {
        results.push_back(result);
    }
}

Мне было интересно, если это push_back Операция может привести к ложному обмену, что даст мне шанс еще больше оптимизироваться, избавившись от него. Я решил сделать несколько стендовых тестов, прежде чем углубляться в эту проблему.

С chronoЯ измерил время выполнения настенных часов some_heavy_work() и критический раздел отдельно. Последнее заняло около 10^(-4) раз времени выполнения первого, поэтому я пришел к выводу, что оптимизация этой части практически не принесет пользы, независимо от того, используется ложное разделение или нет.

Во всяком случае, мне все еще любопытно, является ли ложная передача здесь проблемой. Должен ли я смотреть на внутреннюю реализацию std::vector? Любое просвещение будет с благодарностью. (Я на VS2015)

Источник

2 ответа

Решение

Учитывая, что ваш FortyByteStruct Возможно, он меньше, чем строка кэша (обычно 64 байта), при записи данных результатов может произойти некоторое ошибочное совместное использование. Тем не менее, это вряд ли имеет значение, потому что оно будет омрачено стоимостью критического раздела, а также "истинным" разделением изменений vector сам (не это данные). Вам не нужно знать детали std::vectorРеализация - только то, что его данные непрерывны в памяти и что его состояние (указатель (и) на данные / размер / емкость) находится в памяти самой векторной переменной. Ложное совместное использование обычно является проблемой, когда к нескольким потокам доступ к отдельным данным в одной строке кэша осуществляется незащищенным способом. Имейте в виду, что ложный обмен не влияет на правильность, только производительность.

Немного другой пример ложного обмена был бы, когда у вас есть std::vector<std::vector<struct FortyByteStruct>> и каждый поток выполняет незащищенный push_back, Я объяснил это подробно здесь.

В вашем примере, с известным общим размером вектора, лучшим подходом было бы изменить размер вектора перед циклом, а затем просто назначить results[i] = result, Это позволяет избежать критической секции, и OpenMP обычно распределяет итерации цикла таким образом, что существует небольшое ложное совместное использование. Также вы получаете детерминированный порядок results,

Тем не менее, когда вы подтвердили измерения, что время доминирует some_heavy_workтогда ты в порядке.

Источник

Я не эксперт в реализации std::vector, но я уверен, что он не будет проверять, пишет ли другой процесс одновременно.

Тем не менее, вот два совета:

  • Да, критическая операция имеет небольшие накладные расходы, но она незначительна по сравнению с выигрышем от выполнения some_heavy_work параллельно (я думаю...). Так что, сомневаюсь, я бы оставил его там

  • Вам следует проверить разницу между критическим и атомарным ( openMP, атомарный и критический?).

Надеюсь, поможет

Источник
Другие вопросы по тегам