Lock-free Parallel Dynamic Programming


Autoria(s): Stivala, A.; Stuckey, P.J.; García de la Banda, M.; Hermenegildo, Manuel V.; Wirth, A.
Data(s)

2010

Resumo

We show a method for parallelizing top down dynamic programs in a straightforward way by a careful choice of a lock-free shared hash table implementation and randomization of the order in which the dynamic program computes its subproblems. This generic approach is applied to dynamic programs for knapsack, shortest paths, and RNA structure alignment, as well as to a state-of-the-art solution for minimizing the máximum number of open stacks. Experimental results are provided on three different modern multicore architectures which show that this parallelization is effective and reasonably scalable. In particular, we obtain over 10 times speedup for 32 threads on the open stacks problem.

Formato

application/pdf

Identificador

http://oa.upm.es/11119/

Idioma(s)

eng

Publicador

Facultad de Informática (UPM)

Relação

http://oa.upm.es/11119/1/HERME_A_2010-1.pdf

http://www.sciencedirect.com/science/article/pii/S074373151000011

Direitos

http://creativecommons.org/licenses/by-nc-nd/3.0/es/

info:eu-repo/semantics/openAccess

Fonte

Journal of parallel and distributed computing, ISSN 0743-7315, 2010, Vol. 70, No. 8

Palavras-Chave #Informática
Tipo

info:eu-repo/semantics/article

Artículo

PeerReviewed