codice C parallelo per calcolo distanza

Question

Ho un codice C che calcola la distanza tra due gruppi di nodi (tre coordinate ciascuno), anche se il mio codice è stato abbastanza veloce ancora, voglio potenziarlo un po 'di più usando calcolo parallelo. Ho già trovato alcune informazioni su openMP e sto cercando di usarlo in questo momento, ma c'è qualcosa di strano. Senza omp il codice cpu time è 20s, aggiungendo le due linee pragma ci vogliono 160! Come potrebbe accadere?

aggiungo il mio codice qui

float computedist(float **vG1, float **vG2, int ncft, int ntri2, int jump, float *dist){ 
    int k = 0, i, j; 
    float min = 0; 
    float max = 0; 
    float avg = 0; 
    float *d = malloc(3*sizeof(float)); 
    float diff; 

    #pragma omp parallel 
    for(i=0;i<ncft;i+=jump){ 
     #pragma omp parallel 
     for(j=0;j<ntri2;j++){ 
      d[0] = vG1[i][0] - vG2[j][0]; 
      d[1] = vG1[i][1] - vG2[j][1]; 
      d[2] = vG1[i][2] - vG2[j][2]; 
      diff = sqrt(pow(d[0],2) + pow(d[1],2) + pow(d[2],2)); 
      if(j==0) 
       dist[k] = diff; 
      else 
       if(diff<dist[k]) 
        dist[k] = diff; 

     } 
     avg += dist[k]; 
     if(dist[k]>max) 
      max = dist[k]; 
     k++; 
    } 

    printf("max distance: %f\n",max); 
    printf("average distance: %f\n",avg/(int)(ncft/jump)); 

    free(d); 

    return max; 
} 

Grazie mille per tutto l'aiuto

Answer 1

(La risposta qui sotto si riferisce al codice iniziale nella questione, che da allora è stato migliorato con l'applicazione di questi suggerimenti)

---

Hai bisogno di leggere di più su come usare OpenMP. La specifica è disponibile allo http://www.openmp.org; e ci sono collegamenti a tutorial e altre risorse.

Sottolineerò alcuni problemi nel codice e fornirò consigli su come risolverli.

float *d = malloc(3*sizeof(float)); 
    float diff; 

d viene utilizzato come una variabile temporanea, viene quindi contrassegnato come private in #pragma omp parallel for (vedi sotto) per evitare corse di dati. Nel frattempo, invece di allocazione dinamica, userei solo 3 galleggianti separati. diff contiene anche un valore temporaneo, quindi dovrebbe anche essere private.

#pragma omp parallel 
    for(i=0;i<ncft;i+=jump){ 
     #pragma omp parallel 
     for(j=0;j<ntri2;j++){ 

è stata creata una zona parallela in cui ogni thread esegue l'intero ciclo (perché la regione non contiene costrutti di condivisione di lavoro), e al suo interno è stata creata una zona nidificato con un nuovo (!) Insieme di fili, inoltre ognuno esegue l'intero ciclo interno. Aggiunge un sacco di spese generali e calcoli non necessari al tuo programma. Quello che ti serve è #pragma omp parallel for e applicato solo al ciclo esterno.

  d[0] = vG1[i][0] - vG2[j][0]; 
      d[1] = vG1[i][1] - vG2[j][1]; 
      d[2] = vG1[i][2] - vG2[j][2]; 
      diff = sqrt(pow(d[0],2) + pow(d[1],2) + pow(d[2],2)); 

non legati al parallelismo, ma perché chiamare pow solo per calcolare le piazze? Una buona vecchia moltiplicazione sarebbe probabilmente più semplice da leggere e più veloce.

  if(j==0) 
       dist[k] = diff; 
      else 
       if(diff<dist[k]) 
        dist[k] = diff; 

Poiché l'azione è la stessa (dist[k]=diff;), il codice può essere semplificata combinando due condizioni con || (logico o).

 } 
     avg += dist[k]; 
     if(dist[k]>max) 
      max = dist[k]; 

Qui si calcolano i valori aggregati attraverso il ciclo esterno.In OpenMP, questo è fatto con reduction clausola di #pragma omp for.

 k++; 
    } 

Attualmente, si incrementa k ad ogni iterazione, creando così una dipendenza non necessaria tra le iterazioni che conduce ad una gara di dati in codice parallelo. Secondo il tuo codice, k è solo un comodo "alias" per i/jump, quindi basta assegnarlo come tale all'inizio dell'iterazione e creare private.

Answer 2

Si utilizza un sacco di sincronizzazione quando si aggiunge #pragma omp parallel sia su circuito esterno e ciclo interno.

Quando si utilizza #pragma omp parallel, c'è un barrier dopo il ciclo, quindi tutti i thread attendono fino al termine dell'ultimo thread.
Nel tuo caso, devi attendere tutti i thread sia nel ciclo interno sia in quello esterno, ottenendo così un sovraccarico per l'uso della sincronizzazione.

In genere è preferibile utilizzare #pragma omp parallel solo sul loop esterno [presupponendo che ci sia abbastanza lavoro da fare ...] per ridurre al minimo la quantità di barriere.

Answer 3

Nel codice si scrive in un array comune a tutti i thread, dist. Probabilmente stai avendo problemi di condivisione falsi lì. Prova ad allocare quell'array con il padding.