我正在尝试使用 openMP 优化下面函数 generate_histogram() 中的嵌套 for 循环。根据我在 this SE post 中阅读的内容,我尝试了很多不同的编译指示组合。 .
问题是嵌套 for 循环在没有 openMP 的情况下比使用 openMP 执行得更快!
如果我尝试使用缩减而不是原子 pragma 来并行化我的代码,我最终会遇到 netchunk 失败。有人知道这个的花哨调整吗?我正在尝试将数据分类为直方图。因此,直方图在实际代码中的大小是可变的,这与下面的代码片段不同。
#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);
}
最佳答案
这是一个有趣的问题。我修复了你的代码。 @KunHuang 的想法是正确的,但是您在私有(private)变量和共享变量方面还有更多问题。
您的旧函数称为 generate_histogram
,我在其中注释掉了 omp 内容。使用 OpenMP 的新方法称为 generate_histogram_omp
。
旧代码在我的系统(ivy bridge 双核)上完成时间为 0.67 秒,新代码在 0.32 秒内完成。
此外,我尝试融合您的循环,但它使性能变得更糟(可能是缓存问题),所以我只并行化了第一个循环,并且无论如何我仍然使用当前代码在两个内核上获得了 2 倍的速度。如果你想玩的话,我把融合代码注释掉了。
最后,矩阵的初始值并没有真正填满直方图,即只有几个箱子被填满。
我编译了
g++ hist.cpp -o hist -fopenmp -O3
代码:
#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);
}
关于c - 使用 openMP 并行化嵌套 for 循环,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16751445/