Texto completo
Vista Previa |
PDF (Portable Document Format)
- Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (1MB) | Vista Previa |
Lock-free Parallel Dynamic Programming
Cita
Stivala, A., Stuckey, P.J., García de la Banda, M., Hermenegildo, Manuel V. 
ORCID: https://orcid.org/0000-0002-7583-323X 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.
ORCID: https://orcid.org/0000-0002-7583-323X 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.
Descripción
| Título: | Lock-free Parallel Dynamic Programming |
|---|---|
| Autor/es: |
|
| Tipo de Documento: | Artículo |
| Título de Revista/Publicación: | Journal of parallel and distributed computing |
| Fecha: | 2010 |
| ISSN: | 0743-7315 |
| Volumen: | 70 |
| Número: | 8 |
| Materias: | |
| ODS: | |
| 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 |
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: | https://oa.upm.es/11119/ |
| Identificador OAI: | oai:oa.upm.es:11119 |
| URL Oficial: | http://www.sciencedirect.com/science/article/pii/S... |
| Depositado por: | Biblioteca Facultad de Informatica |
| Depositado el: | 21 Jun 2012 06:52 |
| Ultima Modificación: | 20 Abr 2016 19:17 |
Acciones
- Estadísticas
- Exportar cita
- Editar (sólo personal del Archivo)
