Параллельное динамическое программирование
Есть ли хорошие статьи, обсуждающие, как взять динамическую программу и распараллелить ее?
2 ответа
IIRC, что вы обычно делаете с динамическим программированием, это рекурсивное разделение проблемы на подзадачи и сбор оптимальных решений из оптимальных решений. Что делает его эффективным, так это то, что все оптимальные подрешения встроены в кеш, поэтому их не нужно пересчитывать.
Если проблему можно разделить несколькими способами, вы можете разветвлять решатель для каждой подзадачи. Если каждая (под) задача имеет в среднем 1+ эпсилон (для эпсилона, что интересно, больше нуля) возможных подрешений, то таким образом вы получите много параллелизма. Вероятно, вам понадобятся блокировки записей кэша, чтобы защитить отдельные решения от создания более одного раза.
Вам нужен язык, на котором вы можете раскошелиться на подзадачи дешевле, чем работа по их решению, и который рад иметь множество разветвленных задач одновременно. Типичные параллельные предложения в большинстве языков делают это плохо; Вы не можете иметь много разветвленных задач в системах, использующих "модель большого стека" (см. Как работает язык без стеков?).
Мы реализовали наш язык параллельного программирования, PARLANSE, чтобы получить язык, который обладал правильными свойствами.
Недавно мы опубликовали статью, показывающую, как распараллелить любой dp на многоядерном компьютере с общей памятью с помощью общей хэш-таблицы без блокировки:
Стивала, А. и Штуки, П.Дж. и Гарсиа де ла Банда, М. и Херменегильдо, М. и Вирт, А. 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
По сути, вы запускаете несколько потоков, каждый из которых выполняет один и тот же код, начиная со значения dp, которое вы хотите вычислить, вычисляя его сверху вниз (рекурсивно) и запоминая в общей хэш-таблице без блокировки, но рандомизируя порядок, в котором подзадачи вычисляются так, что потоки расходятся, в каких подзадачах они вычисляются.
С точки зрения реализации, мы просто использовали C и pthreads в системах типа UNIX, все, что вам нужно, это иметь возможность иметь общую память и CompareAndSwap (CAS) для синхронизации без блокировок между потоками.
Поскольку этот документ был опубликован в журнале Elsevier, вам необходимо получить доступ к вышеупомянутому через библиотеку университета или аналогичную с подпиской на него. Вы можете получить препринтную копию через веб-страницу профессора Штуки.
Были некоторые работы, связанные с реализацией алгоритмов динамического программирования на графических процессорах. Например:
Динамическое программирование с помощью CUDA
Оптимизированное для графического процессора динамическое программирование
Реализация динамического программирования на графическом процессоре для оптимальной триангуляции многоугольника