Mehrere Ebenen der Parallelität mit OpenMP - Möglich? Clever? Praktisch?

Question

Ich arbeite zur Zeit an einer C++ - Bibliothek für spärliche Matrix/Mathe/iterative Solver für ein Simulationswerkzeug, das ich verwalte. Ich hätte es vorgezogen, ein existierendes Paket zu verwenden, jedoch wurde nach umfangreichen Untersuchungen keine gefunden, die für unseren Simulator geeignet wäre (wir haben uns flens, it ++, PetSC, eigen und einige andere angesehen). Die gute Nachricht ist, dass meine Solver und spärlichen Matrixstrukturen jetzt sehr effizient und robust sind. Die schlechte Nachricht ist, dass ich jetzt die Parallelisierung mit OpenMP untersuche und die Lernkurve ein wenig steil ist.

Die von uns gelöste Domäne kann in Subdomänen aufgeteilt werden, die in einem Blockdiagonalformat zusammenkommen. Unser Speicherschema sieht also aus wie ein Array kleinerer quadratischer Matrizen (Blöcke []) mit jeweils einem für die Subdomäne geeigneten Format (z. B. komprimierte Zeilenspeicherung: CRS, komprimierte diagonale Speicherung: CDS, dicht, usw.). und eine Hintergrundmatrix (die derzeit CRS verwendet), die die Konnektivität zwischen Subdomänen berücksichtigt.

Der "Hotspot" in den meisten (alle?) Iterativen Solvern ist die Matrix-Vektor-Multiplikation, und dies gilt für meine Bibliothek. Daher habe ich mich auf die Optimierung meiner MxV-Routinen konzentriert. Für die Blockdiagonalstruktur, die Pseudo-Code für M * x = b wäre wie folgt:

b=background_matrix*x 
start_index = 1; 
end_index = 0; 
for(i=1:number of blocks) { 
    end_index=start_index+blocks[i].numRows(); 
    b.range(start_index, end_index) += blocks[i] * x.range(start_index, end_index); 
    start_index = end_index+1; 
} 

wo background_matrix ist der Hintergrund (CRS) Matrix, die Blöcke ist die Anordnung von Subdomäne Matrizen und .Range gibt den Teil des Vektors von einem Startindex zu einem Endindex zurück.

Offensichtlich kann (und wurde) die Schleife parallelisiert werden, da die Operationen unabhängig von anderen Iterationen der Schleife sind (die Bereiche sind nicht überlappend). Da wir in einem typischen System 10-15 Blöcke haben, macht 4+ Threads tatsächlich einen signifikanten Unterschied.

Die andere Stelle, an der die Parallelisierung als eine gute Option angesehen wurde, ist die MxV-Operation für jedes Subdomänenspeicherschema (Aufrufe in den Zeilen 1 und 6 im obigen Code). Es gibt viel da draußen bei der Parallelisierung von CRS-, CDS- und dichte Matrix-MxV-Operationen. In der Regel wird ein schöner Boost mit 2 Threads erzielt, mit stark abnehmenden Renditen, wenn mehr Threads hinzugefügt werden.

Ich stelle mir ein Schema vor, bei dem 4 Threads in der Blockschleife für den obigen Code verwendet würden und jeder dieser Threads 2 Threads für die Subdomänen-Lösungen verwenden würde. Ich bin mir jedoch nicht sicher, wie man mit OpenMP den Pool von Threads verwalten kann - ist es möglich, die Anzahl der Threads in einem openmp for force zu begrenzen? Ist diese mehrstufige Parallelität in der Praxis sinnvoll? Alle anderen Gedanken auf, was ich hier vorgeschlagen würde geschätzt (und vielen Dank für das Lesen den ganzen Weg bis zum Ende!)

Answer 1

Bitte beachten Sie, dass alles, was ich beschreibe, implementierungsabhängig ist.

Ist es möglich, die Anzahl der Threads in einem Openmp for Loop zu begrenzen?

Ja. Es gibt verschiedene Möglichkeiten, dies zu tun. Setzen Sie omp_set_nested(1); und verwenden Sie so etwas wie #pragma omp parallel for num_threads(4) oder ähnliche in Ihrer äußeren Schleife und #pragma omp parallel for num_threads(2) Direktive in Ihrer inneren Schleife.Dies sollte Ihnen 8 Threads geben (abhängig von der Implementierung müssen Sie möglicherweise auch OMP_THREAD_LIMIT setzen, wenn Sie weniger als 8 Kerne haben)

Alternativ können Sie Ihre Schleifen manuell ausrollen, z. so etwas wie

#pragma omp parallel sections { 
    #pragma omp section 
    do your stuff for the first part, nest parallel region again 
    #pragma omp section 
    and so on for the other parts 
} 

verwenden, können Sie das gleiche tun manchmal effizienter in OpenMP 3.0 mit #pragma omp task.

Oder Sie starten 8 Threads und erhalten die aktuelle Thread-Nummer innerhalb des parallelen Abschnitts und planen manuell basierend auf der Thread-Nummer.

Schließlich, wenn Sie eine perfekt geschachtelte Schleife haben (eine Schleife ist perfekt geschachtelt, wenn die tatsächliche Zuweisung nur in der innersten Schleife passiert), können Sie alles in eine einzige Schleife umschreiben. Grundsätzlich packen Sie Ihre beiden Iteratoren i und j in einen großen Iterator (i, j). Beachten Sie, dass dies die Lokalität reduzieren und somit die Leistung verringern kann.

Ist diese mehrstufige Parallelität etwas, was in der Praxis Sinn macht?

Es kommt darauf an, und Sie müssen es selbst herausfinden. Im Allgemeinen macht Multilevel-Parallelität Ihr Problem besser skalierbar. Die Planung kann jedoch komplizierter sein. Diese paper könnte interessant sein.

Zum manuellen Festlegen der Anzahl der Threads: Der Hauptvorteil der Anzahl der Threads besteht darin, dass Sie bei der Planung spezifische Kenntnisse über Ihr Problem verwenden können. Dadurch können Sie den Overhead reduzieren und eine höhere Lokalität des ausgeführten Codes erreichen und somit mehr Cache-Treffer und weniger Hauptspeicher-E/A.

Der Hauptnachteil der manuellen Festlegung der Anzahl von Threads in verschachtelter Parallelität ist, dass Threads in der innersten Schleife untätig auf die implizite Barriere warten können, während zusätzliche Arbeit getan werden konnte (example). Grobkörnige Parallelität skaliert auch nicht gut. Wenn also Ihre äußere Schleife innerhalb der Schleife eine sehr unterschiedliche Laufzeit hat, möchten Sie flexibler planen als einfach in 4 Threads aufzuteilen.

Alle anderen Gedanken

Haben Sie aber über die mxv mit SIMD tun. Abhängig von der Architektur kann dies zu einer Beschleunigung von 2-4 führen. Ich habe diese presentation für Sie schnell gegoogelt.

Für MxV, loop tiling, register and cache blocking und verwandte Techniken können Datenlokalität erhöhen und andere Probleme reduzieren, z. falsches Teilen Diese book, Kapitel 11 (Sie können es in der Vorschau anzeigen), könnte Ihnen einige zusätzliche Ideen zur Umstrukturierung des Datenzugriffs geben.

Answer 2

Warum nicht fragen die Experten über bei OpenMP.org

registrieren und melden Sie sich an unter: http://openmp.org/forum/viewforum.php?f=3