OpenMPで2D Haarウェーブレット変換のCコードを並列化

Question

これは私の最初の質問です。私はopenMPとCで2d haar transform関数を並列化しようとしています。私はそれをhereとそれに応じて変更しました。 プログラムは黒色の&白画像を取り、それをマトリックスに入れ、1レベルのハールウェーブレット変換を計算します。最後に、値を正規化し、変換されたイメージをディスクに書き込みます。

これは1 level of HDT

私の問題は、並列化されたバージョンは、シリアルよりもかなり遅く走るということです結果の画像です。 今の私はここで私は（私はすべての周辺のコードを置くことができ、後に）並列化したい主要部分の抜粋添付：私は

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

：タイミングが多かれ少なかれあり

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;} 

を静的スケジュール、セクション、タスクなどを使用してさまざまな方法でプラグマを再配置しようとしました。変数のデータスコープを再配置し、内部並列領域を動的に割り当てます。 2レベルを並列化するのは簡単だと思っていましたが、今は苦労している2日間です。あなたの助けを求める人を探して、私はすでにここですべての関連する質問の近くでチェックアウトしたが、まだ進まない、または少なくとも、理由を理解する。前もって感謝します。 （CPUインテルCore i3-4005UのCPUの@の1.70GHz×4スレッド、2つのコア）

UPDATE：メートル&のnについて、一日もrectangled画像を実現することになって何

1）、私はただそれをそこに残しました。

2）実際には、uは実際に行内に線形化された行列（PGMイメージを使用します）を持つ通常の配列であることが分かりました。

3）memcpyはより良いオプションですので、今は使用しています。

主なトピックは何ですか、私は各チャンクに対してタスクを生成することでn個のジョブを分割しようとしましたが、その結果はシリアルコードよりも少し速いです。 私は入力行列uが良好な行優先順序であることを知っていますが、2つのforsはそれに応じて進んでいるようですが、タイミングについてはわかりません：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

問題は、私がomp_get_wtime（）の代わりにclock（）を使用していたことです。これはZ bosonのおかげです。

Answer 2

私はあなたのコードについて深く懸念しています。

1. メートル& N dimentions（すべての画像が完全正方形）

   は、なぜ2つのサイズパラメータが存在していますか？

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）をコード内で使用する必要があります。誤った共有は悪いことを覚えておいてください。