producto - Paralelismo anidado para bucle con openMP

paralelizar en c

Question

Estoy tratando de optimizar el bucle for anidado en la función generate_histogram () a continuación con openMP. He probado mucho con diferentes combinaciones de pragmas en base a lo que he leído en este post SE .

¡El problema es que el bucle anidado para se realiza más rápido sin abrirMP que con openMP!

Si intento paralelizar mi código con reducción en lugar de pragma atómico, termino con falla de netchunk. ¿Alguien sabe un ajuste elegante para este? Estoy tratando de bin datos en un histograma. Por lo tanto, el histograma tiene un tamaño variable en el código real , a diferencia del fragmento de abajo.

#include<stdio.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#define float_t float
#include <time.h>
#include <omp.h>
float_t generate_histogram(float_t **matrix, int *histogram, int mat_size, int hist_size)
{
int i,j,k,count;
float_t max = 0.;
float_t sum;
//set histogram to zero everywhere
for(i = 0; i < hist_size; i++)
histogram[i] = 0;
//matrix computations
#pragma omp parallel for private(i) shared(histogram,j,k,max) schedule(dynamic)
//#pragma omp parallel for schedule(runtime)
for (i = 1; i < (mat_size-1); i++)
{
#pragma omp parallel for private(j,k) shared(histogram,max) schedule(dynamic)
//pragma omp prallel for schedule(dynamic)
for(j = 1; j < (mat_size-1); j++)
{
//assign current matrix[i][j] to element in order to reduce memory access
sum = fabs(matrix[i][j]-matrix[i-1][j]) + fabs(matrix[i][j] - matrix[i+1][j])
+ fabs(matrix[i][j]-matrix[i][j-1]) + fabs(matrix[i][j] - matrix[i][j+1]);
//compute index of histogram bin
k = (int)(sum * (float)mat_size);
#pragma omp atomic
histogram[k] += 1;
//keep track of largest element
if(sum > max)
max = sum;
}//end inner for
}//end outer for
return max;
}
main()
{
int i,j,N,boxes;
N = 10000;
float_t **matrix;
int* histogram;
boxes = N / 2;
//allocate a matrix with some numbers
matrix = calloc(N, sizeof(float_t **));
for(i = 0; i < N; i++)
matrix[i] = calloc(N, sizeof(float_t *));
for(i = 0; i < N; i++)
for(j = 0; j < N; j++)
matrix[i][j] = 1./(float_t) N * (float_t) i;
histogram = malloc(boxes * sizeof(int));
generate_histogram(matrix, histogram, N, boxes);
}

Answer 1

No es posible reducir una matriz o una estructura en OpenMP, que se menciona aquí: https://computing.llnl.gov/tutorials/openMP/#REDUCTION .

Creo que puedes declarar varias copias de histogram , cada una de las cuales se usa en un hilo. Luego, use otro bucle OpenMP para agregarlos.

Answer 2

Este es un problema interesante. He arreglado tu código. @KunHuang tuvo la idea correcta pero tiene varios problemas más con variables privadas y compartidas.

Su función anterior se llama generate_histogram en la que comenté las cosas omp. El nuevo que usa OpenMP se llama generate_histogram_omp . El código anterior termina en el tiempo 0.67 segundos en mi sistema (doble núcleo del puente de hiedra) y el nuevo código termina en 0.32 segundos.

Además, intenté fusionar tu bucle, pero empeoró mucho el rendimiento (probablemente un problema de caché), así que solo paralelizo el primer ciclo y de todos modos obtengo una velocidad 2x en dos núcleos con el código actual. Dejé el código fusionado como comentario si quieres jugar con él.

Por último, sus valores iniciales de la matriz realmente no completan el histograma, es decir, solo se están llenando unos pocos contenedores.

Compilé con

g++ hist.cpp -o hist -fopenmp -O3

El código:

#include<stdio.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#define float_t float
#include <time.h>
#include <omp.h>
float_t generate_histogram(float_t **matrix, int *histogram, int mat_size, int hist_size)
{
int i,j,k,count;
float_t max = 0.;
float_t sum;
//set histogram to zero everywhere
for(i = 0; i < hist_size; i++)
histogram[i] = 0;
//matrix computations
//#pragma omp parallel for schedule(runtime)
for (i = 1; i < (mat_size-1); i++)
{
//pragma omp prallel for schedule(dynamic)
for(j = 1; j < (mat_size-1); j++)
{
//assign current matrix[i][j] to element in order to reduce memory access
sum = fabs(matrix[i][j]-matrix[i-1][j]) + fabs(matrix[i][j] - matrix[i+1][j])
+ fabs(matrix[i][j]-matrix[i][j-1]) + fabs(matrix[i][j] - matrix[i][j+1]);
//compute index of histogram bin
k = (int)(sum * (float)mat_size);
histogram[k] += 1;
//keep track of largest element
if(sum > max)
max = sum;
}//end inner for
}//end outer for
return max;
}
float_t generate_histogram_omp(float_t **matrix, int *histogram, int mat_size, int hist_size) {
float_t max = 0.;
//set histogram to zero everywhere
int i;
for(i = 0; i < hist_size; i++)
histogram[i] = 0;
//matrix computations
#pragma omp parallel
{
int *histogram_private = (int*)malloc(hist_size * sizeof(int));
int i;
for(i = 0; i < hist_size; i++)
histogram_private[i] = 0;
float_t max_private = 0.;
int n;
int j;
#pragma omp for
for (i = 1; i < (mat_size-1); i++) {
for(j = 1; j < (mat_size-1); j++) {
// for (n=0; n < (mat_size-2)*(mat_size-2); n++) {
// int i = n/(mat_size-2)+1;
// int j = n%(mat_size-2)+1;
float_t sum = fabs(matrix[i][j]-matrix[i-1][j]) + fabs(matrix[i][j] - matrix[i+1][j])
+ fabs(matrix[i][j]-matrix[i][j-1]) + fabs(matrix[i][j] - matrix[i][j+1]);
//compute index of histogram bin
int k = (int)(sum * (float)mat_size);
histogram_private[k] += 1;
//keep track of largest element
if(sum > max_private)
max_private = sum;
}
}
#pragma omp critical
{
for(i = 0; i < hist_size; i++)
histogram[i] += histogram_private[i];
if(max_private>max)
max = max_private;
}
free(histogram_private);
}
return max;
}
int compare_hists(int *hist1, int *hist2, int N) {
int i;
int diff = 0;
for(i =0; i < N; i++) {
int tmp = hist1[i] - hist2[i];
diff += tmp;
if(tmp!=0) {
printf("i %d, hist1 %d, hist2 %d/n", i, hist1[i], hist2[i]);
}
}
return diff;
}
main() {
int i,j,N,boxes;
N = 10000;
float_t **matrix;
int* histogram1;
int* histogram2;
boxes = N / 2;
//allocate a matrix with some numbers
matrix = (float_t**)calloc(N, sizeof(float_t **));
for(i = 0; i < N; i++)
matrix[i] = (float_t*)calloc(N, sizeof(float_t *));
for(i = 0; i < N; i++)
for(j = 0; j < N; j++)
matrix[i][j] = 1./(float_t) N * (float_t) i;
histogram1 = (int*)malloc(boxes * sizeof(int));
histogram2 = (int*)malloc(boxes * sizeof(int));
for(i = 0; i<boxes; i++) {
histogram1[i] = 0;
histogram2[i] = 0;
}
double dtime;
dtime = omp_get_wtime();
generate_histogram(matrix, histogram1, N, boxes);
dtime = omp_get_wtime() - dtime;
printf("time %f/n", dtime);
dtime = omp_get_wtime();
generate_histogram_omp(matrix, histogram2, N, boxes);
dtime = omp_get_wtime() - dtime;
printf("time %f/n", dtime);
int diff = compare_hists(histogram1, histogram2, boxes);
printf("diff %d/n", diff);
}