Параллельное динамическое программирование

Question

Есть ли хорошие статьи, обсуждающие, как взять динамическую программу и распараллелить ее?

Answer 1

Недавно мы опубликовали статью, показывающую, как распараллелить любой д.п. на многоядерном компьютере с общей памятью с помощью общей хэш-таблицы без блокировки:

Стивала, А. и Штуки, П. Дж. И Гарсиа де ла Банда, М. и Херменегильдо, М. и Вирт, А. 2010 "Беспараллельное параллельное динамическое программирование" J. Parallel Distrib. Вычи. 70: 839-848 дои: 10.1016 / j.jpdc.2010.01.004

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

По сути, вы запускаете несколько потоков, каждый из которых выполняет один и тот же код, начиная со значения d.p. Вы хотите вычислить, вычислить его сверху вниз (рекурсивно) и запоминать в общей хэш-таблице без блокировок, но рандомизировать порядок, в котором вычисляются подзадачи, так что потоки расходятся, в каких подзадачах они вычисляются.

С точки зрения реализации, мы только что использовали C и pthreads в системах типа UNIX, все, что вам нужно, это иметь возможность иметь общую память и CompareAndSwap (CAS) для синхронизации без блокировок между потоками.

Поскольку этот документ был опубликован в журнале Elsevier, вам необходимо получить доступ к вышеперечисленному через университетскую библиотеку или аналогичную систему с подпиской на нее. Вы можете получить препринтную копию через веб-страницу профессора Штуки.

Answer 2

IIRC, что вы обычно делаете с динамическим программированием, это рекурсивное разделение проблемы на подзадачи и сбор оптимальных решений из оптимальных подзадач. Что делает его эффективным, так это то, что все оптимальные подрешения встроены в кэш, поэтому их не нужно пересчитывать.

Если проблему можно разделить несколькими способами, вы можете разветвлять решатель для каждого поднабора. Если каждая (под) задача имеет в среднем 1 + эпсилон (для эпсилона, что интересно, больше нуля) возможных подрешений, тогда вы получите много параллелизма таким образом. Вероятно, вам понадобятся блокировки записей кэша, чтобы защитить отдельные решения от создания более одного раза.

Вам нужен язык, на котором вы можете раскошелиться на подзадачи дешевле, чем работа по их решению, и который рад иметь сразу много разветвленных задач. Типичные параллельные предложения в большинстве языков делают это плохо; Вы не можете иметь много разветвленных задач в системах, использующих «модель большого стека» (см. Как работает язык без стеков? ).

Мы внедрили наш язык параллельного программирования, PARLANSE, чтобы получить язык с правильными свойствами.