Lock-free Parallel Dynamic Programming

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

Descripción

Título: Lock-free Parallel Dynamic Programming
Autor/es:
  • Stivala, A.
  • Stuckey, P.J.
  • García de la Banda, M.
  • Hermenegildo, Manuel V.
  • Wirth, A.
Tipo de Documento: Artículo
Título de Revista/Publicación: Journal of parallel and distributed computing
Fecha: 2010
Volumen: 70
Materias:
Palabras Clave Informales: Dynamic programming, Lock-free hash tables, Constraint, programming, Multicores, Parallelism
Escuela: Facultad de Informática (UPM) [antigua denominación]
Departamento: Inteligencia Artificial
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (1MB) | Vista Previa

Resumen

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.

Más información

ID de Registro: 11119
Identificador DC: http://oa.upm.es/11119/
Identificador OAI: oai:oa.upm.es:11119
URL Oficial: http://www.sciencedirect.com/science/article/pii/S074373151000011
Depositado por: Biblioteca Facultad de Informatica
Depositado el: 21 Jun 2012 06:52
Ultima Modificación: 20 Abr 2016 19:17
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM