Algoritmo grasp en computación grid
Páginas: 7 (1748 palabras)
Publicado: 12 de enero de 2010
Aplicación de un algoritmo GRASP para dar solución al problema de balanceo de carga Multi-Objetivo en Computación Grid
Pedro Castañeda1 David Mauricio2
1,2Universidad Nacional Mayor de San Marcos
1pcastanedav@gmail.com, 2dms_researsh@yahoo.com
Resumen
La gran demanda tanto de computación como de espacio y gestión de almacenamiento requeridos por un gran número deaplicaciones que gestionan grandes cantidades de datos y han de hacerlo de forma eficiente, exige el uso de nuevas tecnologías, como es el caso de las Tecnologías Grid que permite aprovechar los recursos computacionales que muchas organizaciones no vienen utilizando adecuadamente. Uno de los principales problemas que se genera cuando se comparte recursos computacionales es el Balanceo de Carga queimplica en cómo gestionar los diversos recursos que las grandes organizaciones geográficamente distribuidas van a compartir a través de redes de alta velocidad. En el presente artículo se muestra un algoritmo GRASP para balancear la carga dinámicamente sobre arquitecturas Grid, hacienda uso de dos criterios de relajación que permitirá elegir el recurso más óptimo para la ejecución de unadeterminada tarea.
1. Introducción
La necesidad creciente de recursos de cómputo e infraestructuras que proporcionen el soporte para estos recursos dio origen a conceptos como: programación paralela, clusters, P2P, y Grids, siendo este último el que toma realce entre los demás, debido a las implicaciones derivadas de este concepto.
El Grid no sólo es una aplicación para interconexión de equipos decómputo, su concepto es tan amplio como el mismo problema a resolver, puesto que es una tecnología que ofrece una solución por medio de una estructura abierta la cual, además de permitir el manejo de recursos locales y remotos, plantea la convivencia entre sistemas distribuidos heterogéneos (independientes de arquitectura física y lógica) por medio de redes tanto comerciales como privadas[Galaviz, 2005].
El rendimiento del sistema en Computación Grid depende directamente de la utilización efectiva de todos los procesadores. Por tanto, es crítico distribuir las tareas de una aplicación entre los procesadores de forma que todos los procesadores estén ocupados trabajando eficientemente en la aplicación y que no haya procesadores ociosos mientras quede trabajo pendiente. Encontrar unasolución óptima al balanceo de la carga es un problema NP-completo, y por eso se suele recurrir a soluciones heurísticas y aproximadas.
El resto de éste artículo está organizado de la siguiente manera. En la sección 2 se muestran Trabajos Previos. La sección 3 describe el algoritmo GRASP. Los Experimentos y Resultados se encuentran en la sección 4. La Discusión de los Experimentos se muestra en lasección 5 y finalmente, las conclusiones están en la sección 6.
2. Trabajos Previos
Si bien existen métodos y algoritmos que han dado solución a problemas específicos, cuando se requiere aplicar a entornos Grid, se muestran deficiencias por los siguientes motivos:
a) Han sido desarrollados para entornos homogéneos, donde las características de los recursos que integran la red son similares,presentando dificultades cuando se implantan en un entorno Grid.
b) Los algoritmos han sido desarrollados para tecnologías propietarias.
c) Los algoritmos han sido desarrollados para modelos cliente-servidor.
d) En [Bonabeau, 1999], numerosos experimentos muestran que utilizando la técnica metaheurística “Colonia de Hormigas”, se encuentran soluciones cercanas a las óptimas, pero podemosencontrarnos con que la solución se quede rápidamente estancado en un óptimo local, sin embargo, los métodos metaheurísticos son susceptibles de ser mejorados.
3. Algoritmo GRASP
Para dar solución al problema de balanceo de carga multi-objetivo en un entorno Grid, en su variante Tareas Independientes y Recursos Heterogéneos, se propone un algoritmo GRASP con dos criterios de relajación, cuyos...
Pedro Castañeda1 David Mauricio2
1,2Universidad Nacional Mayor de San Marcos
1pcastanedav@gmail.com, 2dms_researsh@yahoo.com
Resumen
La gran demanda tanto de computación como de espacio y gestión de almacenamiento requeridos por un gran número deaplicaciones que gestionan grandes cantidades de datos y han de hacerlo de forma eficiente, exige el uso de nuevas tecnologías, como es el caso de las Tecnologías Grid que permite aprovechar los recursos computacionales que muchas organizaciones no vienen utilizando adecuadamente. Uno de los principales problemas que se genera cuando se comparte recursos computacionales es el Balanceo de Carga queimplica en cómo gestionar los diversos recursos que las grandes organizaciones geográficamente distribuidas van a compartir a través de redes de alta velocidad. En el presente artículo se muestra un algoritmo GRASP para balancear la carga dinámicamente sobre arquitecturas Grid, hacienda uso de dos criterios de relajación que permitirá elegir el recurso más óptimo para la ejecución de unadeterminada tarea.
1. Introducción
La necesidad creciente de recursos de cómputo e infraestructuras que proporcionen el soporte para estos recursos dio origen a conceptos como: programación paralela, clusters, P2P, y Grids, siendo este último el que toma realce entre los demás, debido a las implicaciones derivadas de este concepto.
El Grid no sólo es una aplicación para interconexión de equipos decómputo, su concepto es tan amplio como el mismo problema a resolver, puesto que es una tecnología que ofrece una solución por medio de una estructura abierta la cual, además de permitir el manejo de recursos locales y remotos, plantea la convivencia entre sistemas distribuidos heterogéneos (independientes de arquitectura física y lógica) por medio de redes tanto comerciales como privadas[Galaviz, 2005].
El rendimiento del sistema en Computación Grid depende directamente de la utilización efectiva de todos los procesadores. Por tanto, es crítico distribuir las tareas de una aplicación entre los procesadores de forma que todos los procesadores estén ocupados trabajando eficientemente en la aplicación y que no haya procesadores ociosos mientras quede trabajo pendiente. Encontrar unasolución óptima al balanceo de la carga es un problema NP-completo, y por eso se suele recurrir a soluciones heurísticas y aproximadas.
El resto de éste artículo está organizado de la siguiente manera. En la sección 2 se muestran Trabajos Previos. La sección 3 describe el algoritmo GRASP. Los Experimentos y Resultados se encuentran en la sección 4. La Discusión de los Experimentos se muestra en lasección 5 y finalmente, las conclusiones están en la sección 6.
2. Trabajos Previos
Si bien existen métodos y algoritmos que han dado solución a problemas específicos, cuando se requiere aplicar a entornos Grid, se muestran deficiencias por los siguientes motivos:
a) Han sido desarrollados para entornos homogéneos, donde las características de los recursos que integran la red son similares,presentando dificultades cuando se implantan en un entorno Grid.
b) Los algoritmos han sido desarrollados para tecnologías propietarias.
c) Los algoritmos han sido desarrollados para modelos cliente-servidor.
d) En [Bonabeau, 1999], numerosos experimentos muestran que utilizando la técnica metaheurística “Colonia de Hormigas”, se encuentran soluciones cercanas a las óptimas, pero podemosencontrarnos con que la solución se quede rápidamente estancado en un óptimo local, sin embargo, los métodos metaheurísticos son susceptibles de ser mejorados.
3. Algoritmo GRASP
Para dar solución al problema de balanceo de carga multi-objetivo en un entorno Grid, en su variante Tareas Independientes y Recursos Heterogéneos, se propone un algoritmo GRASP con dos criterios de relajación, cuyos...
Leer documento completo
Regístrate para leer el documento completo.