OpenMP: gute Strategien für Tiefensuche

Question

Ich schreibe ein C++ - Programm, das eine Brute-Force-Suche nach geschlossenen Knight's tours durchführt. Der Code lautet here.

Ich möchte dies mit OpenMP parallelisieren. Mein Problem besteht darin, dies auf eine Weise zu tun, die ein ausreichendes Maß an Parallelität schafft. Derzeit the relevant portion meines Code wie diese

#pragma omp parallel for reduction(+:count) if (depth==4) 
    for (size_t i=0;i<g.neighbours[last].size();i++){ 
    auto n = g.neighbours[last][i]; 
    // See if n can be used to extend or complete the tour 

sieht

The if (depth==4) ist mein Versuch, um sicherzustellen, dass nicht zu viele parallelen Aufgaben erstellt werden, aber auf der anderen Seite genug erzeugt, um alle Prozessoren beschäftigt zu halten. Die Einstellung depth==2 ändert nicht die Laufzeit des Programms.

Dies scheint nicht zu funktionieren. Bei einem 3x12-Problem beträgt die CPU-Zeit auf meinem Dual-Core-Prozessor etwa 130s, während eine Single-Threaded-Version ohne OpenMP etwa 40s CPU-Zeit beansprucht.

Ich würde gerne Vorschläge, wie besser OpenMP verwenden oder Gründe, warum es für dieses Problem ungeeignet ist.

UPDATE: Dank @Zulan habe ich eine newer version mit OpenMP Aufgaben mit einer viel schnelleren sequentiellen Leistung sowie eine gute Parallelisierung.

Answer 1

Zuerst lässt einen superschnellen nehmen Blick auf, wo Ihre Anwendung seine Zeit verbringt, durch perf mit:

perf record ./knights_tour_omp 3 12 
perf report 

# Overhead Command   Shared Object  Symbol                       
# ........ ............... ................... ................................................................................................. 
# 
    53.29% knights_tour_om libc-2.19.so   [.] malloc                      
    23.16% knights_tour_om libc-2.19.so   [.] _int_free                      
    10.31% knights_tour_om libc-2.19.so   [.] _int_malloc                     
    4.78% knights_tour_om knights_tour_omp  [.] _Z13continue_tourIZ4mainEUlRKSt6vectorIiSaIiEEE_EmRK5GraphS4_RKS0_IcSaIcEEiiRT_.constprop.119 
    2.64% knights_tour_om libc-2.19.so   [.] __memmove_ssse3_back                   
    1.48% knights_tour_om libc-2.19.so   [.] malloc_consolidate                 

Sie Anwendung, es ist Zeit damit verbringt, Aufteilung und Gedächtnis zu befreien. Zwar gibt es einige Berichte, dass malloc is is not fully locked, es scheint auch nicht parallel zu sein.

Es bedarf keiner weiteren Untersuchung, um herauszufinden, dass dies durch Kopieren der Vektoren visited und path für jede Iteration verursacht wird. Zum Glück hat die DFS die schöne Eigenschaft, dass Sie nicht unbedingt brauchen, das zu tun, können Sie den Zustand wiederverwenden und wiederherstellen:

visited[n] = 1; 
path.emplace_back(n); 
count += continue_tour(g, path, visited, depth+1,remain-1, cb); 
visited[n] = 0; 
path.pop_back(); 

jedoch für die parallele Schleife, müssen Sie Arbeitskopien für jeden Thread machen , so müssen Sie einen separaten Pfad für diesen Fall mit dem ursprünglichen Verhalten erstellen.

Diese kleine Änderung senkt bereits die serielle Laufzeit von 22 s auf 2,65 s. Weiter geht es mit 2 Threads auf 2.0 s runter. Es gibt eine Beschleunigung, aber es ist nicht so gut - warum? Um das zu verdeutlichen, habe ich 4 Threads verwendet (auf einem System, das groß genug ist). Hier ist die Ausführung der Anwendung über die Zeit aufgezeichnet mit score-p, in Vampir gezeigt.

Rot ist eigentliche Arbeit, blau eine implizite Barriere ist, werden die Fäden bedeutet Leerlauf. Es scheint immer entweder 3 oder 1 aktiven Thread zu sein. Der Grund ist einfach: Die meisten Positionen auf dem Board haben entweder 4 oder 2 Nachbarn, aber einer von ihnen ist bereits besucht, so dass diese Schleifen-Iteration sofort abgeschlossen wird. Die eigentliche Arbeit liegt also entweder in 3 oder in 1 Iteration der Schleife. Das ist eine besonders schlechte Übereinstimmung für 2 Threads. Bei 3 Threads sinkt die Laufzeit auf 1.7 s

Hinweis: Allzeit mit gcc 5.3 auf einem E5-2690 @ 2.90 GHz kein Turbo. Es wurde nicht darauf geachtet, die Varianz der Laufzeiten auszugleichen.

Wenn man bedenkt, dass eine einzelne Schleife für dieses Problem eine sehr schlechte Parallelität aufweist, könnten Sie versucht sein, parallele Schleifen zu verschachteln. Ich ermutige Sie, es zu versuchen, aber ich denke nicht, dass das gut funktionieren wird. Ich denke, dass Aufgaben in diesem Kontext gut funktionieren, weil Aufgaben andere Aufgaben hervorbringen können. So können Sie jeden rekursiven Schritt als Aufgabe erstellen und der OMP-Laufzeitumgebung eine gute Planung überlassen. Aber stellen Sie sicher, dass Sie es auf einen bestimmten depth begrenzen, damit die Aufgaben nicht zu kurz werden.

Ich möchte die Wichtigkeit der Verwendung von Tools betonen: Der Versuch, Performance-Probleme ohne Performance-Analyse-Tools herauszufinden, ist wie Fehler ohne einen Debugger herauszufinden. perf ist für Linux leicht verfügbar und in seiner Grundform extrem einfach zu bedienen. Dennoch ist es sehr mächtig (obwohl fortgeschrittener Gebrauch einige Tücken haben kann).

Eine zusätzliche Bemerkung: Mit OpenMP lohnt es sich oft verschiedene Compiler auszuprobieren. Zum Beispiel mit dem (festen) Tasking-Code skaliert gcc nicht mehr als 4 Threads, während die Intel Compiler/omp-Runtime eine Beschleunigung sogar bis zu 24 Threads bietet.