Backtracking parallelisieren (C++11)

[Gast]

Hi,

wie kann ich am besten Backtracking parallelisieren (C++11)?

[Coda]

Entweder mehr Context oder GTFO. Troll.

[Gast]

Backtracking = Tiefensuche über einen Suchbaum.

Wenn ich einfach am Wurzelknoten die Abzweigungen über meine Threads verteile, kann es vorkommen, dass einer viel schneller fertig wird als die anderen => schlechte Resourcenausnutzung.

Wie kann ich das besser machen?

[Gast]

Siehe auch http://de.wikipedia.org/wiki/Backtracking

[Marscel]

Und du bist sicher, dass du nicht schon am theoretischen Limit bist?

[Thunderhit]

Parallelisierung bei Tiefensuche? Bei Breitensuche ja, da ists kein Problem. Aber bei Tiefensuche fällt mir kein sinnvoller Ansatz ein.

[Gast]

Keiner eine Idee? :(

[Gast_samm]

Wenn ich einfach am Wurzelknoten die Abzweigungen über meine Threads verteile, kann es vorkommen, dass einer viel schneller fertig wird als die anderen => schlechte Resourcenausnutzung.

Wie kann ich das besser machen?Wenn du je Pfad einen Thread erstellst ( :freak: ), wo kommt denn das Backtracking in's Spiel? Macht doch keinen Sinn... oder bis zu x Threads, die ausgehend vom ersten Knoten erstmal bis zur jeweils maximalen Tiefe suchen, und solange kein kein Ergebnis gemeldet wird, wird jeder Thread nach Tiefensuche weiterlaufen? Verstehe weder Ausgangslage noch Sinn der Implementatierung von Parallelisierung in einem seriellen Suchverfahren ganz ein.
Mehr Kontext, konkrete Problemstellung und Lösungsansatz, am Besten Code, wären nützlich, wenn du konkrete Hilfe erwartest.

[Gast_Psy]

Schließe mich meinen Vorrednern an und werfe noch mit rein:

Threads zu erstellen ist auch mit Aufwand verbunden. Dein Problem, bzw ein Lösungspfad, muss auch rechenintentsiv genug sein, damit sich das lohnt.
Meistens ist das gar nicht der Fall.

Ansonsten: Wo ist denn das Problem? Kenne jetzt C++ nicht so, eher Java - aber prinzipiell hat man ja immer die Möglichkeit, Threads von aussen noch irgendwie zu steuern. Threads abzubrechen wenn eine Lösung gefunden wurde ist also möglich.
Dass es unterschiedlich lange Laufzeiten gibt - ja, ist klar. Prinzipiell kann man überhaupt nicht vorhersagen, wie das OS die Zeitscheiben verteilt - man muss also sowieso mit allem rechnen.
Woran klemmt es denn nun konkret?

[Gast_Psy]

Hmm wenn du nur über die verschiedenen Laufzeiten nachdenkst, ist vll ein Thread-Pool etwas für dich.
D.h. du splittest am Wurzelknoten und steckst die Threads in einen Pool. Falls ein Thread sehr früh fertig ist können die verbleibenden im Pool schauen, ob sie eigene Teilaufgaben in die frei gewordenen Threads auslagern können.

Dadurch entfallen auch die teuren Thread-Erstellungsaufwände (abgesehen vom initialen Erstellen natürlich).

Bevor du das aber selbst implementierst: Thread-Pools sind "ein alter Hut". In Java ist das im JDK mit drin, für C++ gibts sicher auch schon fertige Bibliotheken. Mach bitte nicht den Fehler zu glauben, es selbst besser zu können. :)

[Exxtreme]

Dadurch entfallen auch die teuren Thread-Erstellungsaufwände (abgesehen vom initialen Erstellen natürlich).

Threads erstellen ist gar nicht teuer. Ich glaube, selbst ein eher betagter Rechner kann mehrere Tausend Threads pro Sekunde erstellen.

[Gast_samm]

Nützliche Angaben wären auch, falls es nicht ganz konkretisiert werden soll:

was sind die Eigenschaften des Baums: ist er balanced, gibt es eine Ordnung, enthalten Knoten Daten oder nur die Blätter

was sind die constraints des Problems?

und auch, ist anhand der Problemstellung a) ein Baum überhaupt eine gute Datenstruktur b) Backtracking überhaupt ein sinnvolles vorgehen

[Gast_Psy]

Threads erstellen ist gar nicht teuer. Ich glaube, selbst ein eher betagter Rechner kann mehrere Tausend Threads pro Sekunde erstellen.
"Teuer" muss man natürlich in Relation sehen. Ich weiß auch nicht, wie groß die Unterschiede zwischen einer nativen und einer JVM-Sprache sind.
Neben dem Erstellen müssen die Threads aber auch verwaltet werden.

Es gibt oftmals Aha-Effekte, wie groß eine Aufgabe erst sein muss, damit sich Parallelisierung überhaupt lohnt und in kürzerer Verarbeitungszeit bemerkbar macht - darauf wollte ich hinweisen. Da schadet auch mal die eine oder andere Messung nicht.