使用 OpenMP 并行化二维 Haar 小波变换的 C 代码

Question

这是我的第一个问题。我正在尝试与 openMP 并行化 C 中的 2d haar 变换函数。我获得了它 here 并进行了相应的修改。该程序采用黑白图像，将其放入矩阵并计算 haar 小波变换的一个级别。最后，它对值进行归一化并将转换后的图像写入磁盘。

这是生成的图像1 level of HDT

我的问题是并行版本比串行版本运行得慢得多。现在我在这里附上我想要并行化的主要部分的片段（稍后我可以放置所有周围的代码）：

void haar_2d ( int m, int n, double u[] )
// m & n are the dimentions (every image is a perfect square)
//u is the input array in **(non column-major!)** row-major order</del>
int i;
int j;
int k;
double s;
double *v;

int tid, nthreads, chunk;

s = sqrt ( 2.0 );

v = ( double * ) malloc ( m * n * sizeof ( double ) );

for ( j = 0; j < n; j++ )
{
    for ( i = 0; i < m; i++ )
    {
        v[i+j*m] = u[i+j*m];
    }
}
/*
Determine K, the largest power of 2 such that K <= M.
*/
k = 1;
while ( k * 2 <= m )
{
    k = k * 2;
}

/*   Transform all columns.  */

while ( n/2 < k ) // just 1 level of transformation
{
    k = k / 2;

    clock_t begin = clock();

    #pragma omp parallel shared(s,v,u,n,m,nthreads,chunk) private(i,j,tid)
    {
        tid = omp_get_thread_num();
        printf("Thread %d starting...\n",tid);

        #pragma omp for schedule (dynamic)
        for ( j = 0; j < n; j++ )
        {
            for ( i = 0; i < k; i++ )
            {               
                v[i  +j*m] = ( u[2*i+j*m] + u[2*i+1+j*m] ) / s;
                v[k+i+j*m] = ( u[2*i+j*m] - u[2*i+1+j*m] ) / s;
            }
        }

    #pragma omp for schedule (dynamic)
    for ( j = 0; j < n; j++ )
    {
        for ( i = 0; i < 2 * k; i++ )
        {
            u[i+j*m] = v[i+j*m];
        }
    }
}//end parallel

clock_t end = clock();
double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
printf ( "Time for COLUMNS: %f ms\n", time_spent * 1000);

}//end while

// [...]code for rows
free ( v );

return;}

时间大概是：

Time for COLUMNS: 160.519000 ms // parallel
Time for COLUMNS: 62.842000 ms // serial

我尝试以多种不同的方式重新安排 pragma，例如使用静态调度、部分、任务等，还重新安排变量的数据范围并在并行区域内动态分配。我认为将 2 级并行化会很简单，但现在我已经苦苦挣扎了两天。寻求你们的帮助，我已经检查了这里所有相关的问题，但仍然无法继续，或者至少无法理解原因。先感谢您。（CPU 英特尔酷睿 i3-4005U CPU @ 1.70GHz × 4 线程，2 核）

更新：

1) m & n呢，估计有一天也能实现矩形图像，所以我就把它放在那里了。

2）我发现u其实是一个普通数组，里面有一个线性化矩阵，也就是逐行排列（我用的是PGM图片）。

3) memcpy 是一个更好的选择，所以现在我正在使用它。

关于主题，我尝试通过为每个块生成一个任务来将作业划分为 n 个，结果比串行代码快一点。现在我知道输入矩阵 u 处于良好的行优先顺序，2 for 似乎相应地进行，但我不确定时间：同时使用 omp_get_wtime() 和 clock() 我不不知道如何测量加速比。我用不同的图像尺寸进行了测试，从 16x16 到 4096x4096，并行版本使用 clock() 似乎更慢，使用 omp_get_wtime() 和 gettimeofday() 似乎更快。关于如何使用 OpenMP 正确处理它，或者至少如何正确测量加速比，您有什么建议吗？

while ( n/2 < k )
{
    k = k / 2;
    double start_time = omp_get_wtime();
    // clock_t begin = clock();
    #pragma omp parallel shared(s,v,u,n,m,nthreads,chunk) private(i,j,tid) firstprivate(k)
    {
        nthreads = omp_get_num_threads();

         #pragma omp single
         {
          printf("Number of threads = %d\n", nthreads);

          int chunk = n/nthreads;
          printf("Chunks size = %d\n", chunk);
          printf("Thread %d is starting the tasks.\n", omp_get_thread_num());

          int h;

          for(h=0;h<n;h = h + chunk){
          printf("FOR CYCLE i=%d\n", h);

            #pragma omp task shared(s,v,u,n,m,nthreads,chunk) private(i,j,tid) firstprivate(h,k)
            {
                tid = omp_get_thread_num();
                 printf("Thread %d starts at %d position\n", tid , h);

                for ( j = h; j < h + chunk; j++ )
                {
                    for ( i = 0; i < k; i++ )
                    {
                        v[i  +j*m] = ( u[2*i+j*m] + u[2*i+1+j*m] ) / s;
                        v[k+i+j*m] = ( u[2*i+j*m] - u[2*i+1+j*m] ) / s;
                    }
                }
            }// end task
        }//end launching for
        #pragma omp taskwait
        }//end single
        }//end parallel region

        // clock_t end = clock();
        // double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
        // printf ( "COLUMNS: %f ms\n", time_spent * 1000);

        double time = omp_get_wtime() - start_time;
        printf ( "COLUMNS: %f ms\n", time*1000);

    for ( j = 0; j < n; j++ )
    {
        for ( i = 0; i < 2 * k; i++ )
        {
            u[i+j*m] = v[i+j*m];
        }
    }
 }//end while

Answer 1

关于您的代码，我有几个问题让我深感担忧。

m & n 是维度（每个图像都是一个完美的正方形）

那为什么会有两个size参数呢？
u 是列优先顺序的输入数组

这是一个极其糟糕的主意。 C 对内存使用行优先顺序，因此列优先索引导致跨步内存访问。这对性能非常、非常不利。如果可能的话，你需要解决这个问题。

因为u和v都是线性化矩阵，那么这个

for (int j = 0; j < n; j++) {
    for (int i = 0; i < m; i++) {
        v[i + j * m] = u[i + j * m];
    }
}

可以替换为调用 memcpy。

memcpy(v, u, m * n * sizeof(double));

关于你的问题。您使用 OpenMP 的版本较慢的原因是因为您的所有线程都在做同样的事情。这没有用，会导致 false sharing 之类的坏事。您需要使用每个线程的 id（代码中的 tid）来跨线程划分数据；请记住，虚假分享是不好的。

Answer 2

问题是我使用的是 clock() 而不是 omp_get_wtime()，多亏了 Z 玻色子。

使用 OpenMP 并行化二维 Haar 小波变换的 C 代码

Parallelize C code for 2D Haar wavelet transform with OpenMP

c

parallel-processing

multithreading

openmp

haar-wavelet