Meta-Heuristics for Scheduling in Cluster Federated Environments

Abstract

Avui en dia, moltes organitzacions, empreses o universitats han anat acumulant, durant anys, un gran nombre de recursos computacionals agrupats en clústers. Els Entorns Clúster Federats sorgeixen com una nova arquitectura amb l’objectiu d’unir tots aquests recursos, augmentant la capacitat de còmput global de l’organització sense haver de fer una gran inversió econòmica. No obstant això, l’elevat nombre de màquines i recursos computacionals, comporten un gran consum energètic. A causa de les connotacions econòmiques i sostenibles que això implica, recentment s’ha obert una nova línia d’investigació que s’ha centrat a reduir el consum d’energia i maximitzar el rendiment de les aplicacions i la utilització dels recursos computacionals . La planificació en aquests entorns, responsable d’assignar les aplicacions als recursos del sistema, ofereix la possibilitat d’obtenir grans millores, ja que gestionar correctament els recursos pot tenir un gran impacte en el rendiment del sistema i en l’eficiència energètica. Tanmateix, aquest procés és molt complex, ja que pertany al grup de problemes NP. Aquesta tesi estudia el problema de la planificació de grans workloads extrets de diverses traces reals. Les tècniques proposades consideren l’heterogeneïtat dels recursos del sistema, així com també la capacitat d’aplicar la co-assignació per aprofitar els recursos sobrants de cada clúster. Les propostes utilitzaran tàctiques sofisticades multi-criteri, basades en Algoritmes Genètics i Particle Swarm Optimization centrades en la reducció tant del temps d’execució dels treballs com del consum energètic del sistema. Els resultats mostren l’efectivitat dels mètodes proposats, proporcionant solucions que milloren el rendiment respecte a altres tècniques presents en la literatura. Obrint una nova i interessant línia d’investigació en el camp de la planificació en entorns altament distribuïts i heterogenis.

Hoy en día, muchas organizaciones, empresas o universidades han ido acumulando, durante años, un gran número de recursos agrupados en clústeres. Los Entornos Cluster Federados surgen como una nueva arquitectura con el objetivo de unir todos estos recursos, aumentando la capacidad de cómputo global de la organización sin tener que hacer una gran inversión económica. Sin embargo, el elevado número de máquinas y recursos de computo, comportan un gran consumo energético. Debido a las connotaciones económicas y sostenibles que ello implica, recientemente se ha abierto una nueva línea de investigación que se ha centrado en reducir el consumo de energía y maximizar el rendimiento de las aplicaciones y utilización de los recursos. La planificación en estos entornos, responsable de asignar las aplicaciones a los recursos del sistema, ofrece la posibilidad de obtener grandes mejoras, ya que gestionar correctamente los recursos puede tener un gran impacto en el rendimiento del sistema y en la eficiencia energética. Sin embargo, este proceso es muy complejo, ya que pertenece al grupo de problemas NP. Esta tesis estudia el problema de la planificación de grandes workloads extraídos de distintas trazas reales. Las técnicas propuestas consideran la heterogeneidad de los recursos del sistema, así como también la capacidad de aplicar la co-asignación para aprovechar los recursos sobrantes de cada clúster. Las propuestas utilizarán tácticas sofisticadas multi-criterio, basadas en Algoritmos Genéticos y Particle Swarm Optimization centradas en la reducción tanto del tiempo de ejecución de los trabajos como del consumo energético del sistema. Los resultados muestran la efectividad de los métodos propuestos, proporcionando soluciones que mejoran el rendimiento respecto a otras técnicas presentes en la literatura. Abriendo una nueva e interesante línea de investigación en el campo de la planificación en entornos altamente distribuidos y heterogéneos.

Many organizations, companies or universities have accumulated, over the years, a large number of computing resources grouped in Clusters. Cluster Federated Environments arise as a new architecture with the objective of joining all these resources, increasing the global computing capacity of the organization without making a great economic investment. However, the high number of machines and computing resources imples great energy consumption. Due to the economic and sustainable connotations that this entails, recently a new line of investigation has focused on reducing energy consumption while maximizing the performance of the applications and the usage of the system. The scheduling in these environments, responsible for allocating the applications to the system resources, offers the possibility of obtaining great improvements, as managing the resources correctly can have a great impact on the system performance and energy efficiency. However, this process is very complex, since it belongs to the NP problem group. This PhD studies the problem of scheduling large batch workloads extracted from diverse real traces. The proposed techniques consider the heterogeneity of the system resources as well as the ability to apply co-allocation in order to take advantage of the leftover resources across clusters. The proposals will use sophisticated multi-criteria tactics, based on Genetic Algorithms and Particle Swarm Optimization, focused on reducing both the execution time of the jobs and the energy consumption of the system. The results show the effectiveness of the proposed methods, which provide solutions that improved the performance compared with other well-known techniques in the literature, opening new and interesting research lines in the scheduling field in highly distributed and heterogeneous environments.