Comparativa de tres cruzas y cuatro mutaciones para el problema de asignación de tareas en sistemas de cómputo heterogéneo

Comparativa de tres cruzas y cuatro mutaciones para el problema de asignación de tareas en sistemas de cómputo heterogéneo José Carlos Soto Monterrubio1, Héctor Joaquín Fraire Huacuja1, Aurelio Alejandro Santiago Pineda1 1

Instituto Tecnológico de Ciudad Madero

[email protected], [email protected], [email protected] Resumen Este trabajo se enfoca en el problema de asignación de tareas independientes en sistemas de cómputo heterogéneo. La principal contribución es un estudio comparativo de diversas cruzas y mutaciones para el problema de consumo de energía para tareas sin precedencias en clústeres heterogéneos. Dentro de este comparativo se propone una mutación que aprovecha características del problema, la cual se denomina balanceo de carga. Para el control de la energía se usa la técnica de escalamiento dinámico de voltaje y frecuencia (DVFS, por sus siglas en inglés). La comparación se desarrolló utilizando el algoritmo multiobjetivo NSGA-II. Palabras clave: asignación de tareas, comparación de operadores genéticos, multiobjetivo. 1. Introducción Los sistemas de cómputo de alto rendimiento (HCP, High Performance Computing) requieren altas cantidades de energía [1], estos sistemas se encuentran en una gran variedad de escenarios tales como en la NASA o WallStreet [2]. HPC también se conocen como súper computadoras y están compuestas por un conjunto de máquinas interconectadas en una plataforma de red. La National Unversity of Defense Technology (NUDT) en China tiene el sistema HPC más grande con 3,120,000 núcleos con un desempeño de 33.9 Pflops y un consumo de energía de 17.89 MW [3]. Más núcleos proveen más poder de cómputo pero esto implica un mayor consumo de energía. Un mayor uso de energía para ejecutar aplicaciones aumenta el gasto económico y los problemas de calentamiento. El HCSP (Heterogenous Computing Scheduling Problem) con DVFS (Dynamic Voltaje and Frequency Scaling) está formado por un HPC heterogéneo y un conjunto de tareas que deben de ser asignadas a una máquina del HPC. El makespan es la diferencia que existe entre el tiempo de inicio de la primera tarea y el tiempo en que finaliza la última tarea del conjunto. Este problema trata de encontrar la mejor asignación de tareas en máquinas que produzca el menor makespan, y además de generar el menor consumo de energía.

2. Definiciones y conceptos Esta sección presenta los conceptos básicos usados en optimización multi-objetivo basado en optimalidad de Pareto. Estas definiciones son tomadas de [4]. Definición 1. Problema de optimización mulit-objetivo (MOP). Dado un vector función 𝑓 𝑥 = [𝑓& 𝑥 , 𝑓( 𝑥 , … , 𝑓* (𝑥)] y su espacio de soluciones posibles Ω, el MOP consiste en encontrar un vector 𝑥 ∈ Ω que optimice un vector función 𝑓(𝑥). Sin pérdida de generalidad se asumen únicamente funciones de minimización. Definición 2. Dominancia de Pareto. Un vector 𝑥 domina 𝑥′ (se denota como 𝑥 ≺ 𝑥′) si 𝑓2 𝑥 ≤ 𝑓2 (𝑥 4 ) para toda función 𝑖 en 𝑓 hay al menos una 𝑖 tal que 𝑓2 𝑥 < 𝑓2 (𝑥′). Definición 3. Óptimo de Pareto. Un vector 𝑥 ∗ es óptimo de Pareto si no existe 𝑥 4 ∈ Ω tal que 𝑥 4 ≺ 𝑥 ∗ . Definición 4. Conjunto de óptimo de Pareto. Dado un MOP, el conjunto de óptimo de Pareto es definido como 𝑃∗ {𝑥 ∗ ∈ Ω}. Definición 5. Frente de Pareto. Dado un MOP y su conjunto de óptimo de Pareto 𝑃∗ , el frente de Pareto se define como 𝑷𝑭∗ = 𝒇 𝒙 𝒙 ∈ 𝑷∗ . 3. Descripción del problema El problema tratado ocurre en los clústeres HPC, donde las máquinas son usadas para ejecutar una gran carga de tareas. Se asumen las siguientes condiciones: las máquinas son capaces de usar DVFS, las máquinas son heterogéneas, únicamente se reciben tareas sin precedencias, el desempeño de una máquina no es afectada por las demás máquinas. Cada máquina tiene diferentes niveles de configuración para las velocidades de procesamiento. Dado un conjunto de tareas 𝑇 = {𝑡& , 𝑡( , … , 𝑡B }, un conjunto de máquinas heterogéneas 𝑀 = {𝑚& , 𝑚( , … , 𝑚* }, los tiempos de ejecución de cada tarea en cada máquina 𝑃 = {𝑝&,& , 𝑝&,( , … , 𝑝B,* }. El mínimo makespan producido por la asignación de máquina/tarea que minimice: * 𝑀𝐴𝑋HI& (

𝑃2,H ∀𝑡2 ∈ 𝑚H )

(1)

Debido a que las máquinas incluyen tecnología DVFS y son heterogéneas, existen diferentes niveles de voltaje para cada máquina 𝑚H tiene asociada una velocidad relativa. Cuando el

voltaje más alto es seleccionado la velocidad es igual a 1 (ejecución normal en 𝑃), cuando se selecciona un voltaje más bajo la velocidad relativa es disminuida. El tiempo de ejecución 4 relativo 𝑃2,H es calculado con la siguiente ecuación. 4 𝑃2,H =

𝑃2,H 𝑣𝑒𝑙𝑜𝑐𝑖𝑑𝑎𝑑

(2)

Dado un conjunto de tareas 𝑇, y un conjunto de máquinas heterogéneas 𝑀y sus respectivos niveles de voltaje 𝑉H = 𝑣2,& , 𝑣2,( , … , 𝑣2,S ∀ 𝑚H ∈ 𝑀 de diferentes tamaños 𝑙. La energía mínima es producida por la asignación de máquinas/voltaje/tarea que minimice: * ( 4 𝑉H,T 𝑃2,H

(3) ∀ 𝑡2 ∈ 𝑚H

HI&

Donde 𝑝 es el índice del voltaje seleccionado en 𝑉H , la tecnología DVFS se utiliza en el consumo de energía, la función objetivo de energía para el makespan es modificada de la siguiente manera: * 𝑀𝐴𝑋HI& (

(4)

4 𝑃2,H ∀𝑡2 ∈ 𝑚H )

El MOP estudiado consiste en encontrar las asignaciones de máquina/voltaje/tarea que minimice (4) y (3). 4. Operadores genéticos En los algoritmos genéticos el vector de variables de decisión se denomina cromosoma. Actualmente el cromosoma es representado por una estructura de datos particular. La representación del cromosoma para este trabajo es el de la Fig. 1 el cual asigna una máquina 𝑀 y una configuración de voltaje para cada tarea 𝑇.

Figura 1. Representación del cromosoma.

El algoritmo genético consiste de tres operadores genéticos la selección, cruza y mutación. La selección es un mecanismo probabilístico que favorece a los individuos más aptos para tener descendencia. La cruza es un intercambio de secciones del cromosoma entre dos individuos para formar uno nuevo. La mutación es un cambio aleatorio en el cromosoma del individuo. Uno de los mejores algoritmos multiobjetivo es el NSGAII [5] el cual consta de dos mecanismos importantes: fast nondominanted sort el cual se encarga de ordenar el conjunto

de soluciones 𝑃 en diversos conjuntos de soluciones no dominadas 𝐹. Crowding distance assignment permite asignar un valor de calidad a una solución. Para la selección se utilizaron las soluciones que se encuentran en el frente cero si no se llena el número deseado de padres se toman de los siguientes frentes. Las cruzas implementadas son las siguientes. Cruza uniforme (C1): cada gen del padre tiene el 50% de pasar al hijo Fig. 3 (a). Cruza en punto medio (C2): el cromosoma se divide en dos segmentos y cada uno pasa a un hijo diferente Fig. 3 (b). Cruza en dos puntos (C3): el cromosoma se divide en tres segmentos y cada segmento pasa a un hijo diferente Fig. 3 (c). Cruza multipunto (C4): se selecciona un número aleatoriamente el cual indica en cuanto segmentos se dividirá el cromosoma Fig. 3 (d).

Figura 2. Representación de las cruzas.

Se implementó una mutación en la que se modifica el 10% del cromosoma (M1). Una mutación en la que cada gen tiene el 5% de cambiar (M2). Se propone una mutación (M3) que está basada en la idea del balanceo de cargas la cual consiste en distribuir el peso de las máquinas. Esta mutación selecciona aleatoriamente una tarea que se encuentra en una máquina que genera makespan y la cambia a otra máquina aleatoriamente Fig. 4.

Figura 3. Mutación de balanceo de carga.

5. Experimentación Para la experimentación se utilizó un conjunto de cuarenta instancias proporcionadas por el Dr. Pecero Sánchez de la universidad de Luxemburgo. El experimento consistió en 50 pruebas independientes por cada combinación de cruza y mutación. Para medir la calidad de los resultados se utilizaron los indicadores de calidad (IQ) de Hypervolume (HV), Generational Distance (GD) y Generalized Spread (GS), para medir volumen, distribución del frente y diversidad respectivamente. 6. Resultados En la Tabla 1 la primera, tercera y quinta columna muestran la combinación de cruza/mutación. La segunda, cuarta y sexta columna muestran los IQ de HV, GD y GS, respectivamente. Tabla 1. Resultados de la experimentación.

Cruza-Mutación C1M3 C1M2 C1M1 C4M1 C4M3 C4M2 C2M1 C2M3 C2M2 C3M1 C3M3 C3M2

HV 0.776390 0.775394 0.774734 0.769459 0.768544 0.767315 0.528142 0.520752 0.516562 0.510700 0.506926 0.506756

Cruza-Mutación C1M3 C1M1 C1M2 C4M1 C4M3 C4M2 C2M1 C2M2 C3M1 C2M3 C3M3 C3M2

GD 0.004160 0.004252 0.004577 0.005542 0.005808 0.005811 0.075285 0.075713 0.076519 0.077973 0.078446 0.078886

Cruza-Mutación C4M1 C4M2 C4M3 C2M1 C3M1 C2M2 C3M2 C2M3 C1M2 C1M3 C1M1 C3M3

GS 0.745476 0.745545 0.747649 0.758623 0.759231 0.759893 0.773652 0.777252 0.783733 0.793533 0.794606 0.794631

7. Conclusiones De la Tabla 1 podemos observar que la mejor combinación para HV y GD es la combinación de C1 con M3, además de que C1 obtiene los mejores resultados para cualquiera de las tres mutaciones. En cambio para obtener mejor diversidad es mejor utilizar la C4 con la M1. De los resultados obtenidos podemos observar que el aprovechar características propias del problema obtenemos mejores resultados. Parte de las contribuciones es la mutación propuesta en este trabajo denominada balanceo de carga la cual consiste en identificar que elemento del cromosoma está aportando mayor peso y tratar de cambiar dicho elemento identificado a otro valor.

Referencias [1] W.-c. Feng, «The importance of being low power in high performance computing,» de CTWatch Quarterly, vol. 1, 2005, pp. 11-20. [2] T. J. W., I. R. Center y D. Feitelson, «A Survey of Scheduling in Multiprogrammed Parallel Systems,» IBM T. J. Watson Research Center, 1994. [3] TOP500.org, «The 43rd top500 list,» ISC14, Leipzig, Germany, 2014. [4] A. S. Pineda, H. J. F. Huacuja, B. Dorronsoro, J. E. Pecero, C. G. Santillan, J. J. G. Barbosa y J. C. S. Monterrubio, «A survey of decomposition methods for multi-objective optimization,» de Recent Advances on Hybrid Approaches for Designing Intelligent Systems, vol. 547, O. Castillo, P. Melin, W. Pedrycz y J. Kacprzyk, Edits., Tijuana, Springer International Publish, 2014. [5] D. K., A. S., P. A. y M. T., «A fast elitist nondominated sorting genetic algorithm for multiobjective optimization: Nsga-ii.,» In Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, vol. 1917, 2000. [6] D. K., A. S., P. A. y M. T., «A fast elitist non-dominated sorting algorithm for multi-objective optimization: Nsga-ii,» Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, vol. 1917, nº Lecture Notes in Computer Science, 2000.