performance - por - multiplicacion de matrices matefacil

OpenMP paralelizando la multiplicación de matrices por un ciclo triple(problema de rendimiento)

Question

Estoy escribiendo un programa para la multiplicación de matriz con OpenMP, que, para la conveniencia del caché, implementa las filas de multiplicación A x B (transposición) X filas en lugar de las clásicas A x B filas x columnas, para una mejor eficacia de la memoria caché. Al hacer esto me enfrenté a un hecho interesante que para mí es ilógico: si en este código paralelizo el ciclo externo, el programa es más lento que si coloco las directivas OpenMP en el ciclo más interno, en mi computadora los tiempos son 10.9 vs 8.1 segundos.

//A and B are double* allocated with malloc, Nu is the lenght of the matrixes 
//which are square

//#pragma omp parallel for
for (i=0; i<Nu; i++){
  for (j=0; j<Nu; j++){
    *(C+(i*Nu+j)) = 0.;
#pragma omp parallel for
    for(k=0;k<Nu ;k++){
      *(C+(i*Nu+j))+=*(A+(i*Nu+k)) * *(B+(j*Nu+k));//C(i,j)=sum(over k) A(i,k)*B(k,j)
    }
  }
}

Answer 1

Intente golpear el resultado con menos frecuencia. Esto induce el intercambio de caché y evita que la operación se ejecute en paralelo. Usar una variable local en su lugar permitirá que la mayoría de las escrituras tengan lugar en la caché L1 de cada núcleo.

Además, el uso de restrict puede ayudar. De lo contrario, el compilador no puede garantizar que las escrituras en C no cambien A y B

Tratar:

for (i=0; i<Nu; i++){
  const double* const Arow = A + i*Nu;
  double* const Crow = C + i*Nu;
#pragma omp parallel for
  for (j=0; j<Nu; j++){
    const double* const Bcol = B + j*Nu;
    double sum = 0.0;
    for(k=0;k<Nu ;k++){
      sum += Arow[k] * Bcol[k]; //C(i,j)=sum(over k) A(i,k)*B(k,j)
    }
    Crow[j] = sum;
  }
}

Además, creo que Elalfer tiene razón sobre la necesidad de reducción si paraleliza el ciclo más interno.

Answer 2

Probablemente pueda tener algunas dependencias en los datos cuando paraleliza el bucle externo y el compilador no puede resolverlo y agrega bloqueos adicionales.

Lo más probable es que decida que diferentes iteraciones del bucle externo podrían escribir en el mismo (C+(i*Nu+j)) y agrega bloqueos de acceso para protegerlo.

El compilador probablemente podría darse cuenta de que no hay dependencias si paraleliza el segundo ciclo. Pero descubrir que no hay dependencias que paralelicen el bucle externo no es tan trivial para un compilador.

ACTUALIZAR

Algunas medidas de rendimiento

Hola de nuevo. Parece que 1000 double * y + no son suficientes para cubrir el costo de la sincronización de hilos.

He realizado algunas pruebas pequeñas y la multiplicación escalar vectorial simple no es efectiva con openmp a menos que la cantidad de elementos sea inferior a ~ 10''000. Básicamente, cuanto más grande sea tu matriz, obtendrás más rendimiento con el uso de openmp.

Paralelamente al bucle más interno, deberá separar la tarea entre diferentes hilos y volver a recopilar datos 1''000''000 veces.

PD. Pruebe Intel ICC, es un poco gratuito para estudiantes y proyectos de código abierto. Recuerdo que estaba usando openmp para matrices de 10''000 elementos más pequeños.

ACTUALIZACIÓN 2: ejemplo de reducción

    double sum = 0.0;
    int k=0;
    double *al = A+i*Nu;
    double *bl = A+j*Nu;
    #pragma omp parallel for shared(al, bl) reduction(+:sum)
    for(k=0;k<Nu ;k++){
        sum +=al[k] * bl[k]; //C(i,j)=sum(over k) A(i,k)*B(k,j)
    }
    C[i*Nu+j] = sum;