parallelisierter Backtracking-Algorithmus

Google: work stealing c++ liefert auch Ergebnisse ...

*push*

Ich stelle mir das in etwa so vor: http://stackoverflow.com/questions/850866/multi-threaded-algorithm-for-solving-sudoku Leider ist dort kein Code.

Würde folgendes funktionieren:

Initialisiere WorkQueue mit der Wurzel des Suchbaumes.
Starte N Threads mit der Funktion backtracking.

void backtracking()
{
  Wenn WorkQueue leer, return;
  Sonst nimm ein Element aus der WorkQueue, 
    expandiere dort den Suchbaum und
    pushe alle möglichen Fortführungen auf die WorkQueue,
    bis auf die erste, auf diese wende Backtracking an.
}

Das "pushe alle möglichen Fortführungen auf die WorkQueue, bis auf die erste, auf diese wende Backtracking an." scheint mir noch nicht so ganz zu stimmen.

Kann man vielleicht http://www.boost.org/doc/libs/1_61_0/libs/graph_parallel/doc/html/index.html (Parallel Boost Graph Library) nutzen?

Auf http://www.boost.org/doc/libs/1_61_0/libs/graph_parallel/doc/html/tsin_depth_first_visit.html steht:

Depth-first search is inherently sequential, so parallel speedup is very poor. Regardless of the number of processors, the algorithm will not be faster than O(V); see [Tsin02] for more details.

Also macht es vielleicht gar keinen Sinn, einen Backtracking/CSP-Algorithmus zu parallelisieren? Oder unter welchen Umständen würde es Sinn machen?

volkard

dsfsdffd schrieb:

Auf http://www.boost.org/doc/libs/1_61_0/libs/graph_parallel/doc/html/tsin_depth_first_visit.html steht:

Depth-first search is inherently sequential, so parallel speedup is very poor. Regardless of the number of processors, the algorithm will not be faster than O(V); see [Tsin02] for more details.

Also macht es vielleicht gar keinen Sinn, einen Backtracking/CSP-Algorithmus zu parallelisieren? Oder unter welchen Umständen würde es Sinn machen?

Du hast doch einen Baum da liegen, durch den Du rennst, oder? Dann haste durchs Parallelisieren soviel speedup, wie Du Kerne hast (und pro HT-"Kern" nochmal 30%). Abzüglich Ebbes+Epsilon Promille für Verwaltung, wobei ε beliebig groß werden kann, wenn man für jedes Epsilon einen Thread startet. Also auch 10000 oder so. Aber das macht man ja nicht. Im Allgemeinen sind Ebbes+Epsilon vollkommen unspürbar bei Bäumen.

Ja, ich habe einen Baum (kein beliebiger Graph). Es sieht so aus, als müsste ich mir selbst etwas schreiben.

Vielleicht so:

Initialisiere WorkQueue mit der Wurzel des Suchbaumes.
Starte N Threads mit der Funktion backtracking.

void backtracking()
{
  while (WorkQueue nicht leer)
  {
    Nimm ein Element aus der WorkQueue, 
    wenn das Element ein Blatt ist: return;
    sonst: pushe alle dessen Kinder auf die WorkQueue
  }
}

Hierbei müssen die Zugriffe auf die WorkQueue durch einen Mutex geschützt werden.

Besser so:

Initialisiere WorkQueue mit der Wurzel des Suchbaumes.
finished = false;
Starte N Threads mit der Funktion backtracking.

void backtracking()
{
  while (!finished)
  {
    Nimm ein Element aus der WorkQueue, 
    wenn das Element ein Blatt ist: finished = true; return;
    sonst: pushe alle dessen Kinder auf die WorkQueue
  }
}

Hierbei müssen die Zugriffe auf die WorkQueue durch einen Mutex geschützt werden.