Análisis de Consumo Energético en Algoritmos Genéticos Paralelos

Trabajo de Fin de M´ aster M´ aster en Ciencia de Datos e Ingenier ´ ıa de Computadores An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos Autor Salvador Moreno Guti´errez Tutor y Cotutor Julio Ortega Lopera Miguel Damas Hermoso Granada, 7 de septiembre de 2017 MÁSTER EN CIENCIA DE DATOS E INGENIERÍA DE COMPUTADORES DECLARACIÓN DE ORIGINALIDAD DEL TRABAJO DE FIN DE MÁSTER D. Julio Ortega Lopera y D. Miguel Damas Hermoso, profesores del Departamento de Arquitectura y Tecnología de Computadores de la Universidad de Granada, como director/es del Trabajo Fin de Máster titulado “Análisis de Consumo Energético en Algoritmos Genéticos Paralelos” y realizado por el alumno D. Salvador Moreno Gutiérrez. CERTIFICA/N: que el citado Trabajo Fin de Máster, ha sido realizado y redactado por dicho alumno y autorizan su presentación. Granada, Fdo. Julio Ortega Lopera Fdo. Miguel Damas Hermoso Agradecimientos A mi familia y amigos por todo su apoyo; a mis tutores Miguel y Julio su inconmesurable ayuda; y a Patri, Manolo, Marce, las chicas del Hogar San Judas Chico, Giorgina, Durso, Tati, Tatiana y Mauricio, que han estado tan presentes durante la redacci´on de esta memoria en “el Per´u”. Este trabajo ha sido financiado por el Ministerio de Econom´ıa y Competitividad y los fondos FEDER a trav´es del proyecto TIN2015-67020-P. 2 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez An´ alisis de Consumo Energ´ etico en Algoritmos Gen´ eticos Paralelos Energy Consumption Analisys in Parallel Genetic Algorithms Salvador Moreno Guti´errez [email protected] Resumen. En este Trabajo de Fin de M´aster se estudia el consumo energ´etico de algoritmos gen´eticos aplicado la selecci´on de caracter´ısticas multiobjetivo en problemas BCI o Brain Computer Interface por sus siglas en ingl´es. Razones econ´omicas, de impacto medioambiental y de gesti´on de recursos han puesto en el punto de mira el consumo energ´etico de la ejecuci´on de programas desde m´aquinas de altas prestaciones hasta dispositivos m´oviles como smartphones. El consumo energ´etico del algoritmo estudiado se ha caracterizado como caja negra, haciendo la metodolog´ıa que modela el algoritmo, y que es desarrollada a lo largo de toda la memoria, f´acilmente portable y exclusivamente dependiente de par´ametros de configuraci´on de la evoluci´on de la poblaci´on. Del an´alisis de los datos se concluye que la evaluaci´on de los individuos es la parte m´as importante del algoritmo gen´etico estudiado, y que la repartici´on de esta carga entre el m´aximo n´umero de n´ucleos es beneficiosa para la eficiencia. Adem´as, el modelo lineal construido consigue, tras un an´alisis de anomal´ıas y clustering con k-medias, ajustarse al test de validaci´on con un 1.1925 % de error. Palabras calve. Eficiencia energ´etica, modelo, caja negra, clustering, k-medias, detecci´on de anomal´ıas, local outlier factor, LOF, MATLAB, Python, Arduino Mega. Abstract. The energy consumption in parallel genetic algorithms applied to BCI – Brain Computer Interface – aplications is studied in this Master’s Thesis. Economical, environmental and resource management reasons have risen up the importance of energy consumption when running programs from high performance computers to the cheapest smartphones. The algorithm’s energy consumption has been modeled as a black-box, making the methodology deployed along the document easily portable and solely related to settings that configure the population’s evolution. Data analysis reveals that evaluation of individuals is the most important part in the entire process and that sharing that workload amongst the maximum number of cores available is good for efficiency. Moreover, the linear regression model built scores a 1.925 % error rate after outlier removal and k-means clustering. Keywords. Energy efficiency, model, black-box, clustering, k-means, outlier removal, local outlier factor, LOF, MATLAB, Python, Arduino Mega. 3 ´ Indice general ´ Indice de figuras 6 ´ Indice de tablas 8 1. Introducci´on 9 1.1. Objetivos ............................................. 9 1.2. Estructuradelamemoria .................................... 9 2. Fundamentaci´on: estado del arte 11 2.1. Modelos de consumo energ´etico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1.1. Objetivosdelmodelo................................... 11 2.1.2. Enfoques de modelado de consumo energ´etico . . . . . . . . . . . . . . . . . . . . . 12 2.2. Paralelizaci´on en islas: selecci´on de caracter´ısticas mediante clasificaci´on multiobjetivo en aplicacionesBCI ......................................... 13 2.2.1. Procedimiento de Paralelizaci´on en Islas para Selecci´on de Caracter´ısticas Multiobjetivo.......................................... 14 2.2.2. Selecci´on de caracter´ısticas en BCI con MRA . . . . . . . . . . . . . . . . . . . . . 16 2.3. Parallel Computing Toolbox de MATLAB . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3. Recogida de datos 18 3.1. Metodolog´ıa............................................ 18 3.2. Medidas de tiempo en runtime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.3. Medidadeenerg´ıa ........................................ 21 4. An´alisis de los datos 24 4.1. Datos de tiempo y consumo energ´etico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.2. Tests estad´ısticos seg´un experimento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.2.1. Test seg´un n´umero de hilos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.2.2. Test seg´un n´umero de individuos en la poblaci´on . . . . . . . . . . . . . . . . . . . 35 4.2.3. Test seg´un n´umero de generaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.3. Clustering y detecci´on de anomal´ıas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.3.1. Detecci´on de anomal´ıas mediante IQR . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.3.2. Detecci´on de anomal´ıas mediante distancia k-NN . . . . . . . . . . . . . . . . . . . 44 4.3.3. Detecci´on de anomal´ıas mediante LOF . . . . . . . . . . . . . . . . . . . . . . . . . 46 4.3.4. Detecci´on de anomal´ıas mediante selecci´on manual, LOF e IQR . . . . . . . . . . . 47 4.4. Predicci´on de consumo energ´etico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.4.1. Construcci´on del modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.4.2. Validaci´ondelmodelo .................................. 54 5. Conclusiones y trabajo futuro 55 5.1. Conclusiones ........................................... 55 5.2. Trabajofuturo .......................................... 56 5.3. Agradecimientos ......................................... 56 4 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez A. Instrucciones para la recogida de datos. 57 A.1.Recogidadelosdatos ...................................... 57 A.1.1.Datosdeenerg´ıa ..................................... 57 A.1.2.Datosdetiempo ..................................... 59 A.1.3. Construcci´on del dataset: uni´on de datos de tiempo y energ´ıa . . . . . . . . . . . . 59 A.2.C´odigofuente........................................... 59 B. Instrucciones para la predicci´on de consumo energ´etico. 63 Bibliograf´ıa 65 5 ´ Indice de figuras 2.1. Selecci´on de caracter´ısticas mediante m´etodo envoltorio: (a) procedimiento secuencial; (b) procedimiento paralelizado en islas. Fuente: [1]. . . . . . . . . . . . . . . . . . . . . . . . . 14 3.1. Diagrama de flujo: extracci´on de caracter´ısticas mediante paralelizaci´on en Islas. . . . . . 19 3.2. Subrutina: inicializaci´on de la poblaci´on. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.3. Subrutina: evoluci´on de la poblaci´on. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.4. Arduino Mega y sensores de corriente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.5. Diagrama interno de sensor de corriente YHDC-SCTD010T-5A. . . . . . . . . . . . . . . . 21 3.6. Preprocesamiento de datos de tiempo y energ´ıa. . . . . . . . . . . . . . . . . . . . . . . . . 23 4.1. Distribuci´on energ´etica para experimento 4-160-50-1 . . . . . . . . . . . . . . . . . . . . . 27 4.2. Distribuci´on de tiempo para experimento 4-160-50-1 . . . . . . . . . . . . . . . . . . . . . 27 4.3. Distribuci´on energ´etica para experimento 8-160-50-1 . . . . . . . . . . . . . . . . . . . . . 28 4.4. Distribuci´on de tiempo para experimento 8-160-50-1 . . . . . . . . . . . . . . . . . . . . . 28 4.5. Distribuci´on energ´etica para experimento 4-160-100-1 . . . . . . . . . . . . . . . . . . . . 29 4.6. Distribuci´on energ´etica para experimento 4-160-100-1 . . . . . . . . . . . . . . . . . . . . 29 4.7. Distribuci´on energ´etica para experimento 8-160-100-1 . . . . . . . . . . . . . . . . . . . . 30 4.8. Distribuci´on de tiempo para experimento 8-160-100-1 . . . . . . . . . . . . . . . . . . . . 30 4.9. Distribuci´on energ´etica para experimento 4-320-50-1 . . . . . . . . . . . . . . . . . . . . . 31 4.10. Distribuci´on de tiempo para experimento 4-320-50-1 . . . . . . . . . . . . . . . . . . . . . 31 4.11. Distribuci´on energ´etica para experimento 8-320-50-1 . . . . . . . . . . . . . . . . . . . . . 32 4.12. Distribuci´on de tiempo para experimento 8-320-50-1 . . . . . . . . . . . . . . . . . . . . . 32 4.13. Distribuci´on energ´etica para experimento 4-320-100-1 . . . . . . . . . . . . . . . . . . . . 33 4.14. Distribuci´on de tiempo para experimento 4-320-100-1 . . . . . . . . . . . . . . . . . . . . 33 4.15. Distribuci´on energ´etica para experimento 8-320-100-1 . . . . . . . . . . . . . . . . . . . . 34 4.16. Distribuci´on de tiempo para experimento 8-320-100-1 . . . . . . . . . . . . . . . . . . . . 34 4.17. Clustering para experimento 4-160-50-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.18. Clustering para experimento 8-160-50-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.19. Clustering para experimento 4-160-100-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.20. Clustering para experimento 8-160-100-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.21. Clustering para experimento 4-320-50-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.22. Clustering para experimento 8-320-50-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.23. Clustering para experimento 4-320-100-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.24. Clustering para experimento 8-320-100-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.25. Detecci´on de outliers (IQR) para experimento 4-160-50-1 . . . . . . . . . . . . . . . . . . 42 4.26.HistogramasparaCluster1 ................................... 43 4.27.HistogramasparaCluster2 ................................... 43 4.28.HistogramasparaCluster3 ................................... 43 4.29. Detecci´on de outliers (1NN) para experimento 4-160-50-1 . . . . . . . . . . . . . . . . . . 44 4.30. Detecci´on de outliers (3NN) para experimento 4-160-50-1 . . . . . . . . . . . . . . . . . . 45 4.31. Detecci´on de outliers (5NN) para experimento 4-160-50-1 . . . . . . . . . . . . . . . . . . 45 4.32. Detecci´on de outliers (LOF) para experimento 4-160-50-1 . . . . . . . . . . . . . . . . . . 46 4.33. Detecci´on de outliers (LOF e IQR) para experimento 4-160-50-1 . . . . . . . . . . . . . . 48 4.34. Detecci´on de outliers (LOF e IQR) para experimento 4-160-100-1 . . . . . . . . . . . . . 48 4.35. Detecci´on de outliers (LOF e IQR) para experimento 4-320-50-1 . . . . . . . . . . . . . . 49 4.36. Detecci´on de outliers (LOF e IQR) para experimento 4-320-100-1 . . . . . . . . . . . . . 49 4.37. Detecci´on de outliers (Manual e IQR) para experimento 8-160-50-1 . . . . . . . . . . . . 50 6 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez 4.38. Detecci´on de outliers (Manual e IQR) para experimento 8-160-100-1 . . . . . . . . . . . . 50 4.39. Detecci´on de outliers (Manual e IQR) para experimento 8-320-50-1 . . . . . . . . . . . . 51 4.40. Detecci´on de outliers (Manual e IQR) para experimento 8-320-100-1 . . . . . . . . . . . . 51 4.41.LeftModel............................................. 52 4.42.MiddleModel ........................................... 53 4.43.RightModel............................................ 53 A.1. Medida de energ´ıa y tiempos sincronizada. . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 7 ´ Indice de tablas 3.1. Experimentosrealizados...................................... 18 3.2. Etiquetas para cada medida de tiempo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.1. Media de tiempo total en segundos por experimento y fase (1/2) . . . . . . . . . . . . . . 25 4.2. Media de tiempo total en segundos por experimento y fase (2/2) . . . . . . . . . . . . . . 25 4.3. Desviaci´on est´andar de tiempo total en segundos por experimento y fase (1/2) . . . . . . 25 4.4. Desviaci´on est´andar de tiempo total en segundos por experimento y fase (2/2) . . . . . . 25 4.5. Media de energ´ıa total en Wh por experimento y fase (1/2) . . . . . . . . . . . . . . . . . 26 4.6. Media de energia total en Wh por experimento y fase (2/2) . . . . . . . . . . . . . . . . . 26 4.7. Desviaci´on est´andar de energ´ıa total en Wh por experimento y fase (1/2) . . . . . . . . . 26 4.8. Desviaci´on est´andar de energ´ıa total en Wh por experimento y fase (2/2) . . . . . . . . . 26 4.9. Test de hip´otesis (U de Mann-Whitney) para distribuciones de Tiempo. . . . . . . . . . . 35 4.10. Test de hip´otesis (U de Mann-Whitney) para distribuciones de Energ´ıa. . . . . . . . . . . 35 4.11. Test de hip´otesis (U de Mann-Whitney) seg´un poblaci´on para distribuciones de Tiempo. . 36 4.12. Test de hip´otesis (U de Mann-Whitney) seg´un poblaci´on para distribuciones de Energ´ıa. . 36 4.13. Test de hip´otesis (U de Mann-Whitney) seg´un generaciones para distribuciones de Tiempo. 37 4.14. Test de hip´otesis (U de Mann-Whitney) seg´un generaciones para distribuciones de Energ´ıa. 37 4.15. Validaci´on de modelos de predicci´on energ´etica. . . . . . . . . . . . . . . . . . . . . . . . . 54 B.1. Proporci´on de datos seg´un cluster y n´umero de n´ucleos de ejecuci´on . . . . . . . . . . . . 63 B.2. Tiempos m´aximos y m´ınimos seg´un cluster para ejecuci´on en 4 hilos. . . . . . . . . . . . . 63 B.3. Tiempos m´aximos y m´ınimos seg´un cluster para ejecuci´on en 8 hilos. . . . . . . . . . . . . 63 8 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez Algorithm 1 Selecci´on de Caracter´ısticas mediante Paralelizaci´on en Islas 1: procedimiento Parallel NSGAII Feature Selection(N, P) 2: Initialization P(i, N/P, SP (i)) hilos /i = 1, ..., P; 3: wait(i); .Barrera para sincronizar los P hilos. 4: Island evolution(i, N/P, SP(i), commprof, comm, genpar) en hilos /i = 1, ..., P; 5: wait(i); .Barrera para sincronizar los P hilos. 6: NSGAII nondomination sort(SP(1), ..., SP (P)); 7: guardar resultados; 8: end 9: function Initialization(P(i, N/P, SP(i))) 10: (SP(i)) = Initialize population(N, P) 11: f(SP(i)) = Evaluation(SP(i), DS) 12: SP*(i) = NSGAII nondomination sort(SP(i)) 13: function Island evolution(i,N/P, SP(i), commprof, comm, genpar) 14: for j = 1 to comm do 15: for k = 1 to genpar do 16: (SP’(i), f(SP’(i))) = NSGAII tournament selection(SP(i), f(SP(i)); 17: SP”(i) = Genetic operators(SP’(i)); 18: f(SP”(i)) = Evaluation(SP”(i), DS); 19: (SP*(i)) = NSGAII nondomination sort(SP(i), SP”(i)); 20: (SP, f(SP)) = NSGAII replace chromosome (SP*(i)); 21: communication(SP(1), ..., SP(P), commprof); 22: end en el Algoritmo 1. El procedimiento descrito en la l´ınea 1, primero crea Philos con la funci´on Initialization y distribuye los Nindividuos en Psubpoblaciones SP en la l´ınea 2. Estos Philos son sincronizados a trav´es de una barrera en la l´ınea 3 para realizar la evoluci´on de las Psubpoblaciones con la funci´on Island evolution de la l´ınea 4. Cada hilo requiere conocer el n´umero de comunicaciones comm, el n´umero de generaciones que la subpoblaci´on correspondiente tiene que completar entre las comunicaciones genpar, y las parejas de hilos commprof seleccionados al azar que se tienen que comunicar despu´es de cada genpar n´umero de generaciones. Este procedimiento paralelo evolutivo y multiobjetivo, cuyo comportamiento es diferente del secuencial, permite mejorar la calidad de las soluciones encontradas mediante el uso de y / o reducci´on en el tiempo de computaci´on. La funci´on Initialization descrita a partir de la l´ınea 9 inicializa la poblaci´on con Nindividuos. En la l´ınea 10 a cada individuo se le asignan 30 caracter´ısticas aleatorias de las 3600 disponibles, y adem´as, se distribuyen en Psubpoblaciones SP de N/P individuos. A continuaci´on, s´olo queda evaluar cada uno de los individuos en SP entrenando el modelo con el dataset de entrenamiento DS (l´ınea 11), y construir el frente de Pareto de soluciones no dominantes ordenadas con la funci´on NSGAII nondomination sort, que nos devuelve las mejores soluciones de acuerdo a dos par´ametros de optimizaci´on. En este caso, y para el resto de la memoria, el clasificador ser´a un Linear Disciminant Analisys o LDA, y las funciones de optimizaci´on multiobjetivo f1=accuracy yf2= 1 −Kappa, llegando as´ı a un compromiso entre soluciones con alto acierto pero alto rendimiento de clasificaci´on interclase. A partir de la l´ınea 13 se describe la funci´on Island evolution en la que, para el n´umero de comunicaciones comm establecido (l´ınea 14), se desarrolla la subpoblaci´on un n´umero de generaciones genpar (l´ınea 15). Primero se comparan a todos los individuos de la subpoblaci´on SP con NSGAII tournament selection (l´ınea 16), se les aplican los operadores gen´eticos de cruce y mutaci´on (l´ınea 17) y se eval´uan (l´ınea 18). Realizados estos pasos, puede volver a construirse el frente de Pareto de soluciones no dominadas con NSGAII nondomination sort (l´ınea 19) y, por ´ultimo, reemplazar los peores individuos de cada isla de acuerdo a su evaluaci´on previa (l´ınea 20). Para cada una del n´umero de comunicaciones comm definidas se realiza este bucle genpar veces para finalmente intercambiar individuos entre las islas con communication de acuerdo a las parejas de islas aleatorias definidas en commprof. 15 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez 2.2.2. Selecci´on de caracter´ısticas en BCI con MRA El problema de clasificaci´on de alta dimensionalidad que se examina es la Interfaz Cerebro-Ordenador (BCI) basado en la clasificaci´on de se˜nales de EEG correspondientes a las tareas de im´agenes motoras (MI). Este paradigma BCI utiliza una serie de amplificaciones y atenuaciones de corta duraci´on ocasionadas por el movimiento de extremidades imaginadas, la desincronizaci´on relacionada con eventos (ERD) y la sincronizaci´on relacionada con eventos (ERS). Un sistema de an´alisis por multiresoluci´on MRA [21] aplica una secuencia de sucesivos espacios de aproximaci´on que describen la se˜nal objetivo, siendo as´ı ´utiles siempre que la se˜nal objetivo presente diferentes caracter´ısticas a trav´es de los distintos espacios de aproximaci´on. Los patrones utilizados en este trabajo se construyen, a partir de ensayos EEG, por un procedimiento de extracci´on de caracter´ısticas basado en el MRA descrito en [22]. Cada se˜nal obtenida de cada electrodo contiene varios segmentos a los que un conjunto de ondas se les asignan coeficientes de aproximaci´on. De esta manera, considerando S segmentos, E electrodos y L niveles de wavelets, cada patr´on EEG se caracteriza por 2 ·S·E·Lconjuntos de coeficientes. En el conjunto de datos considerado, registrado en el Laboratorio BCI de la Universidad de Essex, S = 20 segmentos, E = 15 electrodos, y L = 6 niveles. Por lo tanto, 3600 conjuntos de coeficientes wavelet en total en cada patr´on, con 4 a 128 Coeficientes en cada conjunto, caracterizan cada patr´on: un total de 151200 coeficientes. Sin embargo, en [22] s´olo una caracter´ıstica es asignada a cada electrodo y cada nivel de aproximaci´on y detalle, y se obtiene calculando la varianza de la distribuci´on de los coeficientes y normalizando los valores obtenidos entre 0 y 1. De este modo, 2 ·S·E·L= 3600 caracter´ısticas que constituyen cada patr´on. Como el n´umero de patrones para cada sujeto es aproximadamente 180, es obvio que es necesario un m´etodo para la extracci´on de caracter´ısticas m´as importantes. Para caracterizar el desempe˜no del clasificador (LDA en este caso) mientras se ha entrenado o ajustado para un conjunto dado de caracter´ısticas (es decir, un individuo de la poblaci´on), es importante no s´olo tener en cuenta la precisi´on obtenida para el conjunto de entrenamiento, sino tambi´en su capacidad de generalizaci´on, es decir, su precisi´on para instancias no vistas durante el entrenamiento. Por lo tanto, la primera funci´on de coste est´a relacionada con el ´ındice Kappa en el conjunto de datos de formaci´on, que tiene en cuenta la distribuci´on del error por clase que se calcula como (p0−pc)/(1 −pc), siendo p0la proporci´on de coincidencias entre las salidas de clasificaci´on y las etiquetas de los patrones y pc la proporci´on de patrones en los que se espera la coincidencia por azar. La segunda funci´on de coste es la funci´on de p´erdida promedio en un an´alisis de validaci´on cruzada de 10 veces a los patrones de entrenamiento. 2.3. Parallel Computing Toolbox de MATLAB Para la implementaci´on de este algoritmo en MATLAB se ha aprovechado la Parallel Computing Toolbox, concretamente, el conjunto de ´ordenes orientado a programaci´on Single Program Multiple Data o SPMD dentro de los Communication Jobs, necesario para la migraci´on de soluciones entre islas propuesta [23]. La forma de lanzar estos programas es la siguiente: 1. Definir perfil de trabajo, en nuestro caso ‘SPMD’. 2. Seleccionar los hilos o cores donde ejecutar, es decir, definir el n´umero de n´ucleos sobre los que se va a evolucionar la poblaci´on a estudiar. 3. Crear un communicatingJob con createCommunicatingJob donde las tareas puedan comunicarse entre s´ı. 4. Crear una tarea o task con createTask a reproducir en cada uno de los cores indicados. 5. Enviar las tareas a los hilos indicados con submit. 6. Esperar y recoger los resultados con wait. 7. Eliminar las tareas y communicatingJobs lanzadas con delete. Una vez se han lanzado las tareas, una para cada trabajador, se pueden establecer comunicaciones entre ellas. Se utiliza la variable interna labindex para controlar en todo momento qu´e hilo de ejecuci´on se est´a manipulando. La orden labBroadcast(labindexSender, data) manda informaci´on al resto de trabajadores, que deber´an estar a la escucha con la orden labBroadcast(labindexSender). 16 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez As´ı es como est´an sincronizadas las distintas islas del programa sobre las que evoluciona la poblaci´on. Est´an emparejadas dos a dos, lo que hace que cuando se emite un labBroadcast, ambas est´an preparadas y sincronizadas para poder enviar y recibir sus mejores individuos de la poblaci´on. 17 Cap´ıtulo 3 Recogida de datos En este cap´ıtulo se recoge la metodolog´ıa seguida para la recogida de los datos. 3.1. Metodolog´ıa La recogida de datos se ha efectuado en el cluster HPMOON de la Universidad de Granada. Concretamente, se ha utilizado el nodo compute-0-1 con un procesador Intel Xeon E5-2620 v4 (2.1 GHz) 8 cores x 2 threads/core, 32 GBytes de memoria RAM, NVS 315 y Tesla K40m. Utiliza Ubuntu con kernel 3.10.0-327.36.3.el7.x86 64 con los programas MATLAB R2014a (8.3.0.532) 64-bit (glnxa64) y Python 2.7.5. Se han ejecutado 10 repeticiones de cada uno de los experimentos mostrados en la Tabla 3.1, correspondiendo su nombre al esquema threads-population-generations-communications. Se ha estudiado en todo momento el poblema con una ´unica comunicaci´on para tratar de modelar los aspectos m´as b´asicos del algoritmo: su distribuci´on en 4 u 8 hilos, una mayor o menor poblaci´on (160-320), y la evoluci´on durante m´as o menos generaciones (50-100). Tabla 3.1: Experimentos realizados. # Experimento # Experimento #1 4-160-50-1 #5 4-320-50-1 #2 8-160-50-1 #6 8-320-50-1 #3 4-160-100-1 #7 8-320-100-1 #4 8-160-100-1 #8 8-320-100-1 3.2. Medidas de tiempo en runtime Para medir el tiempo en MATLAB se ha utilizado la orden clock para ir determinando los tiempos, midiendo el tiempo inicial tiy compar´andolo con etime a cada medida posterior realizada. Las medidas de tiempo se han realizado de manera simult´anea e independiente para cada hilo de ejecuci´on. En la Tabla 3.2 se muestran las etiquetas para cada uno de los tiempos medidos para las fases del algoritmo NSGAII adaptado a paralelizaci´on en hebras y para las ´ordenes de la Parallel Computing Toolbox de MATLAB [23]. En la Figura 3.1 se muestra un esquema general del algoritmo; en las Figuras 3.2 y 3.3 se desarrollan los bloques Initialization yEvolution de las Figuras 3.1a y 3.1b, respectivamente. Tabla 3.2: Etiquetas para cada medida de tiempo. Etiqueta Fase NSGAII-Islands Etiqueta Orden MATLAB 00 Inicializaci´on -1 Evaluaci´on 11 createCommunicationJob 02 Ordenaci´on no dominada 12 createTask 03 Selecci´on por torneo 13 submit 04 Operaciones gen´eticas 14 wait 05 Reemplazo de soluciones 16 labSend +labReceive 18 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez createCommunicationJob CLOCK 11 createTask CLOCK 12 submit wait delete INITIALIZATION initialize_clas_tasks.m CLOCK 00 CLOCK 13 CLOCK 14 START ISLANDS F. SELECTION (1/2) hpmoon_islands_classifier_time.m END (a) Parte 1: Inicializaci´on de la poblaci´on. START ISLANDS F. SELECTION (2/2) hpmoon_islands_classifier_time.m createCommunicationJob CLOCK 11 createTask CLOCK 12 submit wait CLOCK 02 delete EVOLUTION spmd_islands_clas.m CLOCK 13 NON DOMINATION SORT non_domination_sort_mod.m CLOCK 14 END (b) Parte 2: Evoluci´on de la poblaci´on. Figura 3.1: Diagrama de flujo: extracci´on de caracter´ısticas mediante paralelizaci´on en Islas. START INITIALIZATION initialize_tasks_clas.m CLOCK 13 CLASSIFIER (LDA) evaluate_classifier.m CLOCK 00 INITIALIZE POPULATION initialize_clas.m NON DOMINATION SORT non_domination_sort_mod.m CLOCK -1 END CLOCK 02 Figura 3.2: Subrutina: inicializaci´on de la poblaci´on. 19 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez START EVOLUTION spmd_islands_clas.m CLOCK 13 CLASSIFIER (LDA) evaluate_classifier.m CLOCK 04 FOR LOOP j_comm = 1; j_comm < comm; j_comm++ FOR LOOP i_gen = 1; i_gen < gen; i_gen++ TRUE TOURNAMENT tournament_selection.m GENETICS genetic_operator_island.m NON DOMINATION SORT non_domination_sort_mod.m CLOCK 03 CLOCK -1 REPLACE SOLUTIONS replace_chromosome.m CLOCK 02 TRUE MIGRATIONS labBarrier; labSend; labReceive; FALSE FALSE END CLOCK 16 Figura 3.3: Subrutina: evoluci´on de la poblaci´on. 20 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez 3.3. Medida de energ´ıa La medida de energ´ıa se ha hecho a trav´es de un dispositivo Arduino Mega directamente en los nodos del cluster HPMOON, instalado por el departamento de Arquitectura y Tecnolog´ıa de Computadores de la Universidad de Granada (Figura 3.5). Esta medida se realiza a trav´es de sensores que indican la intensidad de corriente que circula en el cable de corriente que conecta el equipo a la red el´ectrica, es decir, se est´a midiendo el consumo real de todo el nodo, incluyendo tanto componentes activos como el de p´erdidas en el transformador de corriente alterna a corriente continua. Figura 3.4: Arduino Mega y sensores de corriente El sistema de medida est´a compuesto de una placa de Arduino Mega y cuatro sensores (uno para cada nodo del cluster HPMOON) para medir su potencia instant´anea en Wy su consumo energ´etico acumulado en W·h. El sensor utilizado es el YHDC-SCTD010T-5A y puede medir hasta 5A con una salida proporcional entre 0 y 5V con una precisi´on del ±2 %. Arduino cuenta con un conversor A/D interno de 10 bits y, para aprovechar mejor su rango din´amico, se utiliza su referencia interna a 2.56V tan s´olo disponible en Arduino Mega. La frecuencia de muestreo es te´oricamente de 1Hz, aunque en la pr´actica ha resultado ser algo menor, detalle que afectar´a a la hora de unir las medidas de tiempo con las de energ´ıa. Se explica m´as adelante dentro de este mismo cap´ıtulo. Arduino Mega se conecta a uno de los nodos del cluster por USB para suministrarle corriente y as´ı poder recoger los datos mediante conexi´on TCP local que se distribuyen desde el puerto 5214. El programa de recogida de datos est´a escrito en Python y su c´odigo fuente est´a en la p´agina 59. Figura 3.5: Diagrama interno de sensor de corriente YHDC-SCTD010T-5A. Para medir correctamente el impacto de la ejecuci´on del algoritmo gen´etico en el consumo energ´etico del cluster, en primer lugar, se mide el consumo medio por segundo del nodo compute-0-1, exclusivamente ejecutando el sistema operativo, para poder sustraerlo posteriormente a las medidas tomadas durante la ejecuci´on del programa. El resultado de la que llamaremos ∆ ¯ ESO que se obtiene despu´es de recoger 4764 21 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez muestras (m´as de 1h de tiempo), corresponde al consumo de energ´ıa en algo m´as de 1s de tiempo, y es de : ∆¯ ESO = (65,38 ±0,08) W·h(3.1) Suponiendo que el consumo energ´etico total ETse puede expresar como la suma del consumo del sistema operativo m´as el consumo del algoritmo entonces podemos calcular la energ´ıa consumida exclusivamente por el mismo: ET=ESO +EAlg (3.2) EAlg =ET−ESO (3.3) Para el caso, nos interesa modelar las medidas de tiempo y energ´ıa como incrementales para poder as´ı tener una nube de puntos a partir de la cual extraer conocimiento. Reformulamos la Ecuaci´on 3.3 en forma de incrementos: ∆EAlg = ∆ET−∆¯ ESO (3.4) Ahora es necesario sincronizar las medidas de tiempo con las de energ´ıa y, para ello, hay que tener en cuenta que la frecuencia de muestreo original es algo inferior a 1Hz. Primero en 3.5 se define un desfase (delay) entre el tiempo total medido por MATLAB (timeElapsed) y el tiempo medido por Arduino Mega (energyTimeMeasured). A continuaci´on, en 3.6 se define realtime como el tiempo medido por MATLAB (runtime) menos la parte proporcional a ese desfase introducido en la muestra. delay =timeElapsed −energyTimeMeasured (3.5) realtime(i) = runtime(i+ 1) −delay ∗runtime(i+ 1) timeElapsed (3.6) Este vector de tiempos realtime sincroniza ambas medidas, de tiempos de ejecuci´on del algoritmo y de energ´ıa consumida, as´ı que sirve tambi´en para poder realizar la estimaci´on energ´etica utilizando una aproximaci´on de integral por trapecios. En la Figura 3.6 se desarrolla el diagrama de flujo para la sincronizaci´on de medidas y estimaci´on energ´etica mencionadas para cada n´ucleo de ejecuci´on. Por ´ultimo, en el Ap´endice A se expone, acompa˜nado de c´odigo y una menci´on m´as detallada de los scripts utilizados, c´omo se he realizado la sincronizaci´on entre las medidas de energ´ıa con Arduino y las medidas de tiempos en MATLAB. 22 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez START PREPARE_PATH energy_profile_isands.m FOR LOOP w = 1; w <= WORKERS; w++ TRUE DELTA-ENERGY ESTIMATION Integrates energy measurement with realtime(i) FREQUENCY ADJUSTMENT delay = timeElapsed - energyTimeMeasured realtime(i) = runtime(i+1) - delay * runtime(i+1)/timeElapsed FALSE END DIFFERENCIATE RUNTIME diffRuntime = diff(runtime) Figura 3.6: Preprocesamiento de datos de tiempo y energ´ıa. 23 Cap´ıtulo 4 An´alisis de los datos En este cap´ıtulo se detalla el an´alisis realizado a los datos. Primero se exponen todos los datos recogidos de forma detallada seg´un la fase del algoritmo, y se les aplican tests de hip´otesis entre las distribuciones generadas. A continuaci´on, se muestran los resultados de aplicar clustering y detecci´on de anomal´ıas y, por ´ultimo, se realiza la construcci´on y validaci´on del modelo de predicci´on de consumo energ´etico. 4.1. Datos de tiempo y consumo energ´etico En primer lugar, vamos a fijarnos en la distribuci´on de tiempos y consumo energ´etico para cada uno de los experimentos. A partir de ahora, los distintos experimentos van a ir refiri´endose con la nomenclatura threads-pop-gen-comm. As´ı, por ejemplo, el experimento 4-160-50-1 corresponde al ejecutado en 4 hilos (procesadores en este caso), 160 individuos, 50 generaciones y una comunicaci´on entre procesos. Se presenta en las Tablas 4.1 - 4.8 un resumen de los datos con las medias y desviaciones est´andar de los tiempos y energ´ıa de cada uno de los experimentos; adem´as, en las Figuras 4.1 - 4.16 puede verse la distribuci´on de tiempo y energ´ıa en cada uno de ellos. En dichas Figuras puede verse la gran importancia de la evaluaci´on de los individuos a nivel de consumo energ´etico y de tiempo, en colores rojo y azul, respectivamente. Los histogramas est´an en escala logar´ıtmica para favorecer la visualizaci´on de tan distintas proporciones. Calculando su proporci´on media respecto a las distintas fases, en todos los experimentos, se puede concluir lo siguiente: La evaluaci´on de los individuos representa, frente al total, el 96.65 % del tiempo de ejecuci´on, y el 97.07 % del consumo energ´etico total. Teniendo en cuenta ese gran peso de la evaluaci´on, es mucho mejor distribuir la carga de la misma entre el m´aximo n´umero de n´ucleos disponibles. Ejecutar un algoritmo en 8 n´ucleos consume de media el 57.40 % del tiempo, y el 71.26 % de la energ´ıa de lo que supone lanzarlo en 4 . La aplicaci´on de operadores gen´eticos (GenOp) y del reemplazo generaci´on tras generaci´on (Replace) es mucho m´as robusta en 4 que en 8 procesadores. En las Tablas 4.3, 4.4, 4.7 y 4.8 puede verse c´omo las desviaciones est´andar son tan peque˜nas que, computacionalmente, valen cero para el tiempo, y pr´acticamente cero para la energ´ıa. La desviaci´on est´andar de las funciones internas de MATLAB CreateCommJob yCreateTask es pr´acticamente nula a nivel energ´etico y de tiempo. Dada la importancia de la fase de evaluaci´on de la poblaci´on, a partir de ahora los esfuerzos de an´alisis de datos se van a centrar en los datos referentes a esta fase del algoritmo. 24 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez 12345678910 10−6 10−5 10−4 10−3 10−2 10−1 100 101 102 Eval Init NonDomSortTournament GenOp ReplaceCreateCommJob CreateTask Submit Wait Energy distribution for runtime−island−clas−4320501 Algorithm steps Total energy (Wh) Figura 4.9: Distribuci´on energ´etica para experimento 4-320-50-1 12345678910 10−3 10−2 10−1 100 101 102 103 104 Eval Init NonDomSort Tournament GenOp Replace CreateCommJob CreateTask Submit Wait Time distribution for runtime−island−clas−4320501 Algorithm steps Total time (s) Figura 4.10: Distribuci´on de tiempo para experimento 4-320-50-1 31 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez 12345678910 10−6 10−5 10−4 10−3 10−2 10−1 100 101 102 Eval Init NonDomSort Tournament GenOp ReplaceCreateCommJob CreateTask Submit Wait Energy distribution for runtime−island−clas−8320501 Algorithm steps Total energy (Wh) Figura 4.11: Distribuci´on energ´etica para experimento 8-320-50-1 12345678910 10−3 10−2 10−1 100 101 102 103 104 Eval Init NonDomSort Tournament GenOp Replace CreateCommJob CreateTask Submit Wait Time distribution for runtime−island−clas−8320501 Algorithm steps Total time (s) Figura 4.12: Distribuci´on de tiempo para experimento 8-320-50-1 32 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez 12345678910 10−6 10−5 10−4 10−3 10−2 10−1 100 101 102Eval Init NonDomSortTournament GenOp ReplaceCreateCommJobCreateTask Submit Wait Energy distribution for runtime−island−clas−43201001 Algorithm steps Total energy (Wh) Figura 4.13: Distribuci´on energ´etica para experimento 4-320-100-1 12345678910 10−3 10−2 10−1 100 101 102 103 104Eval Init NonDomSort Tournament GenOp Replace CreateCommJob CreateTask Submit Wait Time distribution for runtime−island−clas−43201001 Algorithm steps Total time (s) Figura 4.14: Distribuci´on de tiempo para experimento 4-320-100-1 33 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez 12345678910 10−6 10−5 10−4 10−3 10−2 10−1 100 101 102 Eval Init NonDomSort Tournament GenOp ReplaceCreateCommJob CreateTask Submit Wait Energy distribution for runtime−island−clas−83201001 Algorithm steps Total energy (Wh) Figura 4.15: Distribuci´on energ´etica para experimento 8-320-100-1 12345678910 10−3 10−2 10−1 100 101 102 103 104 Eval Init NonDomSort Tournament GenOp Replace CreateCommJob CreateTask Submit Wait Time distribution for runtime−island−clas−83201001 Algorithm steps Total time (s) Figura 4.16: Distribuci´on de tiempo para experimento 8-320-100-1 34 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez 4.2. Tests estad´ısticos seg´un experimento En esta secci´on se van a realizar tests de hip´otesis entre los ocho experimentos realizados para contrastar diferencias entre cada una de las fases del algoritmo seg´un el n´umero de hilos, la poblaci´on a evaluar y el n´umero de generaciones. Se trata de muestras independientes que no presentan normalidad, por ello, se utiliza el test U de Mann-Whitney. 4.2.1. Test seg´un n´umero de hilos Se plantean las siguientes hip´otesis H0 y H1. H0: Las muestras para los experimentos ejecutados en 4 y 8 hilos pertenecen a la misma distribuci´on. H1: Las muestras para los experimentos ejecutados en 4 y 8 hilos provienen de distribuciones diferentes. Los resultados del test se encuentran en la Tabla 4.9 para las distribuciones de tiempo, y en la Tabla 4.10 para las de energ´ıa. El contraste de hip´otesis es el siguiente: H0 se rechaza para las fases Evaluation, Init, NonDomSort, Tournament, GenOp, Replace, CreateCommJob ySubmit. Esto arroja el importante resultado de que la evaluaci´on de los individuos, inicializaci´on, ordenaci´on y la aplicaci´on de operadores gen´eticos difieren al hacerlo en 4 o en 8 n´ucleos. Esto mismo ocurre con las ´ordenes de MATLAB para crear el trabajo de comunicaci´on y su env´ıo. Todo esto encaja perfectamente con lo que se ten´ıa previsto, ya que todos estos procesos vienen directamente ligados a la subpoblaci´on con N/P individuos de cada hilo. H0 se cumple para las fases CreateTask yWait. Del mismo modo, era un resultado previsto ya que son funciones internas de MATLAB a nivel de creaci´on del proceso y sincronizaci´on final. Tabla 4.9: Test de hip´otesis (U de Mann-Whitney) para distribuciones de Tiempo. p-valores Evaluation 3.95 ·10−03*** Replace 1.44 ·10−14*** Init 1.43 ·10−14*** CreateCommJob 3.77 ·10−06*** NonDomSort 1.07 ·10−04*** CreateTask 3.63 ·10−01 Tournament 4.37 ·10−10*** Submit 2.18 ·10−13*** GenOp 1.44 ·10−14*** Wait 5.87 ·10−01 Tabla 4.10: Test de hip´otesis (U de Mann-Whitney) para distribuciones de Energ´ıa. p-valores Evaluation 3.95 ·10−03*** Replace 4.41 ·10−12*** Init 1.61 ·10−07*** CreateCommJob 7.37 ·10−03*** NonDomSort 1.92 ·10−04*** CreateTask 9.50 ·10−01 Tournament 1.44 ·10−14*** Submit 1.44 ·10−14*** GenOp 6.21 ·10−11*** Wait 2.02 ·10−01 4.2.2. Test seg´un n´umero de individuos en la poblaci´on Se plantean las siguientes hip´otesis H0 y H1. H0: Las muestras para los experimentos ejecutados sobre 160 o 320 individuos pertenecen a la misma distribuci´on. H1: Las muestras para los experimentos ejecutados sobre 160 o 320 individuos provienen de distribuciones diferentes. Los resultados del test se encuentran en la Tabla 4.11 para las distribuciones de tiempo, y en la Tabla 4.12 para las de energ´ıa. El contraste de hip´otesis es el siguiente: 35 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez H0 se rechaza para las fases Evaluation yNonDomSort tanto en tiempo como consumo energ´etico. Esto quiere decir que, como cab´ıa esperar, para distintos n´umeros de individuos en la poblaci´on, el consumo energ´etico y el tiempo utilizado difieren tanto para el proceso de evaluaci´on como de ordenaci´on no-dominante. Tambi´en puede verse que H0 se rechaza para Wait en tiempo de ejecuci´on, aunque esto puede ser simplemente debido a ruido en las medidas, se trata de una funci´on interna de MATLAB sobre la que no se tiene control. H0 se cumple para el resto de pasos del algoritmo, en consumo energ´etico y de tiempo. Esto arroja el importante resultado de que la diferencia de poblaci´on propuesta no afecta a los pasos de inicializaci´on, selecci´on por torneo, aplicaci´on de operadores gen´eticos ni reemplazo. Estos resultados encajan con el paradigma SPMD implementado en el algoritmo Las funciones de MATLAB que generan el proceso de comunicaci´on entre hilos, las tareas y su env´ıo tampoco se ven afecatadas. Tabla 4.11: Test de hip´otesis (U de Mann-Whitney) seg´un poblaci´on para distribuciones de Tiempo. p-valores Evaluation 1.10 ·10−10*** Replace 5.16 ·10−01 Init 7.80 ·10−01 CreateCommJob 6.55 ·10−01 NonDomSort 1.92 ·10−11*** CreateTask 4.05 ·10−01 Tournament 4.11 ·10−01 Submit 5.22 ·10−01 GenOp 9.35 ·10−01 Wait 1.59 ·10−05*** Tabla 4.12: Test de hip´otesis (U de Mann-Whitney) seg´un poblaci´on para distribuciones de Energ´ıa. p-valores Evaluation 2.52 ·10−02*** Replace 6.34 ·10−01 Init 7.25 ·10−01 CreateCommJob 8.06 ·10−01 NonDomSort 2.06 ·10−02*** CreateTask 8.89 ·10−01 Tournament 6.13 ·10−01 Submit 9.35 ·10−01 GenOp 6.20 ·10−01 Wait 1.70 ·10−01 4.2.3. Test seg´un n´umero de generaciones Se plantean las siguientes hip´otesis H0 y H1. H0: Las muestras para los experimentos ejecutados durante 50 y 100 generaciones pertenecen a la misma distribuci´on. H1: Las muestras para los experimentos ejecutados durante 50 y 100 generaciones provienen de distribuciones diferentes. Los resultados del test se encuentran en la Tabla 4.13 para las distribuciones de tiempo, y en la Tabla 4.14 para las de energ´ıa. El contraste de hip´otesis es el siguiente: H0 se rechaza para Evaluation, NonDomSort yReplace tanto en tiempo como en energ´ıa, es decir, tan s´olo estas tres partes del proceso se ven afectadas por haber duplicado el n´umero de generaciones de 50 a 100. Adem´as, H0 tambi´en se rechaza para Wait en cuanto a distribuciones de tiempo. H0 se acepta para el resto de partes del algoritmo. El proceso de inicializaci´on (Init) no sufre diferencias dependiendo del n´umero de generaciones a evolucionar, tal y c´omo se esperaba, pero se puede destacar que las fases de selecci´on por torneo (Tournament) y aplicaci´on de operadores gen´eticos (GenOp) tampoco lo han hecho. Esto puede explicarse por el ´ınfimo coste energ´etico y de tiempo que estas fases llevan, adem´as de venir implementadas como SIMD/SPMD, junto a las altas desviaciones est´andar que presentan respecto a sus media. 36 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez Tabla 4.13: Test de hip´otesis (U de Mann-Whitney) seg´un generaciones para distribuciones de Tiempo. p-valores Evaluation 3.67 ·10−07*** Replace 1.86 ·10−02*** Init 4.88 ·10−01 CreateCommJob 7.47 ·10−01 NonDomSort 2.33 ·10−04*** CreateTask 4.00 ·10−01 Tournament 4.16 ·10−01 Submit 5.41 ·10−01 GenOp 1.11 ·10−01 Wait 4.54 ·10−06*** Tabla 4.14: Test de hip´otesis (U de Mann-Whitney) seg´un generaciones para distribuciones de Energ´ıa. p-valores Evaluation 4.27 ·10−07*** Replace 3.09 ·10−03*** Init 6.00 ·10−01 CreateCommJob 7.18 ·10−01 NonDomSort 5.42 ·10−05*** CreateTask 2.09 ·10−01 Tournament 8.66 ·10−01 Submit 8.81 ·10−01 GenOp 1.67 ·10−01 Wait 1.40 ·10−05 4.3. Clustering y detecci´on de anomal´ıas Como se ha visto en el apartado anterior, la evaluaci´on de los individuos supone el grueso en tiempo y energ´ıa del desarrollo del algoritmo. Por ello, a continuaci´on, se presentan los resultados de aplicar clustering mediante el algoritmo de las k-medias [24] a ese conjunto de datos (Figuras 4.17 - 4.24), con los siguientes objetivos: 1. Clasificaci´on de los distintos comportamientos encontrados. 2. Detecci´on de anomal´ıas (outliers) Los experimentos realizados en 4 hilos han sido distribuidos en 3 clusters, mientras que los que se han desarrollado en 8 hilos se han distribuido perfectamente s´olo en 2. Esto es as´ı por la evidente presencia de dos comportamientos crecientes ∆tiempo −∆energ´ ia superpuestos que parecen provocar una generaci´on de un cluster intermedio extra en los experimentos ejecutados en 4 hilos, quedando a la izquierda un ´unico comportamiento creciente, en medio dos comportamientos crecientes superpuestos, y a la derecha un cl´uster disperso de datos. Para 8 n´ucleos estos dos clusters quedan perfectamente definidos como uno a la izquierda compacto y otro a la derecha disperso. Como hip´otesis de esta diferencia sustancial en la distribuci´on de los datos para 4 y 8 n´ucleos se plantean varias casu´ısticas, desde la presencia de cambios de contexto en la ejecuci´on del algoritmo (al no ocuparse todos los n´ucleos, se favorecen los cambios de contexto desde la propia gesti´on del sistema operativo) hasta fallos de cach´e, requiriendo as´ı accesos a memoria principal (distribuir la poblaci´on en 4 hilos en lugar de 8 implicar´ıa la formaci´on de subpoblaciones m´as grandes con las que lidiar). Estas hip´otesis quedan a´un pendientes de validar una vez se realicen las pruebas con una mayor recogida de datos a nivel de kernel mediante herramientas como PERF. Adem´as, hay que tener en cuenta tambi´en las capas extra que a˜nade MATLAB (y Java por detr´as) dentro de la gesti´on del programa. Otro comportamiento curioso se presenta en la Figura 4.18 donde la distribuci´on tiene el doble de “anchura”que el resto de experimentos desarrollados con 4 y 8 hilos. Por ello, se dejar´a fuera de la elaboraci´on del modelo en apartados posteriores. A continuaci´on, en los siguientes subapartados, se van a ir desarrollando los diferentes m´etodos de detecci´on y eliminaci´on de anomal´ıas probados. 37 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez 1.5 2 2.5 3 3.5 4 4.5 5 0.005 0.01 0.015 0.02 0.025 0.03 0.035 0.04 ∆ time (s) ∆ energy (Wh) Clustering k−medias para runtime−island−clas−4160501 Cluster 1 Cluster 2 Cluster 3 Centroides Figura 4.17: Clustering para experimento 4-160-50-1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 0 0.01 0.02 0.03 0.04 0.05 0.06 ∆ time (s) ∆ energy (Wh) Clustering k−medias para runtime−island−clas−8160501 Cluster 1 Cluster 2 Centroides Figura 4.18: Clustering para experimento 8-160-50-1 38 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez Figura 4.19: Clustering para experimento 4-160-100-1 Figura 4.20: Clustering para experimento 8-160-100-1 39 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez 1.5 2 2.5 3 3.5 4 0 0.005 0.01 0.015 0.02 0.025 0.03 0.035 0.04 ∆ time (s) ∆ energy (Wh) Clustering k−medias para runtime−island−clas−4320501 Cluster 1 Cluster 2 Cluster 3 Centroides Figura 4.21: Clustering para experimento 4-320-50-1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 0.01 0.02 0.03 0.04 0.05 0.06 0.07 ∆ time (s) ∆ energy (Wh) Clustering k−medias para runtime−island−clas−8320501 Cluster 1 Cluster 2 Centroides Figura 4.22: Clustering para experimento 8-320-50-1 40 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez Cluster 1: Cluster disperso. La selecci´on no es buena, hay puntos dispersos que no han sido seleccionados. Umbral LOF mayor que 3. Cluster 2: Cluster con combinaci´on de comportamientos. La selecci´on de outliers no es buena para distintos umbrales de LOF. Se muestran outliers con LOF mayores que 40. Cluster 3: Cluster de comportamiento ´unico. La selecci´on de outliers en este caso es suficientemente buena, eliminando aquellos puntos claramente fuera del cluster. Se ha seleccionado el m´ınimo umbral necesario LOF que abarcase a los cinco outliers referidos, consecuentemente, eliminando otros dos puntos en la parte superior del cluster. Umbral LOF mayor que 300. LOF se erige como la soluci´on para estudiar los “Cluster 3” de cada uno de los experimentos ejecutados en cuatro hilos y los “Cluster 2” de los ejecutados en 8 hilos. El resto ser´an procesados mediante detecci´on de outliers IQR. 4.3.4. Detecci´on de anomal´ıas mediante selecci´on manual, LOF e IQR A continuaci´on se utilizan los m´etodos de detecci´on LOF e IQR en los distintos cl´usteres que aparecen en cada uno de los experimentos. Para cada uno de ellos, la kescogida dentro de LOF var´ıa seg´un la naturaleza del cluster. En ellos puede observarse variabilidad de densidades, por lo que es muy importante afinar bien este par´ametro. Hay casos en los que esto no es posible por culpa de la alta heterogeneidad de densidades en la agrupaci´on de los datos; en ellos se ha realizado una selecci´on manual. A continuaci´on se exponen las peculiaridades de cada experimento: Los experimentos ejecutados en 4 hilos, mostrados en las Figuras 4.33 - 4.36, mantienen una estructura similar en todo momento. La detecci´on de outliers con IQR en los clusters 1 y 2 de cada uno de ellos funciona bastante bien; con LOF, en los clusters 3, hay que ser m´as preciso, puesto que el n´umero de vecinos es crucial para hacer una correcta detecci´on de los outliers a nivel local. Esto junto a la densidad no homog´enea del cluster 1 (ver Figura 4.28b) hace que, incluso encontrando el valor de k ´optimo, haya algunos pocos falsos positivos inevitables en la detecci´on. Los experimentos ejecutados en 8 hilos no han permitido el correcto uso de LOF en la detecci´on de anomal´ıas por la alta heterogeneidad de densidades en los mismos, por lo que finalmente ha sido un ajuste manual (Figuras 4.37 - 4.40). Esto ha permitido la disecci´on de unos clusters muy compactos que permitir´an una modelizaci´on posterior m´as robusta. Cabe destacar c´omo IQR ha eliminado pocos o ning´un punto dentro de las distribuciones de los clusters 1. 47 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez 1.5 2 2.5 3 3.5 4 4.5 5 0.005 0.01 0.015 0.02 0.025 0.03 0.035 0.04 ∆ time (s) ∆ energy (Wh) LOF3−IQR outlier removal for runtime−island−clas−4160501− Cluster 1 Cluster 2 Cluster 3 Centroids Outliers Figura 4.33: Detecci´on de outliers (LOF e IQR) para experimento 4-160-50-1 1.5 2 2.5 3 3.5 4 4.5 0.005 0.01 0.015 0.02 0.025 0.03 0.035 0.04 ∆ time (s) ∆ energy (Wh) LOF3−IQR outlier removal for runtime−island−clas−41601001− Cluster 1 Cluster 2 Cluster 3 Centroids Outliers Figura 4.34: Detecci´on de outliers (LOF e IQR) para experimento 4-160-100-1 48 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez 1.5 2 2.5 3 3.5 4 0 0.005 0.01 0.015 0.02 0.025 0.03 0.035 0.04 ∆ time (s) ∆ energy (Wh) LOF3−IQR outlier removal for runtime−island−clas−4320501− Cluster 1 Cluster 2 Cluster 3 Centroids Outliers Figura 4.35: Detecci´on de outliers (LOF e IQR) para experimento 4-320-50-1 1.5 2 2.5 3 3.5 4 0 0.005 0.01 0.015 0.02 0.025 0.03 0.035 ∆ time (s) ∆ energy (Wh) LOF6−IQR outlier removal for runtime−island−clas−43201001− Cluster 1 Cluster 2 Cluster 3 Centroids Outliers Figura 4.36: Detecci´on de outliers (LOF e IQR) para experimento 4-320-100-1 49 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez 1.5 2 2.5 3 3.5 4 4.5 5 5.5 0 0.01 0.02 0.03 0.04 0.05 0.06 ∆ time (s) ∆ energy (Wh) Manual−IQR outlier removal for runtime−island−clas−8160501− Cluster 1 Cluster 2 Centroids Outliers Figura 4.37: Detecci´on de outliers (Manual e IQR) para experimento 8-160-50-1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 ∆ time (s) ∆ energy (Wh) Manual−IQR outlier removal for runtime−island−clas−81601001− Cluster 1 Cluster 2 Centroids Outliers Figura 4.38: Detecci´on de outliers (Manual e IQR) para experimento 8-160-100-1 50 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez 1.5 2 2.5 3 3.5 4 4.5 5 5.5 0.01 0.02 0.03 0.04 0.05 0.06 0.07 ∆ time (s) ∆ energy (Wh) Manual−IQR outlier removal for runtime−island−clas−8320501− Cluster 1 Cluster 2 Centroids Outliers Figura 4.39: Detecci´on de outliers (Manual e IQR) para experimento 8-320-50-1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 ∆ time (s) ∆ energy (Wh) Manual−IQR outlier removal for runtime−island−clas−83201001− Cluster 1 Cluster 2 Centroids Outliers Figura 4.40: Detecci´on de outliers (Manual e IQR) para experimento 8-320-100-1 51 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez 4.4. Predicci´on de consumo energ´etico 4.4.1. Construcci´on del modelo Para la construcci´on del modelo se van a utilizar los datos de las 9 primeras repeticiones, una vez eliminadas las anomal´ıas, de los experimentos #1, #3, #4, #5, #6, #7, #8. El experimento #2 (8-16050-1) se ha dejado fuera de la construcci´on dado a la acumulaci´on energ´etica diferenciada en su cluster 2 (ver Figura 4.18). Dado que para 8 n´ucleos apenas existe el comportamiento lineal extra superpuesto al principal, se asumen 3 partes a partir de las cuales se construyen 3 modelos lineales: LeftModel. Modelos entrenado con los datos correspondientes a la “parte izquierda” de las gr´aficas, es decir, a los cluster #2 de los experimentos ejecutados sobre 8 n´ucleos y a los cluster #3 de los ejecutados sobre 4. El modelo se representa en la Figura 4.41. Pueden diferenciarse dos nubes de datos, a la izquierda los de consumo energ´etico para 4 n´ucleos y a la derecha los de ejecuci´on en 8 n´ucleos. Tambi´en puede apreciarse que su car´acter creciente no parece corresponder con la tendencia general de los puntos. Esto es debido a que existe una mayor acumulaci´on de puntos en la frontera superior correspondiente a los experimentos ejecutados sobre 8 n´ucleos. Sin embargo, como el prop´osito es la agregaci´on de las predicciones, este detalle no va a afectar a una posterior predicci´on. MiddleModel. Modelo entrenado exclusivamente para los experimentos ejecutados sobre 4 n´ucleos. Se encarga de representar la parte intermedia de los mismos donde existe una superposici´on de dos comportamientos lineales perfectamente diferenciados a nivel visual, pero que no se pueden separar por carecer de datos referidos a este fen´omeno. El modelo se representa en la Figura 4.42. RightModel. Modelo entrenado con los datos correspondientes a la “parte derecha” de las gr´aficas. Representa a la minor´ıa de datos dispersa agrupada en los cluster #1 de todos los experimentos seleccionados. El modelo se representa en la Figura 4.43. Figura 4.41: LeftModel 52 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez 2 2.05 2.1 2.15 2.2 2.25 2.3 2.35 2.4 2.45 2.5 0.012 0.014 0.016 0.018 0.02 0.022 0.024 0.026 0.028 ∆ time (s) ∆ energy (Wh) MiddleModel Train Regression Line R2 = 0.0089946 εsum = 8.0617e−15 % y = 0.0075852x + 0.0024248 Figura 4.42: MiddleModel 2.5 3 3.5 4 4.5 5 5.5 0.01 0.02 0.03 0.04 0.05 0.06 0.07 ∆ time (s) ∆ energy (Wh) RightModel Train Regression Line R2 = 0.67332 εsum = 6.7863e−16 % y = 0.015749x −0.020016 Figura 4.43: RightModel 53 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez Como puede observare en las figuras de cada modelo, el coeficiente de determinaci´on R2es muy bajo. Esto es debido a que es directamente dependiente de la dispersi´on de los datos originales respecto a la recta de regresi´on. En regresi´on lineal R2se define como el cuadrado del coeficiente de correlaci´on de Pearson: R2=σ2 XY σ2 Xσ2 Y (4.10) Donde: σXY es la covarianza de (X,Y), en nuestro caso, (E,t). σXes la desviaci´on t´ıpica de (X), en nuestro caso, (E). σYes la desviaci´on t´ıpica de (Y), en nuestro caso, (t). Aunque la tendencia de que el consumo energ´etico es directamente proporcional al tiempo empleado es claramente visible, las desviaciones t´ıpicas de ambas variables son demasiado altas como para proporcionar un valor de R2razonable. Especial menci´on a la desviaci´on t´ıpica de la energ´ıa en el cluster 1, donde la acumulaci´on de datos se da en las fronteras (ver Figura 4.28b), por lo que su magnitud es muy relevante y reduce mucho el coeficiente de determinaci´on. Sin embargo, esto no afecta a nuestro objetivo de determinar cu´al va a ser la suma de todos los datos, ya que la dispersi´on es constante en todo momento. 4.4.2. Validaci´on del modelo En la Tabla 4.15 pueden verse los resultados despu´es de haber entrenado el modelo con las repeticiones 1-9, y validar con la repetici´on 10 de cada experimento. Los resultados son buenos y reflejan una media de error relativo entre la predicci´on y el valor real de 1,1925 % Predicci´on (Wh) Real (Wh) Error relativo ( %) Exp. 1-10 79.46 78.33 1.44 Exp. 2-10 109.21 110.77 1.40 Exp. 3-10 152.36 154.93 1.66 Exp. 4-10 220.33 221.55 0.55 Exp. 5-10 159.28 158.11 0.74 Exp. 6-10 224.56 223.65 0.41 Exp. 7-10 301.48 306.58 1.66 Exp. 8-10 430.06 437.40 1.68 Tabla 4.15: Validaci´on de modelos de predicci´on energ´etica. 54 Cap´ıtulo 5 Conclusiones y trabajo futuro 5.1. Conclusiones En este Trabajo de Fin de M´aster se ha elaborado un modelo de predicci´on de consumo energ´etico para el algoritmo gen´etico NSGA-II paralelizado en Islas orientado a la selecci´on de caracter´ısticas en BCI. Para ello, en primer lugar, ha sido necesaria una revisi´on bibliogr´afica de los m´etodos empleados habitualmente en la caracterizaci´on de consumo energ´etico de sistemas y algoritmos. A continuaci´on, se ha estudiado la ´ultima implementaci´on de NSGA-II realizada por Ortega y cols. [1] orientada a la selecci´on de caracter´ısticas en BCI, y el funcionamiento de la misma con la Parallel Computing Toolbox de MATLAB [23] para poder realizar la medida de tiempos de cada una de sus partes a lo largo de su ejecuci´on y sincronizarla con las medidas de consumo energ´etico. De este caso de estudio se ha extra´ıdo lo siguiente: La evaluaci´on de los individuos representa, frente al total, el 96.65 % del tiempo de ejecuci´on, y el 97.07 % del consumo energ´etico total. Teniendo en cuenta ese gran peso de la evaluaci´on, se puede extraer que distribuir la carga de la misma entre el m´aximo n´umero de n´ucleos disponibles. Ejecutar un algoritmo en 8 n´ucleos consume de media el 57.40 % del tiempo, y el 71.26 % de la energ´ıa de lo que supone lanzarlo en 4 . La aplicaci´on de operadores gen´eticos (GenOp) y del reemplazo generaci´on tras generaci´on (Replace) es mucho m´as robusta en 4 que en 8 procesadores. La desviaci´on est´andar de las funciones internas de MATLAB CreateCommJob yCreateTask es pr´acticamente nula a nivel energ´etico y de tiempo. El n´umero de individuos s´olo afecta de forma significativa en los procesos de evaluaci´on y ordenaci´on no dominada. El n´umero de generaciones s´olo afecta de forma significativa en los procesos de evaluaci´on, ordenaci´on no dominada y reemplazo. Se han estudiado y comparado los datos recogidos en todos los experimentos a partir de un an´alisis de clustering con k-medias, infiriendo comportamientos diferentes para la distribuci´on del mismo problema (poblaci´on inicial, generaciones a evolucionar, una comunicaci´on entre islas) entre 4 y 8 n´ucleos. Adem´as, se han comparado distintos m´etodos de detecci´on de outliers basados en IQR, k-NN, distancia a centroide y LOF, obteniendo diferentes resultados seg´un qu´e agrupaci´on de datos se estuviese analizando: LOF ha sido el m´etodo de detecci´on de anomal´ıas m´as exitoso para los experimentos ejecutados en 4 hilos, a pesar de ser muy costoso computacionalmente. Los outliers de los ejecutados en 8 n´ucleos han sido eliminados manualmente. Por ´ultimo, se ha elaborado un modelo de predicci´on de consumo energ´etico para el algoritmo estudiado que depende exclusivamente de par´ametros intr´ınsecos al propio algoritmo. Esto hace que la metodolog´ıa desarrollada a lo largo de la memoria sea f´acilmente exportable y adaptable a otras m´aquinas o algoritmos gen´eticos de los que se quiera desarrollar un modelo de predicci´on energ´etica similar. As´ı, por todo lo expuesto con anterioridad y los resultados obtenidos, este modelo de caja-negra cumple con los objetivos 55 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez 1, 2, 4, 5, 6 y 7 listados en la Subsecci´on 2.1.1: (1) se trata de una aproximaci´on de sistema completo en la que se contempla el comportamiento de todo el sistema como unidad y su respuesta al algoritmo, (2) tiene un error medio de validaci´on del 1.1925 % (4) es gen´erico y portable por no depender de par´ametros internos de la m´aquina sobre la que se ejecuta el algoritmo, y (5,7) el coste de generaci´on y utilizaci´on del modelo se limita a una simple recta de regresi´on para cada tipo de cluster definido en 4 y 8 n´ucleos de ejecuci´on. Respecto a los objetivos 3 y 6, no se puede asegurar su cumplimiento, porque el modelo permite realizar scheduling est´atico, es decir, predicciones antes de la ejecuci´on del programa, y porque no se puede asegurar que la medici´on de tiempos a lo largo del programa no haya alterado el propio flujo del mismo sin ellas, respectivamente. 5.2. Trabajo futuro Como l´ınea de trabajo futuro y continuaci´on directa de este TFM se plantea lo siguiente: 1. Elaborar modelo que incluya eventos internos a nivel de kernel dentro del sistema con herramientas como PERF. Esto ayudar´ıa a tener datos de contadores internos, y adem´as podr´ıa compararse la medida energ´etica obtenida a trav´es de este software con la obtenida a partir de Arduino. 2. Migrar el c´odigo a OpenCL/OpenMP, optimizando el c´odigo y evitando el m´aximo n´umero posible de capas intermediarias en la ejecuci´on del algoritmo (Java en el caso de MATLAB). 3. Estudiar el impacto de la medici´on de tiempos dentro de la ejecuci´on del programa en la predicci´on de consumo energ´etico con el modelo elaborado. 4. Estudiar el impacto en el consumo energ´etico de m´as de una comunicaci´on entre islas. 5. Estudar la relaci´on entre consumo energ´etico y bondad de la soluci´on encontrada. 5.3. Agradecimientos Este trabajo ha sido financiado por el Ministerio de Econom´ıa y Competitividad y los fondos FEDER a trav´es del proyecto TIN2015-67020-P. 56 Ap´endice B Instrucciones para la predicci´on de consumo energ´etico. En primer lugar necesitamos conocer cu´al es la proporci´on de los datos de cada cluster para seg´un qu´e experimento. Se muestran en la Tabla B.1: Cluster 1 ( %) Cluster 2 ( %) Cluster 3 ( %) 4 n´ucleos 0.14 2.43 97.43 8 n´ucleos 0.22 99.78 0.00 Tabla B.1: Proporci´on de datos seg´un cluster y n´umero de n´ucleos de ejecuci´on A continuaci´on, conociendo la proporci´on de la poblaci´on que se va a evaluar como consecuencia de las probabilidades de que un individuo se cruce o sufra una mutaci´on, calculamos el n´umero de evaluaciones que se va a realizar. Evaluaciones =pop ·gen ·f(B.1) Donde: pop: n´umero de individuos de la poblaci´on a evolucionar. gen: n´umero de generaciones a evolucionar la poblaci´on. f: proporci´on de evaluaciones finales tras aplicar probabilidades de cruce y mutaci´on. En este caso f= 0,5851. Ahora, decidiendo si lo vamos a ejecutar en 4 u 8 n´ucleos, hacemos una distribuci´on uniforme con el tanto por ciento correspondiente a cada cluster entre sus valores m´aximos y m´ınimos (Tablas B.2 y B.3). Cluster 1 Cluster 2 Cluster 3 Tiempo min. (s) 1.73 2.03 2.59 Tiempo max. (s) 1.98 2.44 5.15 Tabla B.2: Tiempos m´aximos y m´ınimos seg´un cluster para ejecuci´on en 4 hilos. Cluster 1 Cluster 2 Tiempo min. (s) 1.98 2.59 Tiempo max. (s) 2.30 5.15 Tabla B.3: Tiempos m´aximos y m´ınimos seg´un cluster para ejecuci´on en 8 hilos. 63 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez Por ´ultimo, a cada distribuci´on uniforme se le aplica su modelo de regresi´on y se agregan todas las predicciones para realizar la suma total. En MATLAB el c´odigo a ejecutar ser´ıa el siguiente: 1% @param tmin : tiempo m ni m o s e g n c l u s t e r . % @param tmax : tiempo m x im o s e g n c l u s t e r . 3% @param e v al ua cio n es : n m e r o de e val u ac io nes de acuerdo a l tanto por % c ie nt o de l c l u s t e r es cog i do . 5% @param model : modelo s e g n c l u s t e r , por ejemplo , [ 0 . 02 3 3 0 6 , −0.026047] para c l u s t e r 1 . 7x = tmin + (tmax−tmin ) ∗rand ( eva l u a ci o ne s ) % Vector de tiempos y = polyval( model , x ) 9p r e d i c c i o n = sum( y ) 64 Bibliograf´ıa [1] J. Ortega, D. Kimovski, J. Q. Gan, A. Ortiz, and M. Damas, “A Parallel Island Approach to Multiobjective Feature Selection for Brain-Computer Interfaces,” in International WorkConference on Artificial Neural Networks (IWANN): Advances in Computational Intelligence, vol. 10305. Cham: Springer International Publishing, 2017, pp. 16–27. [Online]. Available: http://link.springer.com/10.1007/978-3-319-59153-7 2 [2] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE transactions on evolutionary computation, vol. 6, no. 2, pp. 182–197, 2002. [Online]. Available: http://ieeexplore.ieee.org/abstract/document/996017/ [3] S. M. Rivoire, “Models and metrics for energy-efficient computer systems,” Ph.D. dissertation, Stanford University, 2008. [Online]. Available: http://search.proquest.com/openview/ ff08fcba635951b94fa064edf55a7b8d/1?pq-origsite=gscholar&cbl=18750&diss=y [4] D. Brooks, V. Tiwari, and M. Martonosi, “Wattch: A Framework for Architectural-level Power Analysis and Optimizations,” in Proceedings of the 27th Annual International Symposium on Computer Architecture, ser. ISCA ’00. New York, NY, USA: ACM, 2000, pp. 83–94. [Online]. Available: http://doi.acm.org/10.1145/339647.339657 [5] “SimpleScalar LLC.” [Online]. Available: http://www.simplescalar.com/ [6] R. H. Arpaci-Dusseau and A. C. Arpaci-Dusseau, “Paging: Faster Translations (TLBs),” in Operating Systems: Three Easy Pieces, 0th ed. Arpaci-Dusseau Books, May 2015. [7] H. Shafi, P. J. Bohrer, J. Phelan, C. A. Rusu, and J. L. Peterson, “Design and validation of a performance and power simulator for powerpc systems,” IBM J. Res. Dev., vol. 47, no. 5-6, pp. 641–651, Sep. 2003. [Online]. Available: http://dx.doi.org/10.1147/rd.475.0641 [8] W. Bakkali, M. Tlich, P. Pagani, and T. Chonavel, “A measurement-based model of energy consumption for PLC modems,” in 18th IEEE International Symposium on Power Line Communications and Its Applications, Mar. 2014, pp. 42–46. [9] R. Azimi, M. Stumm, and R. W. Wisniewski, “Online Performance Analysis by Statistical Sampling of Microprocessor Performance Counters,” in Proceedings of the 19th Annual International Conference on Supercomputing, ser. ICS ’05. New York, NY, USA: ACM, 2005, pp. 101–110. [Online]. Available: http://doi.acm.org/10.1145/1088149.1088163 [10] A. Jaiantilal, Y. Jiang, and S. Mishra, “Modeling CPU energy consumption for energy efficient scheduling,” in Proceedings of the 1st Workshop on Green Computing. ACM, 2010, pp. 10–15. [Online]. Available: http://dl.acm.org/citation.cfm?id=1925015 [11] J. I. Aliaga, M. Barreda, M. F. Dolz, A. F. Martin, R. Mayo, and E. S. Quintana-Orti, “Assessing the impact of the CPU power-saving modes on the task-parallel solution of sparse linear systems,” Cluster Computing, vol. 17, no. 4, pp. 1335–1348, Dec. 2014. [Online]. Available: http://link.springer.com/10.1007/s10586-014-0402-z [12] “Qu´e es C-state |Dell Espa˜na.” [Online]. Available: http://www.dell.com/support/article/es/es/ esdhs1/qna41893/qu%C3%A9-es-c-state?lang=es [13] “What exactly is a P-state? (Pt. 1) |Intel R Software.” [Online]. Available: https: //software.intel.com/en-us/blogs/2008/05/29/what-exactly-is-a-p-state-pt-1 65 An´alisis de Consumo Energ´etico en Algoritmos Gen´eticos Paralelos S. Moreno Guti´errez [14] R. Barik, N. Farooqui, B. T. Lewis, C. Hu, and T. Shpeisman, “A black-box approach to energy-aware scheduling on integrated CPU-GPU systems.” ACM Press, 2016, pp. 70–81. [Online]. Available: http://dl.acm.org/citation.cfm?doid=2854038.2854052 [15] S. Raudys and A. Jain, “Small sample size effects in statistical pattern recognition: recommendations for practitioners,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 13, no. 3, pp. 252–264, 1991. [Online]. Available: http://dataclustering.cse.msu.edu/papers/RaudysJainPAMI91.pdf [16] D. Kimovski, J. Ortega, A. Ortiz, and R. Banos, “Feature selection in high-dimensional EEG data by parallel multi-objective optimization,” in Cluster Computing (CLUSTER), 2014 IEEE International Conference on. IEEE, 2014, pp. 314–322. [Online]. Available: http://ieeexplore.ieee.org/abstract/document/6968782/ [17] D. Kimovski and al., “Leveraging cooperation for parallel multi-objective feature selection in high-dimensional EEG data: Cooperative parallel MOEAs for feature selection in EEG,” Concurrency and Computation: Practice and Experience, vol. 27, no. 18, pp. 5476–5499, Dec. 2015. [Online]. Available: http://doi.wiley.com/10.1002/cpe.3594 [18] D. Kimovski, J. Ortega, A. Ortiz, and R. Banos, “Parallel alternatives for evolutionary multi-objective optimization in unsupervised feature selection,” Expert Systems with Applications, vol. 42, no. 9, pp. 4239–4252, Jun. 2015. [Online]. Available: http://linkinghub.elsevier.com/ retrieve/pii/S0957417415000846 [19] Y. Saeys, I. n. Inza, and P. Larra˜naga, “A review of feature selection techniques in bioinformatics,” Bioinformatics, vol. 23, no. 19, pp. 2507–2517, Oct. 2007. [Online]. Available: https://academic. oup.com/bioinformatics/article/23/19/2507/185254/A-review-of-feature-selection-techniques-in [20] J. Handl and J. Knowles, “Feature subset selection in unsupervised learning via multiobjective optimization,” International Journal of Computational Intelligence Research, vol. 2, no. 3, pp. 217– 238, 2006. [Online]. Available: https://www.researchgate.net/profile/Joshua Knowles/publication/ 228670597 Feature Subset Selection in Unsupervised Learning via Multiobjective Optimization/ links/0912f509274b1d8ea8000000.pdf [21] I. Daubechies, Ten Lectures on Wavelets. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 1992. [22] J. Asensio-Cubero, J. Q. Gan, and R. Palaniappan, “Multiresolution analysis over simple graphs for brain computer interfaces,” Journal of Neural Engineering, vol. 10, no. 4, p. 046014, Aug. 2013. [23] “Parallel Computing Toolbox Documentation - MathWorks Espa˜na.” [Online]. Available: https://es.mathworks.com/help/distcomp/ [24] S. Lloyd, “Least squares quantization in PCM,” IEEE Transactions on Information Theory, vol. 28, no. 2, pp. 129–137, Mar. 1982. [25] W. H. Swallow and F. Kianifard, “Using Robust Scale Estimates in Detecting Multiple Outliers in Linear Regression,” Biometrics, vol. 52, no. 2, pp. 545–556, 1996. [Online]. Available: http://www.jstor.org/stable/2532894 [26] B. W. Silverman and M. C. Jones, “E. Fix and J.L. Hodges (1951): An Important Contribution to Nonparametric Discriminant Analysis and Density Estimation: Commentary on Fix and Hodges (1951),” International Statistical Review / Revue Internationale de Statistique, vol. 57, no. 3, pp. 233–238, 1989. [Online]. Available: http://www.jstor.org/stable/1403796 [27] M. M. Breunig, H.-P. Kriegel, R. T. Ng, and J. Sander, “LOF: Identifying Density-based Local Outliers,” in Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, ser. SIGMOD ’00. New York, NY, USA: ACM, 2000, pp. 93–104. [Online]. Available: http://doi.acm.org/10.1145/342009.335388 [28] G. Erdogan, “OutlierDetectionToolbox: Outlier Detection Toolbox for MATLAB,” Apr. 2017, original-date: 2015-05-10T13:53:19Z. [Online]. Available: https://github.com/gokererdogan/ OutlierDetectionToolbox 66