Noch einmal bin ich fest, wenn ich openMP in C ++ benutze. Diesmal versuche ich einen parallelen Quicksort zu implementieren.
Code:
%Vor%Algorithmus:
Um openMP für eine rekursive Funktion zu verwenden, verwendete ich einen Stapel, um die nächsten Intervalle zu verfolgen, in denen die qs-Funktion laufen sollte. Ich füge das 1. Intervall [0, Größe] manuell hinzu und lasse dann die Fäden funktionieren, wenn ein neues Intervall im Stapel hinzugefügt wird.
Das Problem:
Das Programm endet zu früh und sortiert das Array nicht nach dem Erstellen der ersten Intervalle ([q, i - 1], [i + 1, r]), wenn Sie sich den Code ansehen Holen Sie sich die Arbeit, berücksichtigt die lokalen Variablen der Quicksort-Funktion (qs im Code) standardmäßig freigegeben, so dass sie sie durcheinander bringen und kein Intervall im Stapel hinzufügen.
Wie kompiliere ich:
%Vor%So lief ich:
./qs < in_100000 > out_100000
wobei in_100000 eine Datei ist, die in der ersten Zeile 100000 enthält, gefolgt von 100k Intergern in der nächsten durch Leerzeichen getrennten Zeile.
Ich verwende gcc 4.5.2 unter linux
Danke für Ihre Hilfe,
Dan
Ich habe deinen Code nicht wirklich ausgeführt, aber ich sehe einen sofortigen Fehler bei p , der private nicht shared sein sollte. Der parallele Aufruf von qs : qs(v, p.first, p.second); hat Rassen auf p , was zu unvorhersehbarem Verhalten führt. Die lokalen Variablen in qs sollten in Ordnung sein, da alle Threads einen eigenen Stack haben. Der Gesamtansatz ist jedoch gut. Du bist auf dem richtigen Weg.
Hier sind meine allgemeinen Kommentare für die Implementierung von parallelem Quicksort. Quicksort selbst ist peinlich parallel , was bedeutet, dass keine Synchronisation erforderlich ist. Die rekursiven Aufrufe von qs in einem partitionierten Array sind peinlich parallel.
Die Parallelität wird jedoch in einer rekursiven Form dargestellt. Wenn Sie einfach die verschachtelte -Parallelität in OpenMP verwenden, haben Sie am Ende tausend Threads in einer Sekunde. Es wird keine Beschleunigung erzielt. Also müssen Sie den rekursiven Algorithmus meistens in einen interativen Algorithmus umwandeln. Dann müssen Sie eine Art Arbeitswarteschlange implementieren. Das ist dein Ansatz. Und es ist nicht einfach.
Für Ihren Ansatz gibt es einen guten Benchmark: OmpSCR. Sie können sie unter Ссылка
herunterladen Im Benchmark gibt es mehrere Versionen von OpenMP-basierten Quicksort. Die meisten von ihnen sind Ihren ähnlich. Um die Parallelität zu erhöhen, muss jedoch der Konflikt in einer globalen Warteschlange minimiert werden (in Ihrem Code ist dies s ). Es könnte also einige Optimierungen geben, wie zum Beispiel lokale Warteschlangen. Obwohl der Algorithmus selbst rein parallel ist, kann die Implementierung Synchronisationsartefakte erfordern. Und vor allem ist es sehr schwer, Beschleunigungen zu erzielen.
Allerdings verwenden Sie die rekursive Parallelität in OpenMP immer noch auf zwei Arten: (1) Drosseln der Gesamtzahl der Threads und (2) Verwenden von OpenMP 3.0 task .
Hier ist Pseudo-Code für den ersten Ansatz (Dies basiert nur auf OmpSCR Benchmark):
%Vor% Um diesen Code auszuführen, müssen Sie omp_set_nested(1) und omp_set_num_threads(2) aufrufen. Der Code ist wirklich einfach. Wir spawnen einfach zwei Threads über die Arbeitsteilung. Wir fügen jedoch eine einfache Drosselungslogik ein, um übermäßige Threads zu vermeiden. Beachten Sie, dass meine Experimente bei diesem Ansatz ordentliche Beschleunigungen gezeigt haben.
Schließlich können Sie OpenMP 3.0's task verwenden, wobei eine Aufgabe eine logisch gleichzeitige Arbeit ist. In den obigen OpenMP-Ansätzen erzeugt jedes parallele Konstrukt zwei physische Threads. Sie können sagen, dass es eine 1: 1-Zuordnung zwischen einer Aufgabe und einem Arbeitsthread gibt. % Co_de% trennt jedoch logische Aufgaben und Worker.
Da OpenMP 3.0 noch nicht populär ist, werde ich Cilk Plus verwenden, was großartig ist, um diese Art von verschachtelten und rekursiven Parallelismen auszudrücken. In Cilk Plus ist die Parallelisierung extrem einfach:
%Vor% Ich habe diesen Code aus dem Beispielcode von Cilk Plus kopiert. Sie sehen ein einzelnes Keyword task ist alles, um Quicksort zu parallelisieren. Ich überspringe die Erklärungen von Cilk Plus und spawn keyword. Es ist jedoch leicht zu verstehen: Die zwei rekursiven Aufrufe werden als logisch gleichzeitige Aufgaben deklariert. Wann immer die Rekursion stattfindet, werden die logischen Aufgaben erstellt. Aber die Cilk Plus-Laufzeitumgebung (die einen effizienten Work-Stealing-Scheduler implementiert) wird alle Arten von schmutzigen Jobs behandeln. Es reiht die parallelen Aufgaben optimal ein und bildet die Arbeitsfäden ab.
Beachten Sie, dass das cilk_spawn von OpenMP 3.0 im Wesentlichen dem Ansatz von Cilk Plus ähnelt. Meine Experimente zeigen, dass ziemlich schöne Beschleunigungen machbar waren. Ich habe eine 3 ~ 4x Beschleunigung auf einem 8-Kern-Maschine. Und die Beschleunigung war Maßstab. Die absoluten Beschleunigungen von Cilk Plus sind größer als die von OpenMP 3.0.
Der Ansatz von Cilk Plus (und OpenMP 3.0) und Ihr Ansatz sind im Wesentlichen gleich: die Trennung von paralleler Aufgaben- und Arbeitslast-Zuweisung. Es ist jedoch sehr schwierig, effizient zu implementieren. Zum Beispiel müssen Sie die Konkurrenzsituation reduzieren und blockfreie Datenstrukturen verwenden.