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

Question

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

Answer 1

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

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

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

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

Answer 2

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

Stivala, A. and Stuckey, PJ and Garcia de la Banda, M. and Hermenegildo, M. and Wirth, A. 2010 «Lock -бесплатное параллельное динамическое программирование "J. Parallel Distrib. Вычи. 70: 839-848 DOI: 10.1016/j.jpdc.2010.01.004

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

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

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

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