Lock-free Parallel Dynamic Programming

Stivala, A. and Stuckey, P.J. and García de la Banda, M. and Hermenegildo, Manuel V. and Wirth, A. (2010). Lock-free Parallel Dynamic Programming. "Journal of parallel and distributed computing", v. 70 (n. 8); pp. 839-848. ISSN 0743-7315.


Title: Lock-free Parallel Dynamic Programming
  • Stivala, A.
  • Stuckey, P.J.
  • García de la Banda, M.
  • Hermenegildo, Manuel V.
  • Wirth, A.
Item Type: Article
Título de Revista/Publicación: Journal of parallel and distributed computing
Date: 2010
Volume: 70
Freetext Keywords: Dynamic programming, Lock-free hash tables, Constraint, programming, Multicores, Parallelism
Faculty: Facultad de Informática (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (1MB) | Preview


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.

More information

Item ID: 11119
DC Identifier: http://oa.upm.es/11119/
OAI Identifier: oai:oa.upm.es:11119
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 21 Jun 2012 06:52
Last Modified: 20 Apr 2016 19:17
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM