parallelisierter Backtracking-Algorithmus

Hallo,

ich suche eine Implementation eines parallelisierten Backtracking-Algorithmus in C++11/14, finde aber mit google "backtracking c++ parallel" nichts passendes. Kann mir jemand etwas in die Richtung verlinken? Danke.

Google: backtracking c++ multithreaded liefert bessere Ergebnisse, aber immer noch keinen konkreten Code!

Google: threadpool c++11 liefert auch etwas ...

volkard

Reicht nicht sowas http://www.drdobbs.com/architecture-and-design/three-parallel-backtracking-designs/232300302 ? Oder muss es ein enterprise framework sein?

Ich suche etwas, das die Thread-Funktionalität von C++11 verwendet.

Oder kannst du mir ein Buch empfehlen?

TBB wäre auch OK.

Kann man vielleicht codereview.stackexchange.com/questions/7870/parallel-quicksort anpassen? Der wesentliche Unterschied ist wohl, dass beim Backtracking der Branching-Faktor größer als 2 sein kann:

tbb::parallel_invoke([&] { quick_sort_parallel(b, m); }, 
                                 [&] { quick_sort_parallel(m + 1, e); });

dsfsdffd schrieb:

TBB wäre auch OK.

Doch nicht. Ist nicht free.

Ich habe mal etwas entworfen:

#include "stdafx.h"
#include <thread>
#include <mutex>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

mutex m;

queue<thread> thread_pool;
const size_t max_thread_num = 6;

const size_t max_len = 10;
void backtracking(vector<int>& data)
{
	if (data.size() == max_len)
	{
		unique_lock<mutex> lck{ m };
		for (auto i : data)
			cout << i << ' ';
		cout << endl;
		return;
	}

	vector<int> possible_continuations;
	for (auto cont : { 0,1,2,3,4,5,6,7,8,9 })
	{
		if (cont % 5 == 0)
			possible_continuations.push_back(cont);
	}

	for (auto cont : possible_continuations)
	{
		vector<int> new_data(data);
		new_data.push_back(cont);
		if (thread_pool.size() < max_thread_num)
		{
			thread_pool.emplace(backtracking, new_data);
			thread_pool.back().join();
			thread_pool.pop();
		}
		else
		{
			backtracking(new_data);
		}
	}
}

int main()
{
	vector<int> data;
	backtracking(data);

	char c;
	cin >> c;
    return 0;
}

Crasht aber, vermutlich, weil in

thread_pool.emplace(backtracking, new_data);
			thread_pool.back().join();
			thread_pool.pop();

.back() und .pop() nicht mehr auf den emplace-ten Thread zugreifen. Man müsste einen Iterator haben, der auf diesen Thread zeigt.

Weitere Kommentare?

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.