Programación paralela dinámica

Question

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

Answer 1

IIRC, lo que normalmente se 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) posibles subsoluciones, entonces obtendrá 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 How does a stackless language work?).

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

Answer 2

Recientemente publicamos un documento que muestra cómo paralelizar cualquier d.p. en una computadora multinúcleo de memoria compartida mediante una tabla compartida de hash sin cerradura:

Stivala, A. y Stuckey, PJ y Garcia de la Banda, M. y Hermenegildo, M. y Wirth, A. 2010 "Bloqueo "programación dinámica paralela libre" 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, usted comienza a múltiples hilos, todos corriendo el mismo código a partir del valor de la D. P. desea calcular, calcularlo de arriba hacia abajo (recursivamente) y memorizar en una tabla hash compartida sin bloqueos, pero aleatorizando el orden en que se calculan los subproblemas 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.

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