Maggiore velocità nonostante falsa condivisione

Question

Ho fatto alcuni test su OpenMP e ha fatto questo programma che non dovrebbe scalare a causa della falsa condivisione della matrice "somma". Il problema che ho è che scala. Anche "peggio":

• con 1 filetto: 4 secondi (ICPC), 4 secondi (g ++)
• con 2 capi: 2 secondi (ICPC), 2 secondi (g ++)
• con 4 fili : 0,5 secondi (icpc), 1 secondo (g ++)

Non ho davvero la velocità che ottengo da 2 thread a 4 thread con i compilatori Intel. Ma il più importante è: perché il ridimensionamento è così buono, anche se dovrebbe mostrare una condivisione errata?

#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

Quel codice sicuramente potrebbe esibire falsa condivisione, se il compilatore ha scelto di implementare in questo modo. Ma sarebbe una cosa stupida da fare per il compilatore.

Nel primo ciclo, ogni filo accede solo un elemento di sum. Non c'è motivo di scrivere num_steps nella memoria dello stack effettivo che memorizza quell'elemento; è molto più veloce mantenere il valore in un registro e scriverlo dopo che il ciclo è terminato. Dato che l'array non è volatile o atomico, non c'è nulla che impedisca al compilatore di comportarsi in questo modo.

E, naturalmente, nel secondo ciclo non c'è la scrittura alla matrice, in modo che nessun falso condivisione.