Prestazioni terribili: un semplice problema di sovraccarico o c'è un difetto di programma?

Question

Ho qui quello che capisco essere un costrutto OpenMP relativamente semplice. Il problema è che il programma esegue circa 100-300 volte più velocemente con 1 thread rispetto a 2 thread. L'87% del programma viene speso in gomp_send_wait() e un altro 9,5% in gomp_send_post.

Il programma restituisce risultati corretti, ma mi chiedo se ci sia un difetto nel codice che sta causando qualche conflitto di risorse, o se è semplicemente che il sovraccarico della creazione del thread è drasticamente non ne vale la pena per un ciclo di blocco la dimensione 4. p varia da 17 a 1000, a seconda della dimensione della molecola che stiamo simulando.

I miei numeri sono per il caso peggiore, quando p è 17 e la dimensione del blocco 4. Le prestazioni sono le stesse sia che io stia utilizzando la programmazione statica, dinamica o guidata. Con p=150 e la dimensione del blocco 75, il programma è ancora 75x-100x più lento del seriale.

... 
    double e_t_sum=0.0; 
    double e_in_sum=0.0; 

    int nthreads,tid; 

    #pragma omp parallel for schedule(static, 4) reduction(+ : e_t_sum, e_in_sum) shared(ee_t) private(tid, i, d_x, d_y, d_z, rr,) firstprivate(V_in, t_x, t_y, t_z) lastprivate(nthreads) 
    for (i = 0; i < p; i++){ 
     if (i != c){ 
      nthreads = omp_get_num_threads();    
      tid = omp_get_thread_num(); 

      d_x = V_in[i].x - t_x; 
      d_y = V_in[i].y - t_y; 
      d_z = V_in[i].z - t_z; 


      rr = d_x * d_x + d_y * d_y + d_z * d_z; 

      if (i < c){ 

       ee_t[i][c] = energy(rr, V_in[i].q, V_in[c].q, V_in[i].s, V_in[c].s); 
       e_t_sum += ee_t[i][c]; 
       e_in_sum += ee_in[i][c];  
      } 
      else{ 

       ee_t[c][i] = energy(rr, V_in[i].q, V_in[c].q, V_in[i].s, V_in[c].s); 
       e_t_sum += ee_t[c][i]; 
       e_in_sum += ee_in[c][i];  
      } 

      // if(pid==0){printf("e_t_sum[%d]: %f\n", tid, e_t_sum[tid]);} 

     } 
    }//end parallel for 


     e_t += e_t_sum; 
     e_t -= e_in_sum;    

... 

Answer 1

Credo che si dovrebbe provare a spostare tutti quei rami (vale a dire IFS) all'interno del ciclo, e farlo in due cicli separati, uno per i < c, e uno per i> c. Questo sarebbe di grande beneficio anche per il codice a thread singolo, ma dovrebbe darti più parallelismo, anche se come hai detto il sovraccarico di creazione thread potrebbe essere maggiore dei benefici per il piccolo n.

Answer 2

Metiu ha ragione. Non ci si può aspettare buone prestazioni da un ciclo che contiene istruzioni condizionali. Questa è solo una cattiva programmazione. Anche per le prestazioni scalari.

Il tuo capo deve capire che OpenMP e la parallelizzazione in generale non sono magiche. Per ottenere buone prestazioni da un codice in parallelo, è necessario che il codice di base sia ottimizzato per le prestazioni scalari.

I test non devono essere rimossi. Il ciclo deve essere ristrutturato. Anche le prestazioni scalari ne trarranno vantaggio.

Answer 3

Sembra che sia un dato di fatto che se si esegue un codice seriale in una modalità multithead deve essere migliore. Questo non è un dato. E, spesso non è vero. Parallelizzare un ciclo da eseguire in più thread o più processori non sempre porta a prestazioni migliori. Nella maggior parte dei casi, è necessaria qualche ristrutturazione. Nel tuo caso il codice non è nemmeno un buon codice seriale.

Qualsiasi libro sull'ottimizzazione del codice seriale ha come regola numero 1 per i loop: rimuovere tutte le operazioni condizionali. I test costano Alcuni compilatori (a proposito, non si dice mai quale OS/compilatore/processore si sta utilizzando .. importa) si può provare a ottimizzare il codice condizionale. Alcuni compilatori (come il compilatore C di Sun) consentono anche di eseguire il programma in modalità "raccolta" in cui genera informazioni sul profilo di runtime sulla frequenza con cui vengono utilizzati i rami di un condizionale e quindi consentono di ricompilare in una modalità che utilizza tali dati raccolti per ottimizzare il codice generato. (Vedere l'opzione -xprofile)

La prima regola per l'ottimizzazione del codice parallelo è innanzitutto la migliore ottimizzazione seriale possibile. Quindi parallelizza i loop.

Spostando i condizionali fuori dal ciclo e, come suggerisce Metiu, riscrivendo il codice come due loop separati, si fornisce all'ottimizzatore una fonte migliore con cui lavorare. Il codice seriale funziona meglio e il codice parallelo è imbarazzantemente parallelo.

Tuttavia, i risultati possono variare a seconda del sistema operativo/del compilatore/della piattaforma.

Vedi Using OpenMP e Solaris Application Programming

Answer 4

Questo appare come un problema con l'implementazione OpenMP del compilatore GNU. Prova un altro compilatore. Intel ha un compilatore Linux che dovresti riuscire a scaricare una copia e provare qui.

Un'altra cosa che ho notato è che le prime variabili private che sembrano essere del tutto inutili. Potrebbe esserci un sovraccarico significativo nel fare copie private dell'array V_in quale potrebbe essere il tuo problema.

Direi che è uno di quei 2 problemi che è il vostro problema.

Answer 5

In primo luogo, provare a pompare la dimensione del blocco più grande ancora. La creazione del thread porta in overhead, raccogliendo nuovo lavoro per ogni thread, e la dimensione del grano deve essere abbastanza grande da sopraffarlo.

Una possibilità più grande: L'implementazione di GOMP della riduzione può essere molto scarsa (suggerita dai dati del profilo) e genera messaggi dopo ogni blocco, anziché accumularsi all'interno di ciascun thread e quindi raccoglierli alla fine. Provare ad allocare e_t_sum e e_in_sum come array con gli elementi nthreads e aggiungerli a e_t_sum[tid] all'interno del ciclo, quindi eseguire il ciclo su di essi per calcolare la somma globale dopo che il ciclo parallelo è terminato.

noti che questo introduce un potenziale problema falsa condivisione fatto che più elementi di queste matrici giacerà entro cachelines comuni, e più processori sarà scritto in questo stesso cacheline. Se lo usi su un set di core che condividono la cache, questo andrà bene, ma puzzerà altrove.

Altra possibilità: Si potrebbe trattarsi di falsa condivisione nei vostri aggiornamenti agli elementi di ee_t. Garantire l'allineamento di questo array e provare le dimensioni dei blocchi che sono multipli della dimensione della linea della cache. Un sottile accenno a questa patologia sarebbe la parte del ciclo in cui i > c si allunga in modo sproporzionato rispetto alla parte dove i < c.

Answer 6

In primo luogo, non penso che l'ottimizzazione del codice seriale in questo caso possa aiutare a rispondere al dilemma OpenMP. Non preoccuparti per questo

IMO ci sono tre possibili spiegazioni per il rallentamento:

1. Questo può spiegare un rallentamento facilmente. Gli elementi dell'array ee_t stanno portando a false condivisioni all'interno della linea della cache. False condivisione è quando core finiscono per scrivere alla stessa linea di cache non becuase che sono in realtà la condivisione dei dati, ma quando ciò che i nuclei stanno scrivendo sembra appena essere nella stessa linea di cache (che è il motivo per cui la sua chiamata falso sharing). Posso spiegare di più se non trovi false condivisioni su google. Rendere allineata la linea di cache degli elementi ee_t può essere di grande aiuto.

2. Il sovraccarico delle attività di deposizione delle uova è superiore al vantaggio del parallelismo. Hai provato meno di 8 core? Come sono le prestazioni a 2 core?

3. Il numero totale di iterazioni è piccolo, diciamo prendiamo 17 come esempio.Se lo dividi su 8 core, soffrirà di problemi di sbilanciamento del carico (specialmente dato che alcune delle tue iterazioni praticamente non stanno facendo alcun lavoro (quando sono == c). Almeno un core dovrà fare 3 iterazioni, mentre tutti gli altri saranno fare 2. Questo non spiega un rallentamento, ma sicuramente uno dei motivi per cui l'accelerazione non è così alta come ci si potrebbe aspettare. Dal momento che le iterazioni sono di lunghezza variabile, vorrei usare una pianificazione dinamica con una dimensione del blocco pari a 1 o utilizzare openmp guidato. esperimento con la dimensione del blocco, un pezzo troppo piccolo porterà anche a rallentamento.

Vorrei sapere come va.