Constraint Satisfaction Problem/Backtracking multithreaded?
-
Du brauchst keine Threads beenden und neue starten. Mach einen Threadpool mit einer konstanten Anzahl an Threads (Gleich viele wie CPU-Cores) und dann schmeiss einfach die Tasks rein.
Die Intel TBB Bibliothek dürfte sowas schon fertig implementiert haben: http://threadingbuildingblocks.org/
-
rapso schrieb:
bei sowas eignet sich 'task stealing'
du hast einen thread pool und der bekommt einen task (also root node), ein thread wird sich den task schnappen und bei z.b. einem binaerbaum ein element auf einen stack legen und das zweite weiter abarbeiten.
da die task queue vom thread pool leer ist, schauen die threads im pool bei den nachbarn ob die was in der lokalen queue aka stack haben. falls ja, schnappen die sich das unterste element vom stack und arbeiten genau so weiter.auf diese weise 'klauen' die threads immer den potentiell teuersten task und balanzieren sich zudem aus. 'klauen' kann in dem fall ein simpler atomic-swap sein, bei dem man 0 eintraegt. wenn der eigentliche thread per atomic swap 'popt', braucht man den stack nicht grossartig kopieren und auch kein mutex etc.
Gibt es dafür Beispielcode im Internet?
Die Intel TBB Bibliothek dürfte sowas schon fertig implementiert haben: http://threadingbuildingblocks.org
Auch hier: Gibt es Beispielcode?
-
-
csp schrieb:
Dort ist leider kein Beispiel für task stealing ...
-
Das macht TBB automatisch.
-
Ich will aber mal größeren Beispielcode sehen.
-
--> Doc
-
-
csp schrieb:
rapso schrieb:
bei sowas eignet sich 'task stealing'
du hast einen thread pool und der bekommt einen task (also root node), ein thread wird sich den task schnappen und bei z.b. einem binaerbaum ein element auf einen stack legen und das zweite weiter abarbeiten.
da die task queue vom thread pool leer ist, schauen die threads im pool bei den nachbarn ob die was in der lokalen queue aka stack haben. falls ja, schnappen die sich das unterste element vom stack und arbeiten genau so weiter.auf diese weise 'klauen' die threads immer den potentiell teuersten task und balanzieren sich zudem aus. 'klauen' kann in dem fall ein simpler atomic-swap sein, bei dem man 0 eintraegt. wenn der eigentliche thread per atomic swap 'popt', braucht man den stack nicht grossartig kopieren und auch kein mutex etc.
Gibt es dafür Beispielcode im Internet?
TBB macht das nicht ganz so AFAIK, da es ja nicht weiss dass dein code damit klar kommt dass der stack am 'falschen' ende abgeschnitten wird.
task stealing mit beispiel code wird hier erklaert: http://software.intel.com/en-us/articles/do-it-yourself-game-task-scheduling
(aber vorsicht, der code war ein wenig buggy als ich es das letzte mal sah, also nur als 'beispiel' nehmen, nicht als copy&paste oder lib
).
-
csp schrieb:
Der Link ist leider nicht mehr aktuell ...