Ist diese Implementierung von gleichzeitigen Quicksort korrekt?

Question

Ich habe gleichzeitige Quicksort in C++ mit OpenMP implementiert.

#include <omp.h> 
#include <iostream> 
#include <algorithm> 
using namespace std; 

void sort(int *a, int low, int high); 
int partition(int *a, int low, int high); 

class QuickSort { 
    private: 
     int *arr; 
     int len; 

    public: 
     void init(); 
     void Sort(); 
     void Display(); 
}; 

int main() { 
    cout << "Program implementing Quicksort." << endl; 

    QuickSort a; 

    a.init(); 
    a.Sort(); 
    a.Display(); 
} 

void sort(int *a, int low, int high) { 
    if(high < low || low == high) 
     return; 
    if(high == low+1) { 
     if(a[low] > a[high]) 
      swap(a[low], a[high]); 
     return; 
    } 
    int pivotidx = partition(a, low, high); 
    /*for(int i = 0; i < 5; ++i) 
     cout << a[i] << " "; 
    cout << endl;*/ 
    cout << "Pivot element has been placed at correct position: " << pivotidx << " by thread " << omp_get_thread_num() << endl; 
    #pragma omp parallel sections 
    { 
     #pragma omp section 
     { 
      sort(a, low, pivotidx); 
     } 
     #pragma omp section 
     { 
      sort(a, pivotidx+1, high); 
     } 
    } 
} 

int partition(int *a, int low, int high) { 
    int pivot = low; 
    int pivotval = a[low]; 
    int leftpointer = low; 
    int rightpointer = high; 
    while(leftpointer < rightpointer) { 
     while(a[leftpointer] <= a[pivot] && leftpointer <= high) 
      ++leftpointer; 
     if(leftpointer > high) 
      --leftpointer; 
     while(a[rightpointer] >= a[pivot] && rightpointer >= low) 
      --rightpointer; 
     if(rightpointer < low) 
      ++rightpointer; 
     if(leftpointer < rightpointer) 
      swap(a[leftpointer], a[rightpointer]); 
    } 
    a[low] = a[rightpointer]; 
    a[rightpointer] = pivotval; 
    return rightpointer; 
} 

void QuickSort::init() { 
    cout << "Enter the number of elements in the array: "; 
    cin >> len; 

    cout << "Enter the elements of the array: "; 
    arr = new int[len]; 
    for(int i = 0; i < len; ++i) 
     cin >> arr[i]; 
} 

void QuickSort::Sort() { 
    sort(arr, 0, len-1); 
} 

void QuickSort::Display() { 
    cout << "Sorted array is: " << endl; 
    for(int i = 0; i < len; ++i) 
     cout << arr[i] << " "; 
    cout << endl; 
} 

Es ist richtig sortiert, aber ich bin mir nicht sicher, ob es wirklich auf mehreren Kernen läuft. Wie kann ich das überprüfen? Außerdem ist mein paralleler Code dem in der obersten Antwort here sehr ähnlich. Dort wird am Ende erwähnt, dass dies nicht mehr Parallelität extrahieren kann als zwei Threads: Wenn es mit mehr Threads ausgeführt wird, haben die anderen Threads keine Arbeit zu tun und setzen sich einfach im Leerlauf hin. Wieso ist es so?

Answer 1

Es ist ein subtiler Fehler in partition:

while(a[leftpointer] <= a[pivot] && leftpointer <= high) 
    ... 
    while(a[rightpointer] >= a[pivot] && rightpointer >= low) 

In beiden Fällen Sie müssen den Auftrag, diese Kontrollen ändern, sonst manchmal greifen Sie a[leftpointer] während leftpointer > high die aus gebunden sein kann. Ähnlich für den zweiten while Zustand.

Auch liegen nicht an den Leser ist leftpointer kein Zeiger, sondern ein Index! Es gibt andere schwerwiegende Stilprobleme, aber da dies nicht CodeReview ist, konzentriere ich mich auf die Parallelisierung.

Die Verwendung von Abschnitten für die Parallelität ist hier alles andere als ideal. Zum Beispiel müssen Sie verschachtelte Parallelität aktivieren, um möglicherweise mehr als zwei Threads gleichzeitig aktiv zu haben. Stattdessen sollten Sie OpenMP-Aufgaben verwenden. Nun ist das Erstellen einer Aufgabe für jeden einzelnen Aufruf von sort schlecht, weil es viele kleine Aufgaben erstellt und ein schlechtes Verhältnis von Aufwand und Arbeit aufweist. Erstellen Sie stattdessen Tasks nur für ausreichend große Datenblöcke, und stellen Sie sicher, dass kein Runtime-Overhead in der Rekursion auftritt. Denn das eine hoch entwickelte zweite rekursive Funktion ist die beste Option:

void sort_serial(int* a, int low, int high) 
{ 
    if (high < low || low == high) 
     return; 
    if (high == low + 1) 
    { 
     if (a[low] > a[high]) 
      swap(a[low], a[high]); 
     return; 
    } 
    int pivotidx = partition(a, low, high); 
    sort_serial(a, low, pivotidx); 
    sort_serial(a, pivotidx + 1, high); 
} 

void sort(int* a, int low, int high) 
{ 
    if (high < low || low == high) 
     return; 
    if (high == low + 1) 
    { 
     if (a[low] > a[high]) 
      swap(a[low], a[high]); 
     return; 
    } 
    int pivotidx = partition(a, low, high); 

    // This is an arbitrary threshold. 
    if (high - low > 1000000) 
    { 
#pragma omp task 
     { 
      sort(a, low, pivotidx); 
     } 
#pragma omp task 
     { 
      sort(a, pivotidx + 1, high); 
     } 
    } 
    else 
    { 
     sort_serial(a, low, pivotidx); 
     sort_serial(a, pivotidx + 1, high); 
    } 
} 

Um mit Aufgaben erhalten wollen, müssen Sie eine parallele Region irgendwo schaffen - und verengen sie in der Regel für einen einzelnen Thread nach unten zum Starten, z.B. so wie:

void QuickSort::Sort() 
{  
#pragma omp parallel 
    { 
#pragma omp single 
     sort(arr, 0, len - 1); 
    } 
} 

Für einen ausreichend großen Eingang, und eine gute Auswahl an einer Schwelle, wird dies ausreichend Arbeit machen, die parallel ausgeführt werden können, aber kein großen Aufwand erstellen.

Um zu überprüfen, wie dies parallel läuft, verwendet man normalerweise betriebspezifische Überwachungswerkzeuge, z.B. time unter Linux. Sie können auch ein ausgeklügeltes Performance-Analyse-Tool verwenden, das Ihnen detailliert erklären kann, wie Threads Ihre Aufgaben parallel ausführen.