Parallel Dynamic Programming on Clusters of Workstations

Dormido Canto, Sebastián, Madrid Ángel, P. de y Dormido Bencomo, Sebastián . (2005) Parallel Dynamic Programming on Clusters of Workstations. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 16, NO. 9, SEPTEMBER 2005


Título Parallel Dynamic Programming on Clusters of Workstations
Autor(es) Dormido Canto, Sebastián
Madrid Ángel, P. de
Dormido Bencomo, Sebastián
Palabras clave Parallel dynamic programming
constrained optimization
combinatorial algorithms
networked workstations
performance evaluation
NOWs
Editor(es) IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 16, NO. 9, SEPTEMBER 2005
Fecha 2005-09-01
Identificador DromidoCanto_PerezdeMDormido_sep2005
bibliuned:712
Publicado en la Revista IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 16, NO. 9, SEPTEMBER 2005
Idioma eng
Versión de la publicación publishedVersion
Tipo de recurso Article
Derechos de acceso y licencia http://creativecommons.org/licenses/by-nc-nd/4.0
info:eu-repo/semantics/openAccess
Tipo de acceso Acceso abierto
Notas adicionales The standard DP (Dynamic Programming) algorithms are limited by the substantial computational demands they put on contemporary serial computers. In this work, the theory behind the solution to serial monadic dynamic programming problems highlights the theory and application of parallel dynamic programming on a general-purpose architecture (Cluster or Network Of Workstations). A simple and well-known technique, message passing, is considered. Several parallel serial monadic DP algorithms are proposed, based on the parallelization in the state variables and the parallelization in the decision variables. Algorithms with no interpolation are also proposed. It is demonstrated how constraints introduce load unbalance which affect scalability and how this problem is inherent to DP.

 
Versiones
Versión Tipo de filtro
Contador de citas: Google Scholar Search Google Scholar
Estadísticas de acceso: 335 Visitas  -  Estadísticas en detalle
Creado: Wed, 28 Nov 2007, 11:06:45 CET