C-Code für 2D-Haar-Wavelet-Transformation mit OpenMP parallelisieren

Question

Dies ist meine erste Frage. Ich versuche, mit OpenMP eine 2D-Haar-Transformationsfunktion in C zu parallelisieren. Ich erhielt es here und entsprechend geändert. Das Programm nimmt ein schwarzes & weißes Bild, setzt es in eine Matrix und berechnet eine Ebene der Haar-Wavelet-Transformation. Am Ende normalisiert es die Werte und schreibt das transformierte Bild auf die Festplatte.

Dies ist ein resultierendes Bild 1 level of HDT

Mein Problem ist, dass die parallelisierte Version läuft ziemlich langsamer als die Serien ein. Denn jetzt lege ich hier einen Ausschnitt aus dem Hauptteil I parallelisieren wollen (später ich alle umliegenden Code setzen können):

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

Die Zeiten mehr oder weniger sind:

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

I Ich habe versucht, die Pragmas auf viele verschiedene Arten neu anzuordnen, z. B. mit einem statischen Zeitplan, mit Abschnitten, einer Aufgabe usw., außerdem ordnen Sie die Datenbereiche der Variablen neu an und ordnen dynamisch innerhalb von parallelen Bereichen zu. Ich dachte, es wäre einfach, eine 2-Ebene für zu parallelisieren, aber jetzt sind es zwei Tage, die ich kämpfe. Auf der Suche nach Ihrer Hilfe habe ich mich bereits in der Nähe aller verwandten Fragen erkundigt, kann aber immer noch nicht weitermachen oder zumindest die Gründe verstehen. Vielen Dank im Voraus. (CPU Intel Core i3-4005U CPU @ 1.70GHz × 4 Threads, 2 Kerne)

UPDATE:

1) Was ist m & n, es soll eines Tages auch rectangled Bilder umzusetzen, also habe ich es einfach dort gelassen.

2) Ich fand heraus, dass Sie eigentlich ein normales Array mit einer linearisierten Matrix im Inneren ist, das ist Zeile für Zeile (ich verwende PGM-Bilder).

3) Das Memcpy ist eine bessere Option, also verwende ich es jetzt.

Was ist mit dem Hauptthema, ich habe versucht, den Job über n zu teilen, indem Sie eine Aufgabe für jeden Brocken und das Ergebnis ist ein wenig schneller als der Seriencode. Nun weiß ich, dass die Eingangsmatrix u in einer guten Reihenfolge ist, die 2 Fors scheinen entsprechend zu verfahren, aber ich bin mir nicht sicher über die Timings: mit omp_get_wtime() und clock() weiß ich nicht wie um die Beschleunigung zu messen. Ich habe Tests mit verschiedenen Bildgrößen von 16x16 bis 4096x4096 gemacht, und die parallele Version scheint langsamer mit clock() und schneller mit omp_get_wtime() und gettimeofday() zu sein. Haben Sie einige Vorschläge, wie Sie mit OpenMP richtig umgehen oder zumindest die Beschleunigung richtig messen?

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

Das Problem war, dass ich clock() anstelle von omp_get_wtime(), dank Z Boson.

Answer 2

Ich habe ein paar Fragen, die mich sehr um Ihren Code kümmern.

1. m & n die dimentions sind (jedes Bild ist ein perfektes Quadrat)

   Warum gibt es zwei Größenparameter?

2. u ist der Eingangs-Array in Spalte-Großauftrag

   Dies ist eine unglaublich schlechte Idee. C verwendet eine Reihen-Hauptordnung für den Speicher, so dass die Indexierung der Spalten zu einem schrittweisen Speicherzugriff führt. Dies ist sehr, sehr schlecht für die Leistung. Wenn es möglich ist, müssen Sie das beheben.

3. Da sowohl u und v sind linearisierter Matrizen, dann ist diese

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

   kann mit einem Aufruf an memcpy ersetzt werden.

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

---

On zu Ihrem Problem. Der Grund dafür, dass Ihre Version mit OpenMP langsamer ist, liegt darin, dass alle Ihre Threads dasselbe tun. Dies ist nicht sinnvoll und führt zu schlechten Dingen wie false sharing. Sie müssen die ID jedes Threads (tid in Ihrem Code) verwenden, um die Daten über die Threads zu partitionieren. Denken Sie daran, dass falsches Teilen schlecht ist.