paralelo código C para cálculo de distancia

Question

Tengo un código C que calcula la distancia entre dos conjuntos de nodos (tres coordinan cada uno), aunque mi código ha sido lo suficientemente rápido todavía, quiero aumentarlo un poco más usando computación paralela. Ya he encontrado algo de información sobre openMP y estoy tratando de usarlo ahora, pero hay algo un poco raro. Sin omp, el tiempo de CPU de código es 20s, ¡y se agregan las dos líneas de pragma que toman 160s! ¿Cómo podría pasar?

añado mi código aquí abajo

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; 
} 

muchas gracias por cualquier ayuda

Answer 1

(La respuesta a continuación se refiere al código inicial en la cuestión, que desde entonces se ha mejorado con la aplicación de estas sugerencias)

---

Es necesario leer más información sobre cómo utilizar OpenMP. La especificación está disponible en http://www.openmp.org; y hay enlaces a tutoriales y otros recursos.

Señalaré algunos problemas en su código y daré recomendaciones sobre cómo solucionarlos.

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

d se utiliza como una variable temporal, por lo que se debe marcar como private en #pragma omp parallel for (ver abajo) para evitar razas de datos. Mientras tanto, en lugar de asignación dinámica, solo usaría 3 carrozas separadas. diff también tiene un valor temporal, por lo que también debe ser private.

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

ha creado una región paralela donde cada hilo se ejecuta todo el bucle (porque la región no contiene construcciones de trabajo compartido), y en su interior se crea una región anidada con una nueva (!) Un conjunto de hilos, también cada uno ejecutando todo el ciclo interno. Agrega muchos costos indirectos y cálculos innecesarios a su programa. Lo que necesita es #pragma omp parallel for, y solo se aplica al lazo externo.

  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)); 

No se relaciona con el paralelismo, pero ¿por qué llamar pow sólo para calcular los cuadrados? Una buena multiplicación anterior probablemente sería más simple de leer y más rápida.

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

Dado que la acción es la misma (dist[k]=diff;), el código se puede simplificar mediante la combinación de dos condiciones con || (lógico o).

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

Aquí se calculan los valores agregados en el bucle externo.En OpenMP, esto se hace con la cláusula reduction de #pragma omp for.

 k++; 
    } 

Actualmente, se INCREMENTO k en cada iteración, creando así una dependencia innecesaria entre iteraciones que conduce a una carrera de datos de código paralelo. De acuerdo con su código, k es solo un "alias" conveniente para i/jump, así que simplemente asignelo como tal al comienzo de la iteración, y haga private.

Answer 2

Se utiliza una gran cantidad de sincronización cuando se agrega #pragma omp parallel tanto en bucle exterior y bucle interno.

Al usar #pragma omp parallel, hay un barrier después del ciclo, por lo que todos los hilos esperan hasta que finalice el último hilo.
En su caso, tiene que esperar a todos los hilos tanto en el bucle interno como en el bucle externo, por lo que obtiene una gran cantidad de sobrecarga para usar la sincronación.

Por lo general, es mejor utilizar #pragma omp parallel solo en el bucle exterior [suponiendo que haya suficiente trabajo por hacer ...] para minimizar la cantidad de barreras.

Answer 3

En su código, escriba en una matriz común a todos los hilos, dist. Probablemente estés teniendo problemas de intercambio falso allí. Intenta asignar esa matriz con relleno.