parallel processing - Programación Dinámica Paralela

parallel-processing dynamic-programming

Question

¿Hay algunos buenos documentos que discutan cómo tomar un programa dinámico y ponerlo en paralelo?

Answer 1

Recientemente publicamos un documento que muestra cómo paralelizar cualquier dp en una computadora multinúcleo de memoria compartida por medio de una tabla hash libre de bloque compartido:

Stivala, A. y Stuckey, PJ y García de la Banda, M. y Hermenegildo, M. y Wirth, A. 2010 "Programación dinámica paralela sin bloqueo" 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

Esencialmente, comienzas múltiples hilos, todos ejecutan el mismo código comenzando por el valor del dp que deseas calcular, informándolo de arriba hacia abajo (recursivamente) y memorizando en una tabla hash compartida sin bloqueos, pero aleatorizando el orden en el que los subproblemas se calculan para que los subprocesos diverjan en qué subproblemas calculan.

En términos de implementación, solo usamos C y pthreads en sistemas de tipo UNIX, todo lo que necesita es poder tener memoria compartida, y CompareAndSwap (CAS) para una sincronización sin bloqueos entre hilos.

Debido a que este documento fue publicado en una revista Elsevier, tendrá que acceder al anterior a través de una biblioteca de la Universidad o similar con una suscripción a la misma. Sin embargo, es posible que pueda obtener una copia de preimpresión a través de la página web del Prof. Stuckey.

Answer 2

IIRC, lo que normalmente hace con la programación dinámica es dividir recursivamente un problema en subproblemas, y ensamblar soluciones óptimas a partir de subsoluciones óptimas. Lo que lo hace efectivo es que todas las subsoluciones óptimas están integradas en un caché, por lo que no es necesario volver a calcularlas.

Si el problema se puede dividir de varias maneras, puede bifurcar el solucionador para cada subsolución. Si cada (sub) problema promedia 1 + épsilon (para épsilon interesantemente más que cero) subsoluciones posibles, entonces obtendrás mucho paralelismo de esta manera. Probablemente necesite bloqueos en las entradas de caché para evitar que las soluciones individuales se construyan más de una vez.

Necesita un lenguaje en el que pueda dividir las subtareas de forma más económica que el trabajo para resolverlas, y que está feliz de tener muchas tareas bifurcadas a la vez. Las ofertas paralelas típicas en la mayoría de los idiomas hacen esto mal; no puede tener muchas tareas bifurcadas en sistemas que usan "el modelo de la gran pila" (consulte ¿Cómo funciona un lenguaje sin pilas? ).

Implementamos nuestro lenguaje de programación paralela, PARLANSE, para obtener un lenguaje que tuviera las propiedades correctas.