Keine Beschleunigung für n-stufige Suche mit OpenMP

Question

Ich schreibe Code für n-stufige Suche, d. H. Aufspalten von Suchraum in n Teile. Beim Vergleich paralleler Code mit dem Code ohne OpenMP-Richtlinien, d. H. Serielle Ausführung, beobachtete ich, dass paralleler Code ist viel langsamer als serieller Code. Nachdem ich beide Programme mehrmals ausgeführt hatte, sah ich wenig Beschleunigung im Parallelcode, aber nicht jedes Mal. Dies liegt möglicherweise an der Cache-Hierarchie. Ich führe Programm auf Quad-Core-Prozessor mit 4 GB RAM.

Laut Antwort auf No speedup with OpenMP Speicher gebundene Leistung und Lastenausgleich ist nicht für kleine Probleme wie mit Array SIZE 100. Ich habe keine Synchronisation verwendet. Ich versuchte auch, Array-Größe zu 10000000 zu erhöhen, aber Ausgabe ist nicht immer schneller mit parallelem Code. Häufig schlägt der Seriencode den parallelen Code.

Nach http://pages.tacc.utexas.edu/~eijkhout/pcse/html/omp-loop.html Die implizite Barriere am Ende eines Work-Sharing-Konstrukts kann mit einer nowait Klausel abgebrochen werden. Ich habe versucht, nowait Klausel hinzuzufügen auch habe ich auch versucht, Zeitplan (dynamisch) und Zeitplan (Auto) Bezug auf https://software.intel.com/en-us/articles/openmp-loop-scheduling, aber immer noch das gleiche Problem.

Code:

#include <stdio.h> 
#include <stdlib.h> 
#include <omp.h> 

#define SIZE 100 
#define NUM_THREADS 4 

int* a; 
int num; 


void nary(int num) 
{ 
    int found = 0, low = 0, high = SIZE, step; 
    int i = 0; 
    while(!found && low <= high) 
    { 
     step = (high-low)/NUM_THREADS; 
     printf("Low :- %d\tHigh :- %d\tStep :- %d\n", low,high,step); 
     printf("\n"); 

     #pragma omp parallel for num_threads(NUM_THREADS) shared(low,high,step) 
     for (i = 0; i < NUM_THREADS; ++i) 
     { 
      printf("First element :- %d by thread :- %d\n", a[low+step*i],omp_get_thread_num()); 
      if (a[low+step*i] == num) 
      { 
       found = 1; 
      } 
     } 

     printf("\n"); 
     /* First block */ 
     if (a[low+step] > num) 
     { 
      high = low + step - 1; 
      printf("First \nLow :- %d \nHigh :- %d\n\n",low,high); 
     } 

     /* Last block */ 
     else if (a[low+step*(NUM_THREADS-1)] < num) 
     { 
      low = low + step * (NUM_THREADS-1) + 1; 
      printf("Last\nLow :- %d \nHigh :- %d\n\n",low,high); 
     } 
     /* Middle blocks */ 
     else{ 
      #pragma omp parallel for num_threads(NUM_THREADS) schedule(static) shared(low,high,step) 
      for (i = 1; i < (NUM_THREADS-1); ++i) 
      { 
       if (a[low+step*i] < num && a[low+step*(i+1)] > num) 
       { 
        low = low + step*i + 1; 
        high = low + step*(i+1) - 1; 
       } 
      } 
      printf("middle\nLow :- %d \nHigh :- %d\n\n",low,high); 
     } 
    } 
    if (found == 1) 
    { 
     printf("Element found\n"); 
    } 
    else 
    { 
     printf("Element Not found\n"); 
    } 

} 

int main() 
{ 
    int i = 0; 
    int startTime = omp_get_wtime(); 

    /* Dynamically allocate memory using malloc() */ 
    a = (int*)malloc(sizeof(int) * SIZE); 
    #pragma omp parallel for schedule(static) 
    for (i = 0; i < SIZE; ++i) 
    { 
     a[i] = i; 

    } 

    printf("Enter the element to be searched :- \n"); 
    scanf("%d", &num); 

    nary(num); 


    printf("\nExecution time :- %f\n", omp_get_wtime()-startTime); 
    return 0; 
} 

Parallele Ausführung Ausgang:

Enter the element to be searched :- 
20 
Low :- 0 High :- 100 Step :- 25 

First element :- 0 by thread :- 0 
First element :- 50 by thread :- 2 
First element :- 25 by thread :- 1 
First element :- 75 by thread :- 3 

First 
Low :- 0 
High :- 24 

Low :- 0 High :- 24 Step :- 6 

First element :- 6 by thread :- 1 
First element :- 18 by thread :- 3 
First element :- 0 by thread :- 0 
First element :- 12 by thread :- 2 

Last 
Low :- 19 
High :- 24 

Low :- 19 High :- 24 Step :- 1 

First element :- 20 by thread :- 1 
First element :- 21 by thread :- 2 
First element :- 19 by thread :- 0 
First element :- 22 by thread :- 3 

middle 
Low :- 19 
High :- 24 

Element found 

Execution time :- 26.824379 

serielle Ausführung Ausgang:

Enter the element to be searched :- 
20 
Low :- 0 High :- 100 Step :- 25 

First element :- 0 by thread :- 0 
First element :- 25 by thread :- 0 
First element :- 50 by thread :- 0 
First element :- 75 by thread :- 0 

First 
Low :- 0 
High :- 24 

Low :- 0 High :- 24 Step :- 6 

First element :- 0 by thread :- 0 
First element :- 6 by thread :- 0 
First element :- 12 by thread :- 0 
First element :- 18 by thread :- 0 

Last 
Low :- 19 
High :- 24 

Low :- 19 High :- 24 Step :- 1 

First element :- 19 by thread :- 0 
First element :- 20 by thread :- 0 
First element :- 21 by thread :- 0 
First element :- 22 by thread :- 0 

middle 
Low :- 19 
High :- 24 

Element found 

Execution time :- 4.349347 

Was kann der Grund dafür sein? Liegt das daran, dass es im Code oder in der for-Schleife innerhalb des bedingten Blocks viele bedingte Anweisungen gibt?

Answer 1

Es gibt viele kleine und große Probleme in Ihrem Ansatz.

In erster Linie ist die binäre Suche sehr schnell. Es erfordert nur log (n) Iterationen im schlimmsten Fall. Selbst für eine Billion Elemente, die durchsucht werden müssen, sind das nur 40 Iterationen! Jede Iteration ist extrem einfach und benötigt grundsätzlich nur einen einzigen Speicherzugriff. Wir sprechen also von einer Suchzeit von einigen Mikrosekunden im schlimmsten Fall für einen großen Datensatz. Das heißt natürlich, ohne das Zeug mit printf zu verschmutzen.

Auf der anderen Seite dauert das Laichen eines Threads nach someanswers etwa 10 Mikrosekunden. Selbst für eine perfekte Skalierungsimplementierung gibt es keine realistische Chance für eine Leistungsverbesserung basierend auf der Parallelisierung einer einzigen Suche.

Wenn Sie Ihren spezifischen Code betrachten, erstellen Sie zwei parallele Regionen pro Iteration. Jeder Thread hat nur eine kleine Menge an Arbeit, verglichen mit dem Overhead einer parallelen Region und einem omp for Workshare-Konstrukt (das je nach Implementierung und Betriebssystem stark variieren kann).

Ich finde die Mischung von Arity und NUM_THREADS problematisch. Ihr Aktualisierungsschritt besteht aus zwei seriellen Ausführungen und die verbleibenden NUM_THREADS-2 Intervalle werden von NUM_THREADS Threads überprüft ... So für NUM_THREADS=4, auch mit perfekter paralleler Ausführung, reduzieren Sie nur die Zeit von 4 Intervallprüfungen auf 3 Intervallprüfungen, eine 1,3-fache Beschleunigung auf dem Update-Schritt.

Weiter enthält Ihr Code eine schwere Race-Bedingungen: Modifizieren low in der zweiten parallelen Schleife ist eine sehr schlechte Idee, da andere Threads gleichzeitig ihr Intervall basierend auf low überprüfen.

Wenn Sie die Leistung der Suche in sortierten zusammenhängenden Daten praktisch verbessern möchten, dann überprüfen Sie these slides. Wenn Sie Ihre Anwendung mit OpenMP/threads beschleunigen möchten, sollten Sie dies grobkörniger angehen.