c - 使用 OpenMP 并行化 2D Haar 小波变换的 C 代码

Question

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

这是生成的图像 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

我尝试以多种不同的方式重新排列编译指示，例如使用静态计划、部分、任务等，还重新排列变量的数据范围并在并行区域内动态分配。我以为并行化 2 级会很简单，但现在我已经挣扎了两天了。寻求你们的帮助，我已经检查了这里几乎所有相关的问题，但仍然无法继续，或者至少无法理解原因。先感谢您。(CPU Intel Core i3-4005U CPU @ 1.70GHz × 4线程，2核)

更新:

1)m & n 怎么样，它应该有一天也实现矩形图像，所以我就把它留在那里。

2)我发现 u 实际上是一个普通数组，内部有一个线性化矩阵，即逐行(我使用 PGM 图像)。

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

关于主要主题，我尝试通过为每个 block 生成一个任务来将作业划分为 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

我有几个与您的代码密切相关的问题。

1. m 和 n 是尺寸(每个图像都是完美的正方形)

   那为什么有两个尺寸参数呢？

2. u 是按列优先顺序排列的输入数组

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

3. 因为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)来跨线程划分数据；请记住，虚假分享是不好的。