Programmazione dinamica parallela

Question

Esistono buoni documenti che discutono su come prendere un programma dinamico e parallelizzarlo?

Answer 1

IIRC, ciò che si fa in genere con la programmazione dinamica consiste nel dividere in modo ricorsivo un problema in sottoproblemi e assemblare soluzioni ottimali da sub-ottimali. Ciò che lo rende efficace è che tutte le sottoluzioni ottimali sono incorporate in una cache, quindi non devono essere ricalcolate.

Se il problema può essere suddiviso in diversi modi, è possibile eseguire il fork del risolutore per ogni risoluzione. Se ogni (sotto) problema fa una media di 1 + epsilon (per epsilon interessante più di zero) possibili sottoluzioni, allora otterrai molto parallelismo in questo modo. Probabilmente avrai bisogno di blocchi sulle voci della cache per proteggere le singole soluzioni da essere costruite più di una volta.

È necessario un linguaggio in cui sia possibile eseguire il fork di attività secondarie in modo più economico rispetto al lavoro per risolverli e che è felice di avere molte attività a forcella contemporaneamente. Le offerte parallele tipiche nella maggior parte delle lingue lo fanno male; non è possibile avere molte attività biforcate in sistemi che utilizzano "il modello di grande stack" (vedere How does a stackless language work?).

Abbiamo implementato il nostro linguaggio di programmazione parallelo, PARLANSE, per ottenere un linguaggio con le giuste proprietà.

Answer 2

Recentemente abbiamo pubblicato un documento che mostra come parallelizzare qualsiasi d.p. su un computer multicore memoria condivisa per mezzo di un free-blocco di tabella hash comune:

Stivala, A. e Stuckey, PJ e Garcia de la Banda, M. Hermenegildo, M. Wirth, A. 2010 "Blocco - programmazione dinamica parallela libera "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

In sostanza, si avvia più thread, il tutto in esecuzione lo stesso codice a partire dal valore della d.p. si desidera calcolare, calcolandolo dall'alto verso il basso (in modo ricorsivo) e memoizing in una tabella hash senza blocco condivisa, ma randomizzando l'ordine in cui i sottoproblemi vengono calcolati in modo che i thread divergano in quali sottoproblemi vengono calcolati.

In termini di implementazione, abbiamo appena usato C e pthreads su sistemi di tipo UNIX, tutto ciò che serve è poter disporre di memoria condivisa e di CompareAndSwap (CAS) per la sincronizzazione senza blocco tra i thread.

Poiché questo documento è stato pubblicato su un giornale Elsevier, è necessario accedere a quanto sopra attraverso una biblioteca universitaria o simili con un abbonamento ad esso. Potresti essere in grado di ottenere una copia pre-stampa tramite la pagina web del Prof. Stuckey.