Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/454| Estrategias de calendarización en línea para modelos jerárquico y distribuidos de Grid computacional Online job scheduling strategies for hierarchical and decentralized computational grid models | |
| Ariel Arturo Quezada Pina | |
| Andrey Chernykh | |
| Acceso Abierto | |
| Atribución | |
| Grid computacional,Calendarización en línea,Administración de recursos | |
| En esta tesis se proponen soluciones para el problema de calendarización en línea en un Grid computacional. El problema se aborda utilizando arquitecturas jerárquica de dos niveles y descentralizada de un nivel. Para el modelo de dos niveles se utiliza el esquema denominado de admisibilidad. Se presenta un análisis teórico y experimental de este esquema de admisibilidad. Para el modelo de un nivel se utilizaron estrategias basadas en migración de tareas Se implementó el algoritmo de robo de tareas el cual tiene el mejor desempeño teórico para el modelo utilizado y sólo había sido analizado de forma teórica anteriormente. Se implementaron distintas versiones del algoritmo y se comparó experimentalmente su desempeño con otros algoritmos de calendarización. Se realizaron simulaciones utilizando tres escenarios de Grid para el modelo de dos niveles y dos escenarios para el modelo de un solo nivel. Se elaboraron cargas de tareas de Grid a partir de cargas de trabajo reales de sitios de súpercómputo distribuidos en el mundo para simular cargas de trabajo de Grid para cada uno de los escenarios. Se utilizó una metodología de evaluación de desempeño en la cual se consideraron tres parámetros de desempeño no correlacionados. Considera que las métricas tienen la misma importancia y se elabora una jerarquía con las distintas estrategias para cada uno de los modelos, considerando los resultados de los distintos escenarios donde se probaron las estrategias. Para el modelo jerárquico de dos niveles, se provee de un análisis teórico estableciendo cotas de aproximación para el esquema de admisibilidad con las estrategias MLBa+PS y MCTa+PS, para el caso en línea y fuera de línea. Las cotas son para dos tipos de carga de trabajo: donde las tareas tienen a lo más el tamaño de la máquina más pequeña del Grid y donde las tareas tienen hasta el tamaño de la máquina más grande del Grid. Los resultados experimentales demostraron que nuestras estrategias se benefician al incorporar el esquema de admisibilidad. También, que estrategias más simples de calendarización, mostraron mejor desempeño. Para el modelo de un solo nivel, se provee de un análisis experimental del algoritmo de robo de tareas y de su desempeño en comparación con otras estrategias. Los resultados indican que estrategias que utilizan una sola cola de tareas tienen mejor desempeño para los escenarios propuestos. In this thesis, solutions to the problem of online Grid computing scheduling are proposed. Two-level hierarchical and one-level decentralized architectures are used. The model is defined with jobs executed online, in a non-clairvoyant fashion; multisite execution, preemption and coallocation are not allowed. An admissibility scheme is proposed for the hierarchical two-levels model. A theoretical and experimental analysis is provided for the solutions proposed for this model. For the decentralized one level model, strategies that allow job migration between sites are analyzed. This model considers point-to-point and all-to-all instant communications between sites. The stealing algorithm with the best theoretical performance for this model is implemented to carry out the first experimental analysis known up to date. Different versions of the same algorithm are implemented and compared with other one level scheduling strategies. Experiments include three Grid scenarios for the two level model and two scenarios for the one level model. Grid workloads are built from real supercomputing traces around the world for each scenario. A performance evaluation methodology considers three uncorrelated metrics. Each metric has the same importance in the analysis, and strategies are ranked for each model based on these metrics. For the two-level hierarchical model, a theoretical analysis is provided for strategies MLBa+PS and MCTa+PS which use admissible scheme, for online and offline cases. The obtained bounds consider two types of workload: jobs with sizes up to the smallest machine in the Grid, and jobs with sizes up to the biggest machine of the Grid. Results indicate the strategies benefit from admissible scheme. For the one level model, results indicate that stealing performs efficient load balancing. However, strategies that use a single queue per machine perform better in our scenarios. | |
| CICESE | |
| 2012 | |
| Tesis de doctorado | |
| Español | |
| Quezada Piña, A.A.2012.Estrategias de calendarización en línea para modelos jerárquico y distribuidos de Grid computacional.Tesis de Doctorado en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada,Baja California.96 pp. | |
| CIENCIA DE LOS ORDENADORES | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| 190371.pdf | Versión completa de la tesis | 1.56 MB | Adobe PDF | Visualizar/Abrir |