Оптимизация компилятора устраняет последствия ложного обмена.Как? - PullRequest
Новая
       26

Оптимизация компилятора устраняет последствия ложного обмена.Как?

0 голосов
/ 13 октября 2018

Я пытаюсь повторить эффекты ложного обмена с использованием OpenMP, как объяснено во введении OpenMP Тима Маттсона .

Моя программа выполняет простую числовую интеграцию (см. Ссылку дляматематические подробности), и я реализовал две версии, первая из которых должна быть дружественной к кешу, так как каждый поток сохраняет локальную переменную для накопления своей части пространства индекса, 

const auto num_slices = 100000000; 
const auto num_threads = 4;  // Swept from 1 to 9 threads
const auto slice_thickness = 1.0 / num_slices;
const auto slices_per_thread = num_slices / num_threads;

std::vector<double> partial_sums(num_threads);

#pragma omp parallel num_threads(num_threads)
{
  double local_buffer = 0;
  const auto thread_num = omp_get_thread_num();
  for(auto slice = slices_per_thread * thread_num; slice < slices_per_thread * (thread_num + 1); ++slice)
    local_buffer += func(slice * slice_thickness); // <-- Updates thread-exclusive buffer
  partial_sums[thread_num] = local_buffer; 
}
// Sum up partial_sums to receive final result
// ...

, в то время какво второй версии каждый поток обновляет элемент в общем std::vector<double>, в результате чего каждая запись делает недействительными строки кэша во всех других потоках 

// ... as above
#pragma omp parallel num_threads(num_threads)
{
  const auto thread_num = omp_get_thread_num();
  for(auto slice = slices_per_thread * thread_num; slice < slices_per_thread * (thread_num + 1); ++slice)
    partial_sums[thread_num] += func(slice * slice_thickness); // <-- Invalidates caches
}
// Sum up partial_sums to receive final result
// ...

Проблема заключается в том, что Я не вижу никаких эффектовложного обмена, если я не отключу оптимизацию .

enter image description here

Компиляция моего кода (который должен учитывать несколько больше деталей, чем фрагменты выше) с использованием GCC 8.1 без оптимизации (-O0) приводит кРезультаты, которые я наивно ожидал, используя полную оптимизацию (-O3), устраняют любые различия в производительности между двумя версиями, как показано на графике.

Чем это объясняется?Компилятор фактически устраняет ложное разделение?Если нет, то почему этот эффект настолько мал при запуске оптимизированного кода?

Я на машине с Core-i7, использующей Fedora.На графике показаны средние значения, для которых стандартные отклонения выборки не добавляют никакой информации к этому вопросу.

1 Ответ

0 голосов
/ 13 октября 2018

tl; dr: компилятор оптимизирует вашу вторую версию до первой.

Рассмотрим код в цикле вашей второй реализации - на мгновение игнорируем его OMP / многопоточный аспект.

У вас есть приращения значения в пределах std::vector - которое обязательно находится в куче (ну, в любом случае, вплоть до C ++ 17 и в том числе).Компилятор видит, что вы добавляете значение в кучу в цикле;это типичный кандидат на оптимизацию: он берет доступ к куче из цикла и использует регистр в качестве буфера.Ему даже не нужно читать из кучи, поскольку это всего лишь дополнения - так что это, по сути, приходит к вашему первому решению.

Смотрите, как это происходит на GodBolt (с упрощенным примером) - обратите внимание, что код для bar1() и bar2() практически одинаков с накоплением в регистрах.

Теперь тот факт, что задействованы многопоточность и OMP, нене меняйте вышесказанное.Если бы вы использовали, скажем, std::atomic<double> вместо double, то он мог бы измениться (и, возможно, даже тогда, если компилятор достаточно умен).

Примечания:

  • Спасибо @Evg за то, что он заметил явную ошибку в коде предыдущей версии этого ответа.
  • Компилятор должен уметь знать что func() также не изменит значение вашего вектора - или не решит, что для целей добавления это не должно иметь большого значения.
  • Эта оптимизация может рассматриваться как Снижение прочности - от операции с кучей до операции с регистром - но я не уверен, что в этом случае используется термин.
...