Parallel Dynamische Programmierung

Question

Gibt es gute Papiere diskutieren, wie ein dynamisches Programm zu nehmen und es parallelisieren?

Answer 1

IIRC, was Sie in der Regel mit dem dynamischen Programmierung zu tun ist rekursiv ein Problem in Teilprobleme zu unterteilen, und montiert optimale Lösungen optimal Teillösungen. Was es effektiv macht, ist, dass alle optimalen Teillösungen in einen Cache eingebaut sind, so müssen sie nicht neu berechnet werden.

Wenn das Problem mehr Möglichkeiten, unterteilt werden kann, können Sie den Solver für jede Teillösung Gabel. Wenn jeder (Teil-) Problem mittelt 1 + epsilon (für epsilon interessanter mehr als null) möglich Teillösungen, dann werden Sie eine Menge von Parallelität auf diese Weise erhalten. Sie werden wahrscheinlich brauchen Schlösser an den Cache-Einträge aus den einzelnen Lösungen zu schützen mehr als einmal gebaut.

Sie müssen eine Sprache, in der Sie Unteraufgaben billiger als die Arbeit gabeln können, sich zu lösen, und die gerne viel gegabelt Aufgaben auf einmal haben. Die typischen parallelen Angebote in den meisten Sprachen tun dies schlecht; Sie nicht viel gegabelt Aufgaben in Systemen haben können, die „das große Stapel-Modell“ (siehe Wie funktioniert eine stackless Spracharbeit? ).

Wir führten unsere parallele Programmierung Langauge, PARLANSE, eine Sprache zu erhalten, die die richtigen Eigenschaften hat.

Answer 2

Wir veröffentlichte vor kurzem ein Papier zeigt, wie jede d.p. parallelisieren auf einem gemeinsam genutzten Speicher mehradrige Computer mittels einer gemeinsamen Sperre freien Hashtabelle:

Stivala, A. und Stuckey, P. J. und Garcia de la Banda, M. und Hermenegildo, M. und Wirth, A. 2010 "Lock-frei parallel dynamische Programmierung" J. Parallel Distrib. Comput. 70: 839-848 doi: 10.1016 / j.jpdc.2010.01.004

http://dx.doi.org/10.1016/j.jpdc. 2010.01.004

Im Wesentlichen beginnen Sie mehrere Threads, die alle den gleichen Code des d.p. auf dem Wert laufenden Anfang Sie wollen berechnen, ist es top-down (rekursiv) Berechnen und memoizing in einer gemeinsamen Lock-Free-Hash-Tabelle, aber die Reihenfolge Randomisierung, in dem Subprobleme berechnet werden, so dass die Fäden auseinander gehen, in denen sie Subprobleme berechnen.

Im Hinblick auf die Umsetzung, wir C und pthreads auf UNIX-artigen Systemen nur verwendet, alles, was Sie brauchen, ist in der Lage sein, gemeinsam genutzten Speicher zu haben, und compareAndSwap (CAS) für schleusenfreien Synchronisation zwischen Threads.

Da dieses Papier in einer Elsevier-Zeitschrift veröffentlicht wurde, werden Sie die oben durch eine Universitätsbibliothek oder ähnliches mit einem Abonnement für sie zugreifen müssen. Sie könnten allerdings ein Pre-Print-Exemplar über Prof. Stuckeys Webseite erhalten können.