Título

Optimización extrema generalizada para la calendarización de trabajos paralelos en sistemas Grid de dos niveles

Generalized extremal optimization for parallel job scheduling in two levels hierarchical Grid systems

Autor

Jorge Mario Cortés Mendoza

Colaborador

Andrey Chernykh (Asesor de tesis)

Nivel de Acceso

Acceso Abierto

Resumen o descripción

Los sistemas Grid se utilizan cada vez más debido a los beneficios mostradoscuando es necesario trabajar con una gran cantidad de datos o poder de cómputo. Los retosiniciales se han superado (ejecución de trabajos, transferencia de archivos, múltiplescuentas de usuarios, etc.). Actualmente, se trabaja en la búsqueda de mecanismos quepermitan mejorar la utilización del Grid, uno de los campos más estudiados es lacalendarización de trabajos.Se han utilizado varias técnicas para afrontar el problema de calendarización ensistemas Grid. En los últimos años, la utilización de heurísticas inspiradas por la naturalezaha tenido un gran auge debido a la efectividad para solucionar problemas difíciles. Elpresente trabajo propone la heurística de optimización extrema generalizada (GEO) parasolucionar el problema de calendarización de trabajos paralelos en sistemas Grid de dosniveles. La heurística GEO se basa en el proceso de optimización extrema observado ensistemas complejos, donde avalanchas generacionales evolucionan un ecosistema hasta unestado crítico. Se ha implementado la abstracción de este modelo para solucionar diversosproblemas como: TSP, grafo bipartito y calendarización en sistemas multiprocesadores.Con el objetivo de evaluar el desempeño de GEO como estrategia de asignación detrabajos, se define un modelo para el problema de calendarización y se realizan una serie desimulaciones. Los resultados se analizan y comparan con estrategias existentes en laliteratura. La evaluación de los resultados muestra que es apropiado aplicar optimizaciónextrema generalizada al problema de calendarización de trabajos paralelos en sistemas Gridde dos niveles porque supera el desempeño de las estrategias clásicas de calendarización. 

Grids are becoming almost commonplace nowadays because of the benefits shownwhen it is necessary to work with a large amount of data or computing power. The initialchallenges of Grid computing have been overcome to first order (running a job, transferringfiles, managing multiple user accounts, etc.). Researchers can now address the issuesinvolved to improve the uses of Grid computing, one of the most studied field is jobscheduling.Several techniques have been used to address the problem of scheduling. In recentyears the use of heuristics inspired by nature has boomed owing the effectiveness to solvehard problems. This work presents the generalized extremal optimization heuristic (GEO)to solve parallel job scheduling problem in two levels hierarchical Grid systems. GEOheuristic is based on the extremal optimization observed in complex systems, wheregenerational avalanches evolve an ecosystem to a critical state. The abstraction of thismodel has been successfully implemented to solve various problems such TSP, bipartitegraph and scheduling in multiprocessors systems.In order to evaluate the performance of GEO as job allocation strategy, we defined amodel for the scheduling problem and a series of simulations. The results are analyzed andcompared with existing strategies in the literature. Evaluation result shows that it isappropriate to apply generalized extremal optimization to the parallel job schedulingproblem in two levels hierarchical Grid systems because it exceeds the performance oftraditional scheduling strategies. 

Editor

CICESE

Fecha de publicación

2011

Tipo de publicación

Tesis de maestría

Formato

application/pdf

Idioma

Español

Sugerencia de citación

Cortés Mendoza,J.M.2011.Optimización extrema generalizada para la calendarización de trabajos paralelos en sistemas Grid de dos niveles.Tesis de Maestría en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California.x, 100 pp.

Repositorio Orígen

Repositorio Institucional CICESE

Descargas

878

Comentarios



Necesitas iniciar sesión o registrarte para comentar.