Увеличение скорости, несмотря на ложное разделение

Question

Я делал некоторые тесты на OpenMP и делал эту программу, которая не должна масштабироваться из-за ложного обмена массивом «сумма». Проблема в том, что она масштабируется. Даже "хуже":

• с 1 нить: 4 секунды (ICPC), 4 секунды (г ++)
• с 2 нитями: 2 секунды (ICPC), 2 секунды (г ++)
• с 4-резьбой : 0,5 секунды (icpc), 1 секунда (g ++)

Я действительно не получаю ускорение, которое получаю от 2 потоков до 4 потоков с помощью компиляторов Intel. Но самое главное: почему масштабирование настолько хорошо, хотя оно должно демонстрировать ложное разделение?

#include <iostream> 
#include <chrono> 

#include <array> 

#include <omp.h> 

int main(int argc, const char *argv[]) 
{ 
    const auto nb_threads = std::size_t{4}; 
    omp_set_num_threads(nb_threads); 

    const auto num_steps = std::size_t{1000000000}; 
    const auto step = double{1.0/num_steps}; 
    auto sum = std::array<double, nb_threads>{0.0}; 
    std::size_t actual_nb_threads; 

    auto start_time = std::chrono::high_resolution_clock::now(); 
    #pragma omp parallel 
    { 
     const auto id = std::size_t{omp_get_thread_num()}; 
     if (id == 0) { 
      // This is needed because OMP might give us less threads 
      // than the numbers of threads requested 
      actual_nb_threads = omp_get_num_threads(); 
     } 
     for (auto i = std::size_t{0}; i < num_steps; i += nb_threads) { 
      auto x = double{(i + 0.5) * step}; 
      sum[id] += 4.0/(1.0 + x * x); 
     } 
    } 
    auto pi = double{0.0}; 
    for (auto id = std::size_t{0}; id < actual_nb_threads; id++) { 
     pi += step * sum[id]; 
    } 
    auto end_time = std::chrono::high_resolution_clock::now(); 
    auto time = std::chrono::duration_cast<std::chrono::nanoseconds>(end_time - start_time).count(); 

    std::cout << "Pi: " << pi << std::endl; 
    std::cout << "Time: " << time/1.0e9 << " seconds" << std::endl; 
    std::cout << "Total nb of threads actually used: " << actual_nb_threads << std::endl; 

    return 0; 
} 

Answer 1

Этот код определенно может демонстрировать ложное разделение, если компилятор решил реализовать его таким образом. Но для компилятора это было бы глупо.

В первом цикле каждый поток обращается только к одному элементу sum. Нет никакой причины, чтобы num_steps записывал в фактическую память стека, хранящую этот элемент; гораздо быстрее просто сохранить значение в регистре и записать его после завершения цикла for. Поскольку массив не является изменчивым или атомарным, нет ничего, что помешало бы компилятору вести себя таким образом.

И, конечно же, во втором цикле нет записи в массив, поэтому нет ложного обмена.