Zwiększona prędkość pomimo fałszywego współdzielenia

Question

Wykonałem kilka testów OpenMP i wykonałem ten program, który nie powinien być skalowany z powodu fałszywego współdzielenia tablicy "suma". Problem w tym, że to skaluje. Nawet "gorsze":

• z 1 Gwint 4 sekund (ICPC), 4 s (g ++)
• 2 nici: 2 sekundy (ICPC), 2 sekundy (g ++)
• z 4 nici : 0.5 sekundy (icpc), 1 sekunda (g ++)

Naprawdę nie dostaję przyspieszenia, które otrzymuję od 2 wątków do 4 wątków z kompilatorami Intel. Ale najważniejsze jest: dlaczego skalowanie jest tak dobre, mimo że powinno pokazywać fałszywe dzielenie się?

#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

Ten kod zdecydowanie mógłby wykazują fałszywy podział, jeśli kompilator zdecydował się wdrożyć go w ten sposób. Ale byłoby to niemądre dla kompilatora.

W pierwszej pętli każdy wątek ma tylko dostęp do jednego elementu z sum. Nie ma powodu, aby zapisywać num_steps do rzeczywistej stosu pamięci przechowującej ten element; znacznie szybciej jest zachować wartość w rejestrze i zapisać ją po zakończeniu pętli for. Ponieważ tablica nie jest niestabilna ani atomowa, nic nie stoi na przeszkodzie, aby kompilator zachowywał się w ten sposób.

I, oczywiście, w drugiej pętli nie ma zapisu do tablicy, więc nie ma fałszywego udostępniania.