Optimización de algoritmos de IA aplicando técnicas enfocadas al cómputo de alto rendimiento
Abstract
El trabajo que se presenta se enfoca en la optimización de algoritmos de Inteligencia Artificial (IA) mediante el uso de MPI (Message Passing Interface), una biblioteca estándar desarrollada para el cómputo de alto rendimiento. El objetivo principal consiste en reducir el tiempo de ejecución de los algoritmos, explotando el paralelismo de los recursos de cómputo y la memoria distribuida. Esta tarea es especialmente relevante debido al alto coste computacional y de recursos que implica entrenar o ejecutar estos algoritmos. Este proyecto incluye una descripción de los fundamentos teóricos de los algoritmos que se van a implementar, así como el funcionamiento de la biblioteca MPI. Una vez puesto en contexto, se desarrollan en profundidad las estrategias propuestas para mejorar los algoritmos. Además, se ha realizado un exhaustivo estudio empírico para analizar las estrategias desarrolladas, las cuales han sido ejecutadas en un ordenador personal y en un sistema distribuido que consta de 128 núcleos de CPU y 256 GB de RAM.
Full text
Optimization of AI algorithms by applying high-performance computing techniques Optimización de algoritmos de IA aplicando técnicas enfocadas al cómputo de alto rendimiento TRABAJO DE FIN DE GRADO Grado en Ingeniería Informática DANIEL PIZARRO GALLEGO Director: Alberto Núñez Covarrubias Facultad de Informática Universidad Complutense de Madrid 13 de septiembre del 2024
Autorización de difusión Autor Daniel Pizarro Gallego Fecha Madrid, 11 de Septiembre de 2024. El abajo rmante, matriculado en el Grado de Ingeniería Informática de la Facultad de Informática, autoriza a la Universidad Complutense de Madrid (UCM) a difundir y utilizar con nes académicos, no comerciales y mencionando expresamente a su autor el presente Trabajo Fin de Grado: Optimización de algoritmos de IA aplicando técnicas enfocadas en cómputo de alto rendimiento, realizado durante el curso académico 2023-2024 bajo la dirección de Alberto Núñez Covarrubias en el Departamento de Departamento de Sistemas Informáticos y Computación, y a la Biblioteca de la UCM a depositarlo en el Archivo Institucional E-Prints Complutense con el objeto de incrementar la difusión, uso e impacto del trabajo en Internet y garantizar su preservación y acceso a largo plazo.
Resumen El trabajo que se presenta se enfoca en la optimización de algoritmos de Inteligencia Articial (IA) mediante el uso de MPI (Message Passing Interface), una biblioteca estándar desarrollada para el cómputo de alto rendimiento. El objetivo principal consiste en reducir el tiempo de ejecución de los algoritmos, explotando el paralelismo de los recursos de cómputo y la memoria distribuida. Esta tarea es especialmente relevante debido al alto coste computacional y de recursos que implica entrenar o ejecutar estos algoritmos. Este proyecto incluye una descripción de los fundamentos teóricos de los algoritmos que se van a implementar, así como el funcionamiento de la biblioteca MPI. Una vez puesto en contexto, se desarrollan en profundidad las estrategias propuestas para mejorar los algoritmos. Además, se ha realizado un exhaustivo estudio empírico para analizar las estrategias desarrolladas, las cuales han sido ejecutadas en un ordenador personal y en un sistema distribuido que consta de 128 núcleos de CPU y 256 GB de RAM. Palabras clave IA, aprendizaje automático, MPI, speed-up, distribuida, redes neuronales, algoritmos, clustering, master, worker.
Abstract The work presented focuses on the optimization of Articial Intelligence (AI) algorithms using MPI (Message Passing Interface), a standard library developed for high-performance computing. The main objective consists in reducing the execution time of the algorithms, by exploiting the parallelism of computing resources and distributed memory. This task is especially relevant due to the high computational and resource cost involved in training or running these algorithms This project includes a description of the theoretical foundations of the algorithms that will be implemented. Moreover, functioning of the MPI library is also presented. Once put in context, the strategies employed to enhance the algorithms are described in detail. In addition, an exhaustive empirical study has been carried out to analyze the developed strategies, which have been executed on a personal computer and in a high distributed system consisting of 128 CPU cores and 256 GB of RAM. Keywords IA, machine learning, MPI, speed-up, distributed, neural network, algorithm, clustering, master, worker.
Índice general Índice i Dedicatoria iii 1. Introducción 1 1.1. Denición y alcance del proyecto . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2. Motivación..................................... 3 1.3. Objetivo...................................... 4 1.4. Estructura del documento . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1. Introduction 6 1.1. Project denition and scope . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2. Motivation..................................... 8 1.3. Objective ..................................... 8 1.4. Documentstructure................................ 10 2. Contextualización 11 2.1. MPI ........................................ 11 2.2. Aprendizaje por Refuerzo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2.1. Algoritmo Q-Learning . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2.2. Deep Q-Network (DQN) . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3. Aprendizaje No-Supervisado . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3.1. Clustering jerárquico aglomerativo . . . . . . . . . . . . . . . . . . . 19 2.3.2. Clustering basado en particiones: K-Medias . . . . . . . . . . . . . . 20 2.4. Aprendizaje Supervisado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.4.1. K-Vecinos más Cercanos - KNN . . . . . . . . . . . . . . . . . . . . . 22 2.4.2. RedesNeuronales............................. 23 2.5. AlgoritmosEvolutivos .............................. 25 3. Diseño e Implementación de estrategias para aumentar el rendimiento de algoritmos de IA 27 3.1. Programassencillos................................ 27 3.2. AlgoritmosdeClustering............................. 32 3.2.1. Jerárquico Aglomerativo . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.2.2. K-Medias ................................. 36 3.2.3. K-Vecinos más cercanos (KNN) . . . . . . . . . . . . . . . . . . . . . 39 3.3. Aprendizaje por refuerzo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 i
3.3.1. Q-Learning ................................ 42 3.3.2. DeepQ-Network ............................. 46 3.4. AlgoritmosEvolutivos .............................. 49 3.5. RedesNeuronales................................. 56 4. Estudio empírico 61 4.1. Entornosdeejecución............................... 61 4.2. Programassencillos................................ 63 4.2.1. Ordenaciones ............................... 63 4.2.1.1. Algoritmos de complejidad cuadrática . . . . . . . . . . . . 63 4.2.1.2. Algoritmo MergeSort ...................... 65 4.2.2. Multiplicación de matrices . . . . . . . . . . . . . . . . . . . . . . . . 67 4.3. Algoritmos de Agrupación . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.3.1. Jerárquico Aglomerativo . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.3.2. K-Medias ................................. 75 4.3.3. KNN.................................... 78 4.4. Q-Learning .................................... 81 4.5. AlgoritmosEvolutivos .............................. 85 4.6. RedesNeuronales................................. 96 5. Conclusiones y trabajo futuro 102 5. Conclusions and future work 104 Bibliography 108 ii
Dedicatoria A mis padres, por que gracias a ellos soy quien soy hoy iii
Capítulo 1 Introducción En este capítulo se presenta una perspectiva general del contexto en el que se ha llevado a cabo el proyecto. Además de las dicultades encontradas durante su desarrollo para alcanzar las contribuciones mencionadas, se detallan cada uno de los propósitos perseguidos en él. 1.1. Denición y alcance del proyecto El desarrollo de las Inteligencias Articiales en nuestra sociedad ha sido un fenómeno de gran relevancia, además de popular, en los últimos años. Estas tecnologías han llegado para quedarse y están mejorando nuestra calidad de vida. Desde la automatización de tareas hasta la asistencia virtual 12 , estas IAs desempeñan un papel cada vez más importante en nuestro día a día. Con el advenimiento del Internet de alta velocidad y la proliferación de datos, las empresas tecnológicas se enfrentan a la necesidad creciente de desarrollar servicios de alta calidad en un mercado muy competitivo. Actualmente, se invierte mucho dinero y tiempo en mejorar y diseñar algoritmos para implementar Inteligencias Articiales para el acceso público 21 . El entrenamiento y ejecución de estos algoritmos para modelar inteligencias articiales consumen mucha energía, además de provocar una cantidad excesiva de emisiones de CO 2 . La empresa tecnológica Hugging Face , desarrolladora de BLOOM 1 , la primera LLM (Large Language Model) multilenguaje entrenada de forma transparente, tuvo la colaboración de muchos investigadores. Este proyecto, con 176 mil millones de parámetros, es capaz de 1
generar texto en 46 idiomas y 13 lenguajes de programación. No obstante, estimaron que el entrenamiento de esta inteligencia articial emitió 25 toneladas de CO 2 , cifra que se duplicó al contar el coste de producción del equipo informático usado 10 . Los investigadores se están enfocando en evaluar y reducir el impacto ambiental de las tecnologías de IA. Una prueba de ello es el desarrollo de CarbonTracker 9 (CTI), un equipo de especialistas nancieros que asumen el riesgo climático como realidad de los mercados nancieros actuales. El objetivo de esta herramienta es predecir y reducir la huella de carbono de las etapas de entrenamiento de los modelos de IA 15 . El uso de la programación distribuida, más especícamente, aplicaciones basadas en MPI, permite ejecutar varios procesos en paralelo, dividiendo la carga de trabajo y reduciendo el tiempo de ejecución. Al contrario de los programas basados en el modelo de memoria compartida, en el cual se pueden dar problemas de sincronización, cada proceso generado tiene su propia memoria local, evadiendo estos problemas. Sin embargo, hay que diseñar implementaciones correctas y ecientes para no tener más complejidad espacial (uso de memoria) de la esperada. Las conexiones entre los procesos se pueden congurar para maximizar la eciencia y reducir el tiempo de cómputo. Una de las más populares es el modelo MasterWorker . El proceso master se encarga de distribuir el trabajo a los procesos workers para que, en paralelo, puedan ejecutar la misma tarea con conjuntos de datos más reducidos. Al nalizar la tarea, cada worker envía sus datos procesados, y si el proceso master no ha terminado la ejecución, espera para recibir más datos hasta procesar completamente el data-set inicial. MPI permite la comunicación eciente entre procesos, mejorando la escalabilidad y reduciendo el tiempo de procesamiento. Esta metodología, además de mejorar el rendimiento, también simplica la gestión de recursos, mejorando la utilización del hardware disponible en el sistema. Los algoritmos de IA suelen manejar un vasto número de datos para entrenar y evaluar los modelos deseados. Por eso es fundamental diseñar estrategias para distribuir los datos y dividir las cargas de trabajo de manera equitativa, controlando el ujo de datos para 2
language -currentlyin the eld of articial intelligence 19 . However, being an interpreted language (the code is translated in the same execution), it increases the overhead and makes the program -generallyslower than the same implementation in other languages. For these reasons, Python is the ideal programming language to apply high-performance computing techniques and reduce execution time. Likewise, it will be necessary to achieve the following secondary objectives: 1. Design of scalable and exible implementations. When designing and implementing improvements to each algorithm, it is possible to use -among other parametersdierent numbers of processes in the execution. This allows a deep study of the created implementations. By varying the number of processes you can check which number is ideal for any implementation. Flexibility in the enhancements allows the input data to be varied to work correctly with a variable dataset size. 2. Correct operation of the algorithms. When making improvements, in addition to improving performance, it is necessary to have cohesion with the original algorithm. That is, if we want to maximize an evaluation function, the implementation of the improvement has to provide similar or better results. It is not useful to implement an improvement that reduces the execution time, but obtains worse results than the algorithm executed sequentially. 3. Empirical study. An evaluation of the improvements will be carried out to calculate the obtained speed-up. First, the execution time of each algorithm is measured without improvements and, subsequently, the dierent implementations developed are analyzed by varying the number of processes executed. Finally, the best implementations of each algorithm are tested on a personal computer and on a distributed system consisting of 128 cores. 9
1.4. Document structure The subsequent chapters of this document are organized as follows: Chapter 2: Contextualization. This chapter provides information on each algorithm studied. Chapter 3: Design and implementations. This chapter describes in detail the implementations developed for the dierent techniques addressed. Chapter 4: Empirical study, presents the experimental process carried out, which consists of analyzing the proposed improvements, varying the number of processes and the size of the data, in two dierent environments, personal computer and distributed system. Chapter 5: Conclusions and future work. The last chapter concludes the work with a synthesis of the results obtained, and presents the projection of future work. The material generated in this work (code, datasets, tests, photoshop les, etc.) is stored in the following GitHub repository Danipiza/TFG. The images used in this paper have been created from scratch in Photoshop. 10
Capítulo 2 Contextualización En este capítulo se presenta una descripción de los algoritmos de Inteligencia Articial que se van a utilizar en el proyecto, profundizando es sus usos y características. Además, se presenta la biblioteca de paso de mensajes (MPI) empleada en el proyecto para la paralelización de los algoritmos. 2.1. MPI Message Passing Interface 5 (MPI) es un estándar para una biblioteca de paso de mensajes, diseñado para funcionar en una amplia variedad de arquitecturas informáticas paralelas. MPI permite la comunicación entre procesos, mediante el envío y recepción de mensajes. Comúnmente se utiliza en sistemas de alto rendimiento 20 (HPC, por sus siglas en inglés) y entornos informáticos paralelos para desarrollar aplicaciones paralelas escalables y ecientes. Al crear el entorno MPI en una aplicación, se ejecutan en paralelo varios procesos, cada uno con su correspondiente id , también llamado rank . El programador elige cuál va a ser el desempeño de los procesos. Por ejemplo, en el modelo Master-Worker , el primer proceso ( rank = 0 ) generalmente, es llamado master , y se encarga de distribuir los datos entre los demás procesos, llamados workers . La Figura 2.1, muestra la comunicación entre los procesos en este modelo. El proceso master reparte los datos mientras que los workers los procesan y devuelven el resultado. 11
Figura 2.1: Comunicación Master-Worker Esta técnica de paralelización utiliza memoria distribuida, es decir, cada proceso tiene su propia memoria local. Así, los procesos no tienen que preocuparse por los problemas de la memoria compartida, como la sincronización para el acceso de variables compartidas, condiciones de carrera o deadlocks (dos o más procesos quedan bloqueados en un estado en el que ninguno puede continuar con su ejecución, pues están esperando a que otro proceso, también bloqueado, libere un recurso necesario para continuar). Asimismo, la memoria compartida no es fácilmente escalable a un gran número de procesadores 18 . Un programa ejecutado en paralelo, donde múltiples procesos se ejecutan en el mismo programa de manera independiente, pero trabajan con diferentes conjuntos de datos se denomina, por sus siglas en inglés, SPMD (Single Program Multiple Data). Este modelo es comúnmente utilizado en computación de alto rendimiento (HPC) y en entornos de procesamiento paralelo. La escalabilidad y eciencia de este modelo son sus principales ventajas. Los mensajes pueden ser: Síncronos: El proceso receptor se queda bloqueado esperando el mensaje. Asíncrono: el receptor no se bloquea, por lo que puede adelantar código mientras espera a recibir el mensaje. 12
Un programa MPI (ver Figura 2.2), comparte el mismo código para todos los procesos ejecutados. Un proceso lee el conjunto de datos y los carga en su memoria, para luego dividirlos y enviarlos a los procesos disponibles. Una vez repartido el dataset , se ejecutan en paralelo y procesan los datos recibidos. Cuando un proceso naliza el procesado de los datos, envía los datos procesados al proceso correspondiente. La Figura 2.3 representa en código esta idea. Figura 2.2: Ejecución MPI 1 from mpi4py import MPI # Al importar la biblioteca en Python se genera el entorno. 2 3 comm = MPI.COMM_WORLD # Comunicador 4 status = MPI. Status () # Status 5 myrank = comm. Get_rank () # id de cada proceso 6 numProc = comm. Get_size () # Numero de procesadores 7 8 i f myrank==0: # Master 9 # Carga el conjunto de datos . Los divide y envia . 10 # Recibe todos los datos procesados . 11 else :# Workers 12 # Recibe el subconjunto de datos que le asigna el Master . 13 # Procesa los datos . Los envia . Figura 2.3: Esquema básico para ejecutar un programa MPI en Python 13
2.2. Aprendizaje por Refuerzo Reinforcement Learning (RL, por sus siglas en inglés), en español, Aprendizaje por Refuerzo, es un tipo de aprendizaje automático donde el agente aprende en base a las decisiones tomadas al interactuar con el entorno. El agente aprende a cumplir un objetivo en un entorno ejecutando un determinado número de acciones. Este tipo de algoritmos no requiere de entradas etiquetadas como en el aprendizaje supervisado, sino que recibe una retroalimentación, feedback en inglés (recompensas o castigos), al realizar acciones en los estados. Aprendiendo con prueba y error, el agente explora el entorno para almacenar las mejores acciones para cada estado. Los componentes esenciales del algoritmo son los siguientes: Agente que interactúa con el entorno y aprende de él, ejecutando sus acciones. Entorno con el cual el agente interactúa. Responde a las acciones tomadas por el agente y provee el feedback . Conjunto de acciones o decisiones que el agente puede realizar. Estados , son las conguraciones que el entorno puede tomar. Feedback , recompensas o castigos del entorno al realizar una acción en un estado. Condición de nalización . La cual puede ser desde encontrar la función óptima, hasta realizar un número de acciones. 2.2.1. Algoritmo Q-Learning El algoritmo Q-Learning es una mezcla entre programación dinámica y Monte Carlo 22 . Es el más básico de entre los algoritmos de aprendizaje por refuerzo. Se usa para encontrar la mejor política de selección de acciones para un proceso de Decisión de Markov Determinado (MDP, por sus siglas en inglés) 8 . 14
El procedimiento se realiza actualizando iterativamente las estimaciones de calidad de realizar dicha acción en el estado actual, conocido como valor-Q. Se suele representar en forma de matriz Q(S,A) , guardando los valores-Q de las acciones en los estados. Este valor representa cómo de buena es la acción a realizar en un estado después de realizar una etapa de entrenamiento. Para ello, la Figura 2.4 muestra la fórmula para actualizar los valores, para cada acción tomada por el agente. Q(S, A) = (1 −α)Q(S, A) + α(R(S, A) + maxi{Q(S′, Ai)}) Q(S, A) Es el valor-Q de ejecutar la acción A en el estado S . R(S, A) Es la recompensa obtenida al ejecutar la acción A en el estado S . α Tasa de aprendizaje. Controla cuánta importancia le da a la nueva información frente a la antigua. γ Factor de descuento. Determina la importancia de futuras recompensas comparadas con las recompensas inmediatas. maxi(Q(S′, Ai)) : Es el valor máximo obtenible de realizar las posibles acciones en el estado siguiente. Figura 2.4: Cálculo del Q-Value de un estado y acción El agente toma la decisión de ejecutar una acción dependiendo del hiper-parámetro ϵ con valores entre [0,1] . Con un número aleatorio (en el mismo intervalo) calcula la probabilidad de ejecutar la mejor acción aprendida hasta el momento, o una acción aleatoria entre las disponibles. Si el valor es alto, con alta probabilidad se ejecutará la mejor acción aprendida hasta el momento, y es posible que no aprenda otras formas de alcanzar el objetivo. Este algoritmo se ha aplicado en muchos dominios, como puede ser videojuegos de Atari 14 , robótica o problemas de optimización. Sin embargo, sufre cuando el entorno tiene muchos estados, ya que la complejidad espacial aumenta considerablemente, y no resulta práctico contar con dos matrices. Por eso se diseñó el algoritmo DQN, el cual usa una red neuronal. Así, se elimina la maldición de dimensionalidad 11 , problemas que surgen con el ex15
ceso de variables independientes en un dataset . En este algoritmo, el problema es el elevado número de estados que el agente ha de recorrer. 2.2.2. Deep Q-Network (DQN) Debido a los problemas de escalabilidad mencionados anteriormente, se desarrolló el algoritmo de Redes Neuronales Profundas (DQN, por sus siglas en inglés). Este algoritmo combina redes neuronales con la base de aprendizaje por refuerzo, eliminando así la Q-Table. La estructura de la red neuronal depende del entorno del problema. Los valores de la capa oculta se pueden modicar dependiendo de las necesidades del programador, pero la capa de entrada y salida depende del problema. La entrada se adapta para recibir un estado del entorno, como por ejemplo una imagen representada como una matriz. La salida de la red tendrá tantos nodos como acciones tenga el agente. En este trabajo, el entorno del problema será el juego Pacman, diseñado por la empresa Namco , y en particular la versión de Atari 2600 , (ver Figura 2.5). El juego consiste en recolectar todas las monedas del laberinto sin ser comido por un fantasma. Implementamos el juego -desde ceropara moldear según nuestros intereses la implementación y que el algoritmo DQN sea más eciente y sencillo. En el Capítulo 3, diseño e implementaciones, se desarrolla en profundidad. El algoritmo DQN a realizar tendrá dos redes neuronales, una del estado actual y otra de anticipo, es decir, el siguiente estado. Esto sirve para ayudar a tener más contexto del estado actual, pues con una sola imagen (estado del juego), la información del estado puede variar considerablemente. En la fase de entrenamiento se realizan varios episodios, que consisten en ejecuciones hasta que se dé una condición de nalización. Además de ejecutar repeticiones de estados guardados anteriormente (replay buer). En este algoritmo se usan tres hiperparámetros: 1. Gamma , factor de descuento [0, 1]. Utilizado para saber cuánto resta a la recompensa adquirida al realizar una acción en un estado. 16
Figura 2.5: Juego Pac-Man implementado desde cero. Versión Atari 2600 2. Epsilon , tasa de exploración [0, 1]. Probabilidad utilizada para ejecutar una acción aleatoria o la mejor hasta el momento. 3. Learning rate , tasa de aprendizaje [0, 1]. Para la propagación hacia atrás de las redes neuronales. Esencialmente, mide cuánto cambian los pesos de los nodos al tener un fallo. Además de estos parámetros, el algoritmo cuenta con otras variables para desarrollar las redes neuronales. Epsilon decay . Utilizado para no usar siempre el mismo valor de epsilon . Esta variable marca cuanto se reduce la variable epsilon entre episodios. Número de ejemplos de entrenamiento ( batch size) . Se utiliza para actualizar los parámetros de la red neuronal durante una sola iteración del entrenamiento. Tamaño de la capa oculta. Marca el número de neuronas en cada capa. 17
2.3. Aprendizaje No-Supervisado Los métodos no supervisados (unsupervised methods, en inglés) son algoritmos de aprendizaje automático que basan su proceso en un entrenamiento con datos sin etiquetar. Es decir, a priori, no se conoce ningún valor objetivo, ya sea categórico o numérico. La meta de este aprendizaje es encontrar patrones o estructuras en los datos proporcionados. Estos algoritmos son útiles en escenarios en los cuales hay escasez de datos etiquetados o éstos no están disponibles. Hay muchos tipos de técnicas de aprendizaje no supervisado como, entre otros, la detección de anomalías, reducción de dimensionalidad o clustering . En este proyecto vamos a reducir el tiempo de ejecución de las técnicas de clustering que se encargan de agrupar individuos basándose en alguna medida de similitud. Como no es aprendizaje supervisado, no disponemos de información categorizada previamente, por lo que hay que calcular el número óptimo de clusters . Para ello, hay medidas ya estudiadas como el diagrama de codo, cuyo valor óptimo de clusters se calcula visualmente, cuando empieza a crearse un codo (la diferencia con el número anterior no es tan pronunciada como en puntos anteriores). Hay otros coecientes que calculan la optimalidad con algoritmos, como el coeciente de Davies-Bouldin, cuyo valor mínimo indica el número óptimo de clusters , o el coeciente de Silhouette, similar al anterior, pero con el valor máximo. Se pueden apreciar los diferentes coecientes para una misma categorización en la Figura 2.6. Como se puede apreciar, el diagrama de codo es el coeciente más complicado de visualizar, lo otros dos coecientes solo es necesario encontrar el menor o mayor valor, mientras que en el primero hay que visualizar el codo, y en este ejemplo se podría elegir también tres clusters como número óptimo. Los llamados métodos jerárquicos 3 tienen por objetivo agrupar clusters para formar uno nuevo o bien separar alguno ya existente para dar origen a otros dos, de tal forma que, si sucesivamente se va efectuando este proceso de aglomeración, se minimice alguna distancia o bien se maximice alguna medida de similitud. 18
Algorithm 4: Red Neuronal Data: entrenamiento, etiquetas, evaluacion // Individuos sin categorizar repeticiones, capas // Tam. entrada, oculta, salida Result: pesos // Opcionalmente, devolver los pesos de la red pesos := init() // Inicializar los pesos de manera aleatoria for rep ←0 to repeticiones do cont := 0 for each ind in entrenamiento do // Suma el valor recibido de la capa anterior multiplicada por los pesos de la capa actual con la siguiente. Así se determina la importancia de conexión entre las neuronas. Con el valor calculado se aplica a una función de activación y se pasa a la siguiente capa hasta llegar a la salida. predicion := forward(pesos, ind) // El valor predicho calculado en la salida es comparado con la etiqueta, y se calcula el error. Este error se manda para atrás actualizando los pesos. Se suma la multiplicación del valor predicho en cada capa con la tasa de aprendizaje y el error. backpropagation(pesos, predicion, etiqueta[cont]) cont++ return agrupacion 2.5. Algoritmos Evolutivos La programación evolutiva es una técnica de optimización inspirada en la teoría de la evolución biológica. Se basa en el concepto de selección natural y evolución de las poblaciones para encontrar soluciones a problemas complejos. La población está compuesta por individuos, que pueden ser representados con arrays de números reales, binarios o un árbol. Los individuos tienen un cromosoma, que a su vez tiene uno o varios genes, con uno o más alelos. Esta población es sometida a métodos de evaluación, selección, cruce y mutación para, con el paso de las generaciones, maximizar o minimizar un valor tness . Esta técnica es muy útil para problemas de optimización donde los métodos tradicionales no proporcionan el rendimiento deseado. Los Algoritmos Evolutivos se han aplicado a varios dominios, como por ejemplo la bioinformática o robótica 6 . La Figura 2.10 muestra el diagrama de estados del algoritmo más básico. Cada método se 25
puede modicar para cualquier individuo, así como añadir más técnicas para garantizar y/o mejorar los resultados nales, como puede ser el elitismo, que garantiza la supervivencia de los mejores individuos, o un desplazamiento de los valores tness para evitar valores negativos. Figura 2.10: Algoritmo Evolutivo básico 26
Capítulo 3 Diseño e Implementación de estrategias para aumentar el rendimiento de algoritmos de IA En este capítulo se presentan los diseños e implementaciones desarrollados a lo largo del trabajo. Inicialmente se presenta una introducción a la biblioteca MPI, con varios ejemplos donde se mejora el rendimiento de programas sencillos fuera del ámbito de la inteligencia articial. Posteriormente, se describen los algoritmos de IA ordenados -de menor a mayorsegún su complejidad. 3.1. Programas sencillos Para introducir MPI en el proyecto se implementan -utilizando esta bibliotecavarios programas sencillos. Primero, la multiplicación de matrices, que tiene un coste cúbico O( N3 ), al tener que recorrer, para cada elemento de la matriz, una la y columna entera. Segundo, algoritmos de ordenación que, para simplicar, solo se realiza un estudio de las ordenaciones con mayor complejidad temporal, O( N2 ) y MergeSort con coste O( N∗logN ). Las matrices son un concepto matemático muy relevante en el mundo de los videojuegos y en el ámbito de la inteligencia articial. Hay muchas técnicas de IA que conllevan la gestión de imágenes -representadas digitalmente como matrices de píxelescomo en el algoritmo DQN cuya red neuronal tiene como entrada varios fotogramas para poder aprender 27
La multiplicación de matrices es un buen ejemplo para presentar una estrategia basada en MPI, debido su alto coste computacional. Para ello, hay que plantear cómo dividir el trabajo entre los procesos. Inicialmente, se puede pensar que es mejor enviar los datos conforme se naliza una operación, pero en esta operación se necesitan las las de una matriz y columnas de otra, por lo que conviene que cada proceso tenga una matriz entera en su memoria local para agilizar el proceso y poder enviar más datos al mismo tiempo. Cada worker se va a encargar de un determinado número de las, paralelizando así el cálculo. El master se encarga de dividir la matriz entre los procesos. Se puede abordar con dos enfoques distintos: Reparto estático: los datos se asignan antes de empezar el cálculo. Reparto dinámico: los datos se reparten en tiempo de ejecución, asignando los mismos de forma proporcional a la velocidad de cada proceso. En la primera estrategia, dividimos la segunda matriz entre todos los workers , dejando al master en espera de recibir datos. Esta mejora depende de la velocidad de los procesos, pues se puede generar un cuello de botella si todos terminan y envían los datos al mismo tiempo. Además, se aumenta la complejidad espacial entre los procesos, pues se divide la matriz entera entre los workers . En la segunda estrategia, hay un ujo constante de nuevos datos y resultados obtenidos, reduciendo el tiempo perdido en un posible cuello de botella. En la Figura 3.1 se muestra como el master divide la matriz, marcando en negro la parte ya procesada. A su vez cada worker tiene una sola la en su memoria, reduciendo la complejidad espacial. Los algoritmos de ordenación tienen que iterar varias veces hasta que el array de elementos esté completamente ordenado. Los métodos pueden variar considerablemente el tiempo de ejecución. Para las ordenaciones cuadráticas, los métodos populares como BubbleSort , InsertionSort y SelectionSort , han sido estudiados y optimizados para que, aunque tengan un coste cuadrático O( N2 ), en el caso peor, proporcionen un buen rendimiento. Basándose en estos 28
Figura 3.1: División de datos entre los procesos workers en la multiplicación de matrices algoritmos, se ha diseñado uno adicional llamado SequentialSort . Este algoritmo recorre todas las posiciones del array y, para cada elemento, compara todos los datos, sumando en un contador los elementos mayores que él, para calcular así su posición en el array ordenado. Una vez nalizada una iteración, se coloca el elemento en el array ordenado, si la posición actual está ocupada es porque hay una repetición del elemento, y se tiene que colocar en la siguiente celda libre. La Figura 3.2 representa el proceso de ordenación, marcando en gris el elemento que ha de compararse con los demás en la iteración i-ésima. Este método siempre tendrá coste cuadrático O( N2 ). No es como los anteriores que van reduciendo el espacio conforme aumentan las iteraciones, pero es fácilmente paralelizable. Para lograr reducir el tiempo de ejecución para esta ordenación cuadrática, se desarrollan las dos estrategias siguientes, cada cual con sus ventajas e inconvenientes. 1. Enviar a todos los workers el array entero para que trabajen de manera independiente. 2. Dividir el array entre los workers para trabajar conjuntamente. En la primera estrategia el master envía a todos los workers el array entero. Una vez 29
Figura 3.2: Iteraciones del algoritmo SequentialSort recibido el array de elementos, el master envía elementos sin procesar del array original a los workers disponibles. Al recibir un elemento lo procesan (hacen las comparaciones), y envían la posición del elemento al master , recibiendo de vuelta otro si todavía faltan elementos por procesar. No obstante, la segunda estrategia logra reducir el uso de memoria de tal forma que entre todos los procesos ejecutados solo haya dos copias del array que hay que ordenar, en lugar de mantener M copias (siendo M el número de procesos ejecutados). En cada iteración, el master envía un elemento a todos los workers . Estos hacen todas las comparaciones en sus subarrays y devuelven cuantos elementos pertenecientes a su subarray son mayores que el recibido. Ambas estrategias tienen la misma complejidad temporal. Los algoritmos de ordenación logarítmicos son muy útiles y ecientes. QuickSort tiene varios problemas como la profundidad de recursión y en el caso peor es cuadrático. Los algoritmos de RadixSort y HeapSort son ecientes sin aplicar mejoras, y MergeSort es muy popular, tanto que se aplica en TimSort 4 método de ordenación por defecto en Python. Este último combina InsertionSort , una ordenación cuadrática muy eciente para ordenar pequeños conjuntos de datos, teniendo una baja sobrecarga en términos de operaciones, para luego usar las mitades ordenadas con MergeSort. Sin embargo, el algoritmo básico de 30
MergeSort no es tan eciente. Aplicando la misma idea que TimSort , se puede mejorar el tiempo de ejecución de MergeSort , aplicando combinaciones de los métodos básicos con complejidad cuadrática y comprobar la eciencia. Esta estrategia consiste en crear varios procesos (para mayor ecacia y simplicidad, el número de procesos tiene que ser potencia de dos), y se divide el array entre los procesos. Las fases de esta estrategia son: Primera fase de ordenación: cada proceso ordena su subarray con el método de ordenación correspondiente. En el Capítulo 4, se realiza un estudio de los algoritmos cuadráticos, donde SelectionSort es el algoritmo que mejores resultados obtiene. Segunda fase de reagrupación y ordenación: esta fase se repite hasta solo tener un proceso activo, es decir, el array esté completamente ordenado. En la comunicación entre procesos, cada uno se conecta con el proceso activo más cercano (según su rank ). El proceso de mayor id ( rank ) envía su array ordenado y naliza su ejecución. El proceso receptor se encarga de ordenar ambas mitades en una sola. Utilizando una barrera llamada MPI_Barrier, garantizamos que todos terminen al mismo tiempo. Esta mejora aplica la idea de sincronización con barrera simétrica mariposa , técnica de sincronización que conecta los procesos dos a dos, aumentando la distancia de los procesos para que, en aproximadamente K iteraciones ( 2K = M = número de procesos), todos los procesos estén sincronizados. Para la estrategia implementada, se sincronizan por orden de cercanía entre ids . La Figura 3.3 muestra el proceso de sincronización. En cada iteración se naliza la ejecución de los procesos en rojo, así hasta tener un único proceso con el array entero ordenado. Para aplicar MPI y paralelizar programas hay que tener en cuenta que la comunicación entre procesos requiere un tiempo para enviar/recibir mensajes. Si queremos reducir el tiempo de ejecución de un programa tenemos que asegurarnos que la estrategia es viable para mejorar el rendimiento. Si ejecutamos, por ejemplo, una búsqueda lineal en un array, a 31
Figura 3.3: Ejecución de MergeSort con 8 procesos worker W1 ... W8 primera vista, reducir el espacio de búsqueda puede ser benecioso. Dividiendo el espacio de búsqueda entre los workers reduce el tiempo de O(N) a O(N/numWorkers). Pero ¾se puede reducir el tiempo de ejecución al dividir el espacio entre los workers ? Para responder esta pregunta es necesario tener en cuenta el tiempo de paso de mensajes (overhead). Si no se tuviese en cuenta, se podría garantizar la reducción, pero la comunicación entre procesos tiene un coste, y con un tiempo lineal, generalmente no se pueden lograr mejoras, más bien aumenta el tiempo de búsqueda. Por este motivo, hay que tener en cuenta la complejidad temporal de los algoritmos que queremos optimizar, ya que no siempre es eciente aplicar paralelismo. 3.2. Algoritmos de Clustering Una vez introducido MPI con programas básicos, podemos presentar las implementaciones de los algoritmos relacionados con la inteligencia articial. Las técnicas de clustering toman una población y, dependiendo del conjunto de datos, categorizan los individuos. Los algoritmos pueden ser supervisados, si además de la población a categorizar, tenemos una población categorizada previamente, o no-supervisados, si no contamos con esta población etiquetada. 32
3.2.1. Jerárquico Aglomerativo Este algoritmo de aprendizaje no supervisado usa una matriz para calcular las agrupaciones. Como es una matriz simétrica, podemos reducir la complejidad espacial usando solo el triángulo superior. La distancia entre clusters es muy importante. Además de calcular agrupaciones distintas, también varía la complejidad temporal. La más ecaz y rápida es la de centroides, para calcular la distancia entre dos cluster solo necesita el cálculo entre dos puntos (los centros de los clusters ). El calculo de la distancia por enlace simple y completo, es más complejo. Cada cluster almacena las coordenadas de sus individuos, para, a la hora de calcular la distancia entre dos clusters ( Ci y Cj ), comprobar la distancia de cada par de puntos (donde uno pertenece a Ci y el otro a Cj ). La nueva distancia usando enlace simple es la mínima distancia entre cualquier par de puntos, mientras que la completa es la máxima. Una vez comentadas las estrategias en el cálculo de multiplicación de matrices, podemos usar estas para mejorar este algoritmo. La primera idea de enviar las las conforme se realizan los cálculos no se puede aplicar. El algoritmo es más complejo que realizar sumatorios de multiplicaciones (suma de productos, para la multiplicación de matrices), pues la matriz está en constante cambio. Tendría que realizarse un proceso de comunicación constante para gestionar la matriz. Esto y añadir más operaciones del algoritmo para agrupar los individuos, provoca que no sea viable realizar esta mejora. La estrategia que se va a implementar consiste en dividir la matriz entre los workers . Cada proceso se encarga de una zona, paralelizando así el trabajo a realizar. Como es una matriz simétrica y se representa con el triángulo superior, hay que dividir la carga de trabajo equitativamente. No podemos implementar una mejora sin dividir el espacio de forma equitativa entre los workers . Si dividimos las las de forma secuencial, el primer worker tendrá muchos más elementos que el último, parando la ejecución por culpa del primer proceso. La Figura 3.4 muestra el cálculo de elementos a procesar entre el primer y último worker si no se divide el espacio de manera equitativa. 33
las X i=1 (N−i)≫ las (M−1)+ las X i= las (M−1) (N−i) N individuos de la población, M procesadores. N/M las para cada worker . Con 100 individuos de población y 4 workers , cada uno tendrá 25 las. Por lo que: W1 tiene las las de 1-25, con 2175 elementos. W4 , las las de 76-100, con solo 300 elementos. W1 tiene 7.25 veces más elementos, no se reducirá el tiempo de ejecución. Figura 3.4: Cálculo del número de elementos a procesar usando una distribución secuencial de las Dividiendo las las por pares (parte superior e inferior) conseguimos una distribución mucho más eciente. La Figura 3.5 muestra cómo se distribuyen las las en cada worker . Así, cada worker tiene aproximadamente el mismo número de elementos que calcular y analizar, inicialmente. Sin embargo, puede variar si el número de las no es divisible entre en número de procesos workers Una vez descrito el reparto del espacio entre los procesos, cada uno tiene que ejecutar el algoritmo en paralelo, sincronizándose cada cierto tiempo para actualizar valores. Refrescando la memoria, este algoritmo, en cada iteración, agrupa los dos individuos más cercanos, eliminando una la y columna de la matriz. El bucle principal de la estrategia se repite hasta que solo haya C clusters. Las etapas son las siguientes: 1. El master pide a los workers la celda con menor valor (menor distancia entre los clusters i y j , siendo estos la la y columna). 2. El master , con los valores recibidos, pide la la ( i ) y la columna ( j ) del worker con menor distancia. Con estos datos, el master envía a todos los procesos estos índices, así como los ids de los workers que tienen que eliminar o actualizar la la con mayor o menor índice respectivamente. 34
(a) División de la población categorizada (b) División de la población a predecir Figura 3.8: Estrategias para paralelizar el algoritmo KNN No hay que repetir el mismo algoritmo varias veces, pero puede llegar a ser útil variar el número de vecinos (valor de K ). Las mejoras de esta búsqueda son las mismas que en el algoritmo anterior: 1. Aplicar alguna de las dos implementaciones comentadas anteriormente, con un bucle que varíe la variable K . 2. Ejecutar en cada proceso worker el algoritmo sin mejoras. El master se encarga de almacenar los mejores resultados. 3.3. Aprendizaje por refuerzo Los algoritmos de este tipo de aprendizaje actualizan iterativamente las estimaciones de calidad de las acciones permitidas en el entorno de desarrollo, y pueden ser almacenados en una tabla o aplicar una red neuronal. 41
3.3.1. Q-Learning El algoritmo Q-Learning es el más básico del aprendizaje por refuerzo. Las estimaciones de las mejores acciones para cada estado se almacenan en una Q-Table representada como una matriz en la que cada la es un estado, y las columnas son las acciones disponibles. Este algoritmo tiene numerosas aplicaciones. Nos centramos en la técnica de minimizar las acciones, para llegar desde una celda origen a un destino. El laberinto tiene un tamaño y semilla variable por parámetros de inicialización. Para lograr su objetivo dispone de acciones de movimiento en los dos ejes cardinales: norte, sur, este y oeste. No puede atravesar ni situarse en un muro del laberinto, y para que el agente aprenda a moverse por el laberinto y llegar a la meta hay que jar unas recompensas: Si se choca con un muro castigamos al agente con valores altos para que no añada movimientos innecesarios para alcanzar su objetivo. Al moverse, el agente recibe un castigo pequeño para que aprenda a minimizar las operaciones. Al llegar a la meta le damos una recompensa alta, para que aprenda llegar a la celda destino. Con estas recompensas, el agente aprende a llegar a la meta minimizando las acciones ejecutadas. El código que genera los laberintos ha sido implementado por @ChlouisPy en github 2 Antes de enfocarnos en las implementaciones basadas en MPI, hay que comentar una mejora que se puede aplicar a él algoritmo básico de Q-Learning: realizar un preprocesado. Modicar la Q-Table, convirtiéndola en un array bidimensional, en el cual no se almacenen las acciones que no deseamos que realice el agente, como puede ser chocarse con un muro, o eliminar estados innaccesibles como situarse en un muro. Esta mejora puede reducir el tiempo de cómputo, al no perder tiempo realizando acciones innecesarias para alcanzar su objetivo. Además, se reduce la complejidad espacial al 42
reducir el número de estados. Una desventaja es que añade otra estructura adicional (array bidimensional) para almacenar las acciones para cada estado. Este preprocesado tiene complejidad cuadrática O(4*N 2 ) ≡ O(N 2 ) , siendo N el número de las y columnas. Recorre toda la matriz, comprobando para cada celda si no es un muro, y, en caso armativo, itera en las cuatro direcciones permitidas para almacenar las acciones disponibles para la celda actual (estado). Con tamaños de laberintos pequeños no hace falta paralelizar el preprocesado, porque no se consigue reducir el tiempo signicativamente. Al emplear laberintos con más de mil las y columnas sí se consigue reducir el tiempo de cómputo. En los algoritmos del bloque anterior se necesitaba realizar una búsqueda para encontrar el óptimo general. En este algoritmo conviene realizar otra búsqueda, pero esta vez para encontrar combinaciones de los hiper-parámetros ( α , γ , ϵ ), los cuales son muy importantes para el desarrollo del agente en el entorno. Una mala conguración de éstos hace que sobre aprenda -o no aprendacorrectamente, generando bucles innitos. Por este motivo es importante comprobar tanto las diferentes combinaciones de hiper parámetros, como cuáles funcionan correctamente en el entorno. La búsqueda en laberintos grandes es muy lenta, ya que hay que comprobar muchas combinaciones entre los hiper-parámetros y los episodios del entrenamiento. Por eso es más útil desarrollar el algoritmo Deep Q-Learning, que no tiene problemas con los estados al usar una red neuronal. Pero si queremos usar el algoritmo básico de Q-Learning, hay que realizar una búsqueda exhaustiva en el entorno ejecutando una cantidad signicativa de combinaciones de hiper parámetros. Para paralelizar esta búsqueda se ejecuta el algoritmo básico con el preprocesado mencionado en cada proceso worker . Hay que desarrollar una estrategia para que cada worker reciba una combinación de parámetros distinta, y así no haya repeticiones, perdiendo tiempo de cómputo. El master se encarga de repartir combinaciones de hiper-parámetros. Con una precisión previamente inicializada, el master aumenta un hiper-parámetro hasta llegar al 100% . Cuando llega a dicho límite, se reinicia la variable y se aumenta la siguiente. Este 43
proceso continua hasta llegar al 100% de todos los hiper-parámetros. Cada worker se encarga de una combinación recibida. Cuando termina el algoritmo, ya sea por bucle innito o nalización correcta, envía un mensaje al master con la información de nalización y los hiper-parámetros usados. Si el mensaje de nalización indica bucle, el proceso termina para evitar que se convierta en un proceso inactivo, pues dicha combinación no converge hacia el objetivo. Estos bucles se detectan en el entrenamiento o la evaluación. Hay un bucle en el entrenamiento si un episodio tarda más de X segundos en nalizar. En la evaluación se comprueba teniendo en cuenta los últimos cuatro estados visitados, pues avanza y retrocede constantemente. Estados[0]==Estados[2] and Estados[1]==Estados[3] and Estados[0]!=Estados[1] Una vez realizada una búsqueda de las combinaciones de hiper-parámetros ecaces, se pueden emplearse para las siguientes mejoras: 1. Dividir el entorno (laberinto) entre los procesos. 2. Ejecutar el algoritmo en los workers y juntar las experiencias. Al dividir el laberinto entre los procesos (primera mejora), cada proceso controla una zona, y se genera un ujo constante de episodios (iteraciones del algoritmo). Cuando un agente sale del dominio de un proceso, éste le manda un mensaje al proceso que controla esa parte del laberinto con la posición en la que entra. La Figura 3.9 muestra cómo se divide un posible laberinto entre los procesos, además de mostrar tres episodios con sus respectivos agentes (circulo en rojo). El master se encarga de iniciar a los agentes en la celda verde, y cuando sale de su dominio, envía la posición en el laberinto al respectivo proceso y genera otro agente. Para garantizar el correcto funcionamiento, el master no puede recibir agentes de los workers , en caso contrario no se podría garantizar el ujo de nuevos episodios. En la ejecución, solo pueden existir M agentes en todos los procesos (siendo M el número de procesos 44
ejecutados), debido a que un proceso solo puede gestionar a lo sumo un agente. Cada proceso tiene su propio dominio, lo que provoca que la Q-Table se divida entre éstos. Aplicando el preprocesado comentado anteriormente se dividen los dos arrays bidimensionales (acciones y Q-valores). Figura 3.9: División del entorno de la primera estrategia del algoritmo de Aprendizaje por Refuerzo Aplicando la estrategia realizada en la búsqueda de hiper-parámetros, consistente en ejecutar el algoritmo en varios procesos, se puede obtener la segunda estrategia. El master recolecta las experiencias de los workers , haciendo la media de los Q-valor obtenidos de los procesos, calculando así las mejores acciones para cada estado. Hay que tener en cuenta la posición de inicialización de los agentes en los procesos ejecutados. Si todos los procesos comparten el mismo punto de salida, los resultados serán parecidos a ejecutar el algoritmo en un solo proceso. Sin embargo, al cambiar el punto de origen, los Q-valores obtenidos al realizar las medias de las experiencias varían y se recorre más espacio en menos tiempo. Para lograr buenos resultados se asegura que al menos un proceso empieza desde el punto 45
origen, de otra forma no se podría garantizar que el agente haya aprendido a alcanzar el destino desde la celda origen. 3.3.2. Deep Q-Network Este algoritmo utiliza redes neuronales para obtener la mejor acción para un determinado estado, eliminando así los problemas que tiene el algoritmo anterior. Con este método podemos abarcar entornos más complejos, y por eso se propone el juego de Namco PacMan, cuya implementación creamos desde cero para moldear a nuestro gusto la dicultad del entorno, así como facilitar el aprendizaje de la red neuronal. Nos centramos en obtener el mayor número de monedas antes de provocar una condición de nalización (ser comido por un fantasma o recoger todos los puntos). Para simplicar el entorno, no se desarrollan niveles en la ejecución, al igual de limitar la vida del agente a un único corazón, por lo que sí es comido una única vez se termina la ejecución. Antes de profundizar en el algoritmo de IA, explicamos cómo funciona y hemos realizado la implementación del entorno. Acciones disponibles. Como en el algoritmo anterior, son de movimiento. El agente y los fantasmas no pueden atravesar muros. Entorno. Laberinto con muros, del cual no se puede escapar. Objetos del juego. - Pac-Man: el agente que mueve el usuario. Su objetivo es comer todos los puntos. - Fantasmas: se mueven siguiendo unos objetivos en el laberinto. - Túneles: puntos que se conectan de manera toroidal para no salir del entorno. - Puntos (pellets en inglés): son las "monedas"que el agente tiene que recoger. - Puntos de energía (powers): si el agente consume uno, durante un periodo de tiempo es invencible y puede comer a los fantasmas. - Laberinto: entorno por el cual el agente y fantasmas se mueven. Condiciones de nalización. Ganar obteniendo todas las monedas del laberinto o perder si un fantasma come al agente. 46
Los fantasmas tienen una IA interesante, pues tienen sus propios estados y cada uno tiene unos puntos objetivos que siguen para intentar comer al agente. Cabe recalcar que estos puntos están estratégicamente colocados para que los fantasmas trabajen en conjunto para cerrar huecos y poder atrapar al agente. El movimiento para alcanzar los puntos objetivos es simple, cuando se encuentran en una intersección (punto en el mapa con un hueco a la izquierda o derecha con respecto a su dirección actual) eligen la celda que minimice la distancia con respecto al punto objetivo. Los estados de los fantasmas son los cuatro siguientes: Chase. Cada fantasma sigue unos puntos en movimiento. Scatter. Sigue un punto estático fuera del laberinto para dar vueltas en una determinada zona. Frightened. El agente puede comerlos, se mueve de manera aleatoria al llegar a una intersección. Eaten. Han sido comidos y se encuentran en su casa esperando a salir. (Implementado de forma que espera 3 movimientos del agente para salir) Los estados iteran con una secuencia principal [Scatter, Chase] . La ejecución empieza con Scatter para que los fantasmas, al salir de su casa, se dirijan a sus zonas asignadas. Al ejecutar el agente treinta acciones, el estado cambia a Chase y se mantiene así sesenta acciones, volviendo a repetirse la secuencia. Si el agente come un punto de energía, los fantasmas interrumpen su estado actual para pasar al estado Frightened en el que están treinta acciones siendo vulnerables. Si el agente colisiona con un fantasma en este estado, es comido, pasando al estado Eaten . Al nalizar este estado vuelven al inicio de la secuencia principal. En el estado Chase los fantasmas se mueven de la siguiente forma: Blinky (Rojo): Persigue directamente al agente. 47
Pinky (Rosa): Persigue la celda cuatro posiciones adelantadas a donde apunta el agente. Si el agente mira hacia arriba, también añade cuatro celdas hacia la izquierda. Inky (Azul): Persigue una celda en concreto que se calcula de la siguiente forma. Primero se calcula una posición como lo hace el fantasma rosa, pero en vez de cuatro celdas, se hace con dos. El objetivo se calcula al añadir el vector de distancia de la posición del fantasma rojo a esta posición. Clyde (Naranja): Si está a ocho o más celdas de distancia del agente, lo persigue. En caso contrario sigue su objetivo del estado Scatter. El laberinto (mapa del entorno) se almacena en un chero de texto, para representar las celdas vacías, muros, puntos, o puntos de poder con números enteros (0, 1, 2 y 3 respectivamente). Al igual que en el algoritmo Q-Learning la fase de entrenamiento es crucial, pues modican los valores de la red neuronal para que el agente tome las mejores decisiones en cada estado, y terminar la ejecución sin perder. El entrenamiento se puede realizar de varias formas. Si mantenemos el mismo estado inicial, el agente empieza siempre en el mismo punto, y depende mucho de los hiper-parámetros, además de la aleatoriedad. El agente empieza a investigar el entorno de manera aleatoria, y es muy probable que los fantasmas alcancen al agente bastante rápido sin explorar en profundidad el entorno. Por eso es mejor añadir varios estados iniciales para que pueda investigar el entorno de manera más eciente. Hay que tener en cuenta que los estados iniciales tienen que ser puntos accesibles desde el estado inicial original. El agente no puede saltar a otras celdas sin coger los puntos del laberinto. La Figura 3.10 muestra un estado accesible y otro inaccesible con la misma posición del agente. El estado accesible ha recogido los puntos del laberinto, así como posicionado correctamente los fantasmas, en su contraparte el estado inaccesible no ha recogido los puntos simulando una acción de salto por parte del agente. Si entrenamos con puntos aleatorios sin cambiar 48
el estado del entorno, este entrenamiento no habrá surtido efecto, pues son estados que el agente no va a alcanzar nunca. Figura 3.10: Tipos de estados del entorno en el algoritmo DQN Como se comentó anteriormente, este algoritmo usa redes neuronales para aprender a ejecutar la mejor acción para un estado dado. Se van a aplicar las mejoras que se comentan en la Sección 3.5 de redes neuronales. En este caso, no se pueden aplicar las mejoras del algoritmo anterior, pues no es una matriz que se pueda dividir el trabajo, si no una red neuronal cuyos pesos varían al ejecutar acciones en estados. 3.4. Algoritmos Evolutivos Los algoritmos evolutivos son sencillos de paralelizar. Trabajan con poblaciones de individuos que evolucionan a lo largo de las generaciones. Los individuos se someten a operaciones para producir nuevas generaciones. Estas operaciones de cada método son independientes, pues se puede dividir el cálculo entre varios procesos. Los métodos son las siguientes: 1. Inicialización. Dados los parámetros iniciales se crea la población con los individuos deseados. Hay diferentes tipos, con sus respectivas características. 49
Binarios. Estos individuos son fáciles de inicializar, pero ralentizan la comunicación entre procesos, debido al gran elevado número de bits que es necesario enviar. Sin embargo, se puede enviar el número con su representación real en lugar de enviar todos los bits. Reales. Al igual que los binarios son fáciles de inicializar, pero esta vez son más portables, al usar la base 10 como representación de los números, en vez del sistema binario (0's y 1's). Árboles. Más lentos para inicializar y difíciles de tratar. Se usan punteros y aumenta la complejidad al gestionarlos. 2. Evaluación. Este es la parte del algoritmo que más tiempo de ejecución puede llegar a consumir. Varía dependiendo del tipo de individuo. Como su nombre indica, evalúa a todos los individuos dependiendo de una función de tness , que puede ser desde una fórmula matemática hasta una ejecución de un algoritmo en un entorno. 3. Selección. Se seleccionan a los individuos para una nueva generación. La aleatoriedad predomina en este método, y dependiendo de la estrategia escogida se puede dar más o menos probabilidad a los más aptos. 4. Cruce. Con una probabilidad dada, los individuos se cruzan para introducirlos a la nueva generación. Normalmente tendrán un mayor coste temporal que el método anterior, pues hay que realizar modicaciones en los individuos para realizar el cruce. 5. Mutación. Igual que el cruce, tiene una probabilidad para mutar. Normalmente es un poco más veloz que el cruce, debido a las estrategias implementadas y la probabilidad de mutación suele ser menor a la de cruce, provocando una menor tasa de ejecución en esta parte. En este trabajo se desarrollan los siguientes problemas a optimizar para los tres tipos de individuos implementados: 50
neuronas, una para cada variable, y la salida es el IMC, por lo que la capa de salida es una única neurona. La capa de entrada y salida no varían, pero la capa oculta se puede modicar libremente, aumentando el tiempo de la fase de entrenamiento. Como en algunos de los algoritmos anteriores, necesitamos encontrar la mejor conguración de los hiper-parámetros. En las redes neuronales solo hay uno. La tasa de aprendizaje controla la magnitud de los ajustes a realizar en los pesos de las neuronas durante el proceso de entrenamiento. Especícamente, determina cuánto deben cambiar los pesos en respuesta al error cometido a predecir un individuo. Por ello, diseñamos una estrategia para encontrar la mejor tasa de aprendizaje para una red neuronal en concreto. El proceso master envía intervalos de tasas de aprendizaje a todos los procesos workers ejecutados, para que éstos ejecuten el algoritmo y envíen el sumatorio de errores obtenidos en la predicción. La inicialización de los pesos normalmente es aleatoria, pero para hacer más igualitario el cálculo de los errores, todos los procesos inicializan la red neuronal con los mismos pesos. Las estrategias MPI realizadas son las siguientes: 1. Pipeline. Como en el algoritmo anterior, pero esta vez con un ujo de mensajes bidireccional. 2. Dividir el trabajo entre los procesos. Segmentar el proceso de entrenamiento puede llegar a ser benecioso. Cada proceso se encarga de una capa de la red neuronal, siendo el master el encargado de enviar individuos de la población categorizada. El último worker controla la capa de salida, y con las etiquetas de los individuos, calcula el error y lo propaga hacia atrás. Para el correcto funcionamiento, hay que crear un buen diseño para tener un ujo constante de mensajes, los cuales pueden ser síncronos, es decir, que esperan a recibir los mensajes, o asíncronos, siendo estos últimos solamente admisibles en la etapa de recibir mensaje de una propagación hacia atrás anterior y enviar mensaje hacia adelante del individuo actual. La Figura 3.15 muestra dicho ujo y el trabajo de los procesos es el siguiente: 57
1. El master envía un número proporcional de individuos a los procesos en ejecución. Luego, antes de enviar otro individuo, entra en un bucle en el cual recibe el error de un individuo ya enviado, actualizando sus neuronas, y envía otro individuo. Para nalizar recibe el mismo número de errores (actualizando las neuronas) que individuos envió al principio. 2. El último worker solo recibe las predicciones y calcula el error. 3. Los workers de la capa oculta tienen un proceso más complejo. Primero, reciben un número de individuos proporcional a su id , los procesan y envían. Después entran en un bucle en el cual: Reciben de la capa siguiente: los errores, actualizan sus pesos y lo propagan enviando lo a la capa anterior. Reciben de la capa anterior: los nuevos individuos, procesan y propagan hacia adelante. Al ser un proceso iterativo, en el cual el modelo va aprendiendo en la fase de entrenamiento, a primera vista, dividir la población entre procesos (segunda estrategia) no parece ser benecioso para el correcto aprendizaje de la red. Sin embargo, en redes neuronales hay un proceso llamado ne tuning 13 que consiste en entrenar una red neuronal, con unos pesos ya calculados. Basándonos ligeramente en esta técnica, podemos implementar una mejora en la cual dividamos la población inicial entre procesos y, en paralelo, ejecutamos la fase de entrenamiento. Una vez nalizadas, el master recibe los pesos de cada worker y hace la media. Cuanto más grande sea la red neuronal mayor será -a prioriel speed-up . Las neuronas varían sus pesos para adaptarse a las variables recibidas. Para predecir un individuo, todas las neuronas trabajan en conjunto. Lo que supone que una neurona perteneciente a una red de menor tamaño tendrá más relevancia en comparación con una neurona en una red de mayor escala. Esto plantea un interrogante: ¾es posible paralelizar el trabajo de una red neuronal de gran escala y conservar -o reducirel porcentaje de error al 58
Figura 3.15: Primera estrategia en el algoritmo Red Neuronal predecir individuos? Para ponerlo a prueba hay que probar varias estrategias de agrupaciones en la población que se va a utilizar para entrenar la red neuronal, además de tener en cuenta la inicialización de los pesos. 1. Misma población en todos los procesos. Si cada proceso tiene la misma población y los mismos pesos en la red, se reduce el tiempo de ejecución, pero no mejora la predicción. Sería como ejecutar el algoritmo sin paralelizar, pero con menos iteraciones, pues se ejecutan en los procesos la misma ejecución y la media no varía con respecto a los resultados obtenidos. Inicializando las distintas redes neuronales con pesos diferentes, puede predecir correctamente para este problema en particular, pero no tener unos buenos resultados de manera global o viceversa. Además, depende de la aleatoriedad, pues 59
el porcentaje de errores en una ejecución puede variar bastante con respecto a otra. 2. Diferentes poblaciones para cada proceso. Esta estrategia suena mejor que la anterior. Al no haber intersección de poblaciones en los procesos ejecutados, los valores de los pesos se modicarán de diferente forma y puede que al hacer la media la red se estructure de forma que se obtenga un correcto funcionamiento. La inicialización de los pesos no provoca una gran diferencia, al contrario que mantener la misma población para todos los procesos. En cualquier caso, conviene probar ambas inicializaciones. 60
Capítulo 4 Estudio empírico Después de diseñar e implementar las estrategias descritas en la Sección 3, llevamos a cabo un análisis exhaustivo para evaluar los tiempos de ejecución de cada una, así como contrastar resultados y extraer conclusiones Primero, se ejecutan los experimentos en un ordenador de propósito general. Seguidamente se ejecutan las mejores implementaciones en un sistema distribuido con un número elevado de núcleos de CPU. 4.1. Entornos de ejecución Para ejecutar los experimentos y comprobar el funcionamiento de las implementaciones, primero se ejecutan en un ordenador de propósito general. Este sistema computacional tiene las siguientes especicaciones: Procesador (CPU): AMD Ryzen 7 , con 8 núcleos y 16 hilos, a 4.20 GHzs Memoria (RAM): 32 GB de RAM DDR4 , permitiendo una amplia capacidad para manejar grandes volúmenes de datos en memoria. Característica fundamental para ejecutar algoritmos de IA que demandan una cantidad elevada de recursos. Tarjeta Gráca (GPU): NVIDIA GeForce RTX 3070 con arquitectura Ampere 17 , que cuenta con 5888 núcleos CUDA y 8 GB de memoria GDDR6. La arquitectura Ampere 61
es sucesora de la arquitectura Turing lanzada en 2020. Fue diseñada para brindar un mejor rendimiento, especialmente en aplicaciones de computación paralela. Placa Base: X570 Gaming . Soporta las tecnologías de conectividad de alta velocidad, garantizando el rendimiento y estabilidad del sistema en condiciones de carga elevada. El sistema distribuido consta de tres ordenadores. Uno que funciona de Front-End y dos como nodos de cómputo, sumando entre estos últimos 128 núcleos de CPU y 256 GB de RAM. La gura 4.1 muestra la estructura del cluster . El Front-End realiza la conexión remota con los otros dos ordenadores, situados en la Facultad de Informática de la Universidad Complutense de Madrid. Este ordenador no participa en el cómputo, solo mantiene los scripts (tipo de chero de texto con el código escrito en un lenguaje de programación, en este caso Python) y lanza los experimentos sobre los nodos de cómputo. Durante las pruebas, cada proceso tiene un núcleo dedicado, por lo que el rendimiento de cada proceso no se ve afectado por otros procesos del sistema. Esto permite mayor precisión para evaluar el rendimiento del sistema, y las pruebas ejecutadas no compiten por los recursos de la CPU. Figura 4.1: Estructura del sistema distribuido de la Facultad de Informática 62
Para realizar las pruebas se usan las funciones open() y write() de Python para almacenar los tiempos de ejecución en cheros de texto. Los tiempos se miden con las funciones de tiempo de MPI, MPI.Wtime(). 4.2. Programas sencillos Primero realizamos el estudio de los programas básicos descritos en la Sección 3.1, ordenación de arrays y multiplicación de matrices. 4.2.1. Ordenaciones Las pruebas realizadas para estos algoritmos se realizan para el peor de los casos, es decir, un array de enteros sin repeticiones ordenado de forma decreciente. Cada algoritmo tiene que realizar el mayor número de comparaciones posible para ordenar el array de manera creciente. El resultado de cada experimento (tiempo de ejecución en segundos) es almacenado en un chero de texto. Seguidamente se aumenta el tamaño del array para ejecutar el siguiente experimento, hasta llegar a 100.000 elementos. 4.2.1.1. Algoritmos de complejidad cuadrática Debido al coste cuadrático de estos algoritmos, el incremento entre pruebas del tamaño de los arrays se obtiene de la siguiente forma: [20 −1,000) → 20 elementos. [1,000 −10,000) → 250 elementos. [10,000 −100,000) → 1.000 elementos. SelectionSort es fácilmente paralelizable, pues para cada elemento se comprueba cuantos elementos en el array son mayores. Las estrategias implementadas utilizan el modelo MasterWorker . El master envía a cada proceso worker un elemento del array para que hagan las comparaciones y devuelvan el índice del elemento, junto con el número de elementos mayores que el recibido, y así el master se encarga de ordenar el array y enviar elementos sin procesar. 63
La Figura 4.2 muestra los tiempos de ejecución. En rojo el algoritmo sin mejora, y en verde y negro las dos estrategias ejecutadas con cinco procesos. Se puede apreciar una considerable reducción del tiempo de ejecución. Al comparar las dos estrategias MPI, se obtiene que la primera estrategia es un 34% más rápida que la segunda. Sin embargo, la segunda estrategia tiene una menor complejidad espacial, mostrando en la gráca de la derecha, en negro, que la memoria no varía al aumentar los procesos ejecutados. 0246 0 100 200 Tam. Array ( 104 ) Tiempo de ejecución (s) Secuencial MPI_1 MPI_2 2 3 4 5 6 7 8 9 10 0 2 4 6 8 10 12 Num. Procesadores Memoria (Copias del array) MPI_1 MPI_2 Figura 4.2: Tiempos de ejecución de las estrategias y su uso de Memoria para el algoritmo SequentialSort en ordenador de propósito general Una vez comparadas las estrategias con el algoritmo secuencial, podemos comprobar el rendimiento frente a los algoritmos conocidos. La Figura 4.3 muestra que SelectionSort (la línea negra) es la ordenación que mejores resultados obtiene, y BubbleSort (línea roja) la que peores. SelectionSort es, aproximadamente, 3.5 veces más rápida al ordenar 70.000 elementos. La ordenación SequentialSort sin paralelizar, es incluso más rápida que dos de las más conocidas. Esto es debido a la simpleza de las operaciones aplicadas en la ordenación, pues solo hace N2 comparaciones. En BubbleSort e InsertionSort , además de realizar comparaciones, modican las posiciones de los elementos en el array, aumentando el tiempo de ejecución. La estrategia MPI de SequentialSort que menos tiempo requiere (la primera) no obtiene 64
mejores resultados que la mejor ordenación sin mejoras ( SelectionSort ) hasta llegar a los cuatro procesadores, siendo un 20% más veloz. Para mostrar de forma más clara la diferencia de tiempos entre estas dos ordenaciones, se muestra la ejecución de la primera estrategia con cinco procesadores (Sequential_MPI(5)), obteniendo un 50% de mejora. 012345678 0 100 200 300 Tam. Array ( 104 ) Tiempo de ejecución (s) Bubble Insertion Selection Sequential Sequential_MPI(5) Figura 4.3: Tiempo de ejecución de los algoritmos de ordenación cuadráticos en ordenador de propósito general 4.2.1.2. Algoritmo MergeSort Este algoritmo no tiene un coste tan elevado como los anteriores. La complejidad es logarítmica O(NLogN) lo que provoca que se pueda aumentar el tamaño del array a ordenar. Para la estrategia implementada, no se aplica el modelo Master-Worker , sino que todos los procesos creados trabajan de manera equitativa. Como se dijo en la Sección 3.1, esta estrategia usa potencias de dos procesos para ordenar el array. En cada iteración los procesos se comunican con el más cercano, uno le envía su subarray ordenado y termina su ejecución (el de mayor id de cada pareja), mientras que el otro reordena los dos subarrays y continúa a la siguiente iteración. En esta ocasión, la prueba realizada consiste en ordenar de manera creciente cuatro arrays de enteros inicializados de manera decreciente (peor de los casos), empezando con 25.000 elementos e incrementando esa misma cantidad entre los experimentos. Pese a tener 65
solo ocho núcleos en el ordenador de propósito general, se comprueba el rendimiento de la estrategia con 4 , 8 , 16 y 32 procesos. La Figura 4.4 muestra los resultados obtenidos en forma de histograma. Como la estrategia aplica ordenaciones cuadráticas en los subarrays al comienzo del algoritmo, no se obtienen buenos resultados con pocos procesos, debido al elevado tamaño del array a ordenar. Con dos procesos no reduce el tiempo de ejecución, lo duplica. El cómputo es equivalente a aplicar una ordenación cuadrática con la mitad del array a ordenar. No obstante, se puede apreciar una notoria reducción del tiempo de ejecución a partir de 16 procesos, llegando a tener un speed-up aproximado de 15.5 . Es cierto que se podrían aplicar otras ordenaciones con menor complejidad para reducir más el tiempo, pero así se demuestra que en la computación de alto rendimiento se pueden obtener buenos resultados con estrategias no tan efectivas, pero bien paralelizadas. 25 50 75 100 0 10 20 Tam. array ( 103 ) Tiempo de ejecución (s) Secuencial MPI(4) MPI(8) MPI(16) MPI(32) Figura 4.4: Tiempo de ejecución del algoritmo MergeSort en ordenador de propósito general La memoria está optimizada, puesto que el array está dividido entre los procesos. Al terminar un proceso con la sincronización en mariposa comentada en la Sección 3.1, se termina la ejecución del proceso liberando memoria una vez ha enviado al proceso correspondiente su subarray ordenado. Seguidamente, pasamos a comentar las pruebas realizadas en el sistema distribuido. El algoritmo secuencial de MergeSort tarda unos 20.16 segundos en ordenar, de manera 66
1000 2500 5000 0 200 400 600 800 1,000 1,200 Tam. Población Tiempo de ejecución (s) Secuencial MPI(2) MPI(4) MPI(6) MPI(8) Figura 4.9: Tiempo de ejecución de la distancia entre clusters por centroide del algoritmo Jerárquico Aglomerativo en ordenador de propósito general Ahora veamos el comportamiento de las estrategias para la distancia entre clusters con mayor complejidad, enlace simple o completo . Las pruebas se realizan con tamaños de poblaciones inferiores a las pruebas anteriores. Estos son los siguientes [100, 200, 500, 1000, 1500, 2000] , y se ejecutan las estrategias con cuatro procesos para comprobar el rendimiento. La tercera estrategia tiene el mismo rendimiento que la segunda, pero con más procesos. Reservar procesos únicamente para el cálculo de nuevas distancias no es ecaz, es mejor dividir entre los procesos activos (segunda estrategia). La Figura 4.10 muestra los resultados obtenidos del estudio. Aunque sí reduce el tiempo de ejecución, no se obtienen buenos resultados, pues el speed-up con 2000 individuos de población para la estrategia con mejores resultados es de 1.88 . Al usar cuatro procesos, podemos concluir que los tres workers pierden mucho tiempo calculando las distancias en cada iteración. Es posible que, mediante la renación progresiva de la segunda estrategia a través de un proceso iterativo de prueba y error, se logre reducir el tiempo de ejecución. No obstante, hasta el momento, no hemos logrado reducirlo más allá del tiempo actual. Los resultados de la prueba anterior, con la complejidad del algoritmo indican que no 73
0 200 400 600 800 1,000 1,200 1,400 1,600 1,800 2,000 0 50 100 Tam. Población Tiempo de ejecución (s) Secuencial MPI_1(4) MPI_2(4) Cores Figura 4.10: Tiempo de ejecución de la distancia entre clusters por enlace simple del algoritmo Jerárquico Aglomerativo en ordenador de propósito general es viable probar las estrategias implementadas sobre estas distancias entre cluster en el sistema distribuido. Por este motivo, solo se prueba la distancia por centroides con tres grandes poblaciones. Los tamaños son los siguientes [5000, 7500, 10000] , y se prueban con 20 , 50 , 75 , 100 y 128 procesos. La Figura 4.11 muestra los resultados, y concluimos que para agrupar tamaños de poblaciones elevados no conviene aplicar este algoritmo. 5 7,5 10 0 200 400 600 Tam. Población ( 103 ) Tiempo de ejecución (s) 20 50 75 100 128 Cores Figura 4.11: Tiempo de ejecución de la distancia entre clusters por centroide del algoritmo Jerárquico Aglomerativo en Cluster 74
O por lo menos las estrategias implementadas no dan resultados notorios, pues el speed-up entre usar 20 o 128 procesos en una población de 10000 individuos es de 2.32 . 4.3.2. K-Medias El algoritmo anterior no tiene ninguna variable que modique el tiempo de ejecución (sin contar la distancia entre clusters). Esta técnica de agrupación tiene un coste temporal mucho menor que el aglomerativo, O(N*K*iter) siendo N el tamaño de la población, iter las iteraciones hasta que no cambien los centros y K el número de centros. (N ≫ K,iter) K e iter no son valores muy altos, por lo que la complejidad no llega a ser cuadrática. Cuanto mayor sea el valor de K , más tiempo va a consumir para realizar la asignación, pues cada individuo de la población es comparado con más centros. No obstante, dependiendo de la asignación de los individuos, una ejecución con más centros puede ser más rápida que otra con menos centros. Todo depende de la variable iter , es decir, si consigue llegar antes a la condición de nalización (que los centros no cambien entre dos iteraciones). La Figura 4.12 muestra precisamente este punto. Para dos poblaciones distintas, de 75000 y 100000 individuos aplicando K=25 centros (línea roja), requieren aproximadamente el mismo tiempo. La primera población itera muchas veces, más en concreto, el doble de veces que la segunda población para nalizar la ejecución. Una ejecución del algoritmo sobre una misma población puede variar considerablemente dependiendo del número de centros, o la disposición de los mismos. Las distancias entre individuos siguen presentes, pero esta vez, al tener una complejidad menor, no debería afectar tanto usar la distancia Euclídea o Manhattan . O eso es lo que parece a simple vista. Como se comprobó en la Figura 4.12, el número de iteraciones para llegar a la condición de nalización importa, y usar una distancia u otra va a inuir en el tiempo de ejecución. El número de iteraciones varía dependiendo de qué distancia se use, pues la Euclídea , aunque su cálculo es más lento, tiene una mayor precisión, lo que le da una gran ventaja frente a la distancia Manhattan . Esta última, al no ser tan precisa, puede 75
25000 50000 75000 100000 0 20 40 60 80 100 120 Tam. de la Población Tiempo de ejecución (s) 5 10 25 50 K 5 10 25 50 K Figura 4.12: Variaciones en el número de clusters (K) en el algoritmo K-Medias hacer que, aunque sea por poco, un individuo pertenezca a otro cluster , provocando una reacción en cadena que resulte en un aumento considerable en el número de iteraciones. El estudio realizado para comprobar el rendimiento de la estrategia comentada en la Sección 3.2.2 con cinco procesos frente el algoritmo secuencial, se representa en la Figura 4.13, utilizando K=10 centros, y comparando también las distancias entre individuos ( Euclídea y Manhattan ). Los tamaños de las poblaciones utilizadas para medir estas pruebas se realizan como en las pruebas de las ordenaciones cuadráticas (ver Sección 4.2.1.1). Se puede apreciar que las funciones tienen picos, siendo más pronunciados en los algoritmos sin paralelizar. Como se comentó anteriormente, el tiempo de ejecución para una población puede variar dependiendo de la distancia implementada, además de la posibilidad de que una población con menor tamaño pueda tardar mucho más que una población mayor, debido a la disposición de los individuos y los clusters en la ejecución. Comparando el algoritmo secuencial y el paralelizado se puede apreciar una mejora considerable, y debido a los picos, es interesante medir la evolución de los speed-ups . La Figura 4.14 muestra esta evolución, cuyos speed-ups son calculados con los tiempos utilizados en la anterior gura. Ambas distancias comienzan siendo volátiles, siendo algunas veces peor que el algoritmo secuencial ( speed-up<1 ) y otras veces superando por mucho el speed-up 76
012345678910 0 20 40 60 Tam. Población ( 104 ) Tiempo de ejeución (s) Euclídea Manhattan Euclídea_MPI(5) Manhattan_MPI(5) Figura 4.13: Tiempo de ejecución -con 5 procesosde la primera estrategia del algoritmo K-Medias en ordenador de propósito general ideal. A partir de diez mil individuos de población, el speed-up es equivalente al número de workers ejecutados. Tras analizar los resultados, observamos que, pese a que la distancia Euclídea es más precisa, a la larga es mejor aplicar distancia Manhattan , pues, aunque itere más veces, el coste es menor, llevando a conseguir mejores resultados. Se puede apreciar la línea azul superando en la mayoría de las veces a la línea roja, probando lo comentado. 012345678910 0 2 4 6 8 Tam. Población ( 104 ) speed-up Ideal Euclídea Manhttan Figura 4.14: Speed-up de la primera estrategia del algoritmo K-Medias en ordenador de propósito general usando 5 procesos Para este algoritmo, al contrario que el anterior, se pueden realizar pruebas con tamaños 77
de poblaciones mayores en el sistema distribuido. La siguiente prueba realizada comienza con una población de 20000 individuos, esta vez con cinco variables de entrada. Entre pruebas se aumenta ese mismo tamaño hasta llegar a 240000 individuos, utilizando en proporción una población seis veces mayor que en el ordenador de propósito general. Se usa el mismo valor de K ( K=10 ), y se ejecuta la misma estrategia con 10 , 20 , 35 , 50 , 75 , 100 y 128 procesos. Como se muestra en la Figura 4.15, a partir de veinte procesos, la reducción del tiempo de ejecución se ralentiza. Con un número elevado de procesos, esta estrategia no consigue reducir el tiempo de ejecución en proporción a los procesos ejecutados, esto se debe a la gran cantidad de comunicaciones que se deben realizar para nalizar la ejecución. 2 4 6 8 10 12 14 16 18 20 22 24 0 200 400 600 Tam. Población ( 104 ) Tiempo de ejecución (s) 10 20 35 50 75 100 128 Cores Figura 4.15: Tiempo de ejecución de la primera estrategia del algoritmo K-Medias en el Cluster 4.3.3. KNN En cada iteración de este algoritmo de aprendizaje supervisado, se clasica un individuo utilizando una población previamente categorizada. Al contrario que los algoritmos de aprendizaje no supervisado, que agrupan una población entera al nalizar la población. La complejidad temporal de este algoritmo es menor, y el valor de K no inuye en el tiempo de ejecución como el algoritmo de K-Medias , pues al aumentar este valor solo aumenta el 78
número de los individuos más cercanos que se comprueban para categorizar el nuevo individuo. Este algoritmo usa dos poblaciones, y como se comentó en la Sección 3.2.3, las dos estrategias dividen una de las poblaciones para paralelizar el algoritmo. Para las siguientes pruebas realizadas en el ordenador de propósito general, se ja la misma población utilizada en el algoritmo anterior, con un tamaño de 100000 individuos para la población a categorizar. La población inicialmente categorizada tiene un tamaño de mil individuos y se obtiene realizando una búsqueda exhaustiva con el algoritmo K-Medias. Esta búsqueda se realiza con valores de K en el intervalo de [ 2, 20] centros, ejecutando, para cada uno, el algoritmo diez veces, calculando así la mejor agrupación. Se obtiene como resultado cuatro centros. Con estas dos poblaciones se ejecuta el algoritmo de K-Vecinos más Cercanos con un valor de K=15 , un número impar para que no haya posibilidad de empates a la hora de asignar un cluster a cada individuo. Primero comprobamos los dos métodos para el algoritmo secuencial, actualizar o no actualizar al categorizar un nuevo individuo. Si se actualiza la población conforme avanzan las iteraciones, la población nal será mucho más precisa que si no se actualiza, pero el tiempo de ejecución aumentará considerablemente. La Figura 4.16 muestra los resultados. Si no se actualiza, la complejidad es lineal, pues la población categorizada se mantiene constante, y no se puede diferenciar cuál de las dos distancias ralentiza más la ejecución. Sin embargo, cuando se actualiza la población, se comprueba una vez más que la distancia Euclídea es más lenta que la Manhattan . Después de comprobar el algoritmo secuencial pasamos a las estrategias para reducir el tiempo de ejecución. El algoritmo sin actualizar es rápido y es mejor estudiar el comportamiento con una población variable con el tiempo. Por eso se ejecutan las dos estrategias con cinco procesos. Podemos ver los resultados en la gura 4.17, con una reducción notoria en el tiempo de ejecución. Para la primera estrategia, dividir la población categorizada entre los workers , se realizan dos versiones, una en la que cada worker espera el individuo categorizado de la iteración anterior (línea de color verde), y otra en la que no se espera, sino que los 79
012345678910 0 2,000 4,000 Tam. Población ( 104 ) Tiempo de ejeución (s) Euclídea Euclídea_Act Manhattan Manhattan_Act Figura 4.16: Tiempo de ejecución del algoritmo secuencial KNN en ordenador de propósito general workers trabajan en la siguiente iteración mientras que el master agrupa el individuo (línea de color negro). La primera estrategia es ligeramente más rápida que la segunda (línea de color azul), y aun perdiendo tiempo esperando a la categorización del individuo (la primera versión), sigue nalizando antes que la segunda estrategia. En cuestión de complejidad espacial la segunda estrategia consume mucha más memoria. Al nalizar la ejecución, cada worker tiene una copia entera de la población categorizada, mientras que en la primera mejora se divide esta población entre los procesos. Comparando las evoluciones de los speed-ups en las estrategias, se puede concluir que al principio es mejor dividir la población a predecir, pero a largo plazo es más efectivo dividir la población categorizada, además de tener menos complejidad espacial. En algoritmos pasados ya hemos visto el funcionamiento de varias estrategias con tamaños de poblaciones elevados. Esta vez, para las pruebas en el sistema distribuido, ejecutamos la misma prueba que antes, pero con más procesos en paralelo. Se ejecutan 10 , 20 , 35 , 50 , 75 , 100 y 128 procesos sobre la mejor estrategia obtenida en el estudio anterior, comprobar el speed-up al usar muchos procesos. La Figura 4.19 muestra que, al aumentar los procesos, no se reduce considerablemente el tiempo de ejecución, generando sobrecarga a partir de veinte 80
Figura 4.17: Tiempo de las estrategias del algoritmo KNN en ordenador de propósito general 012345678910 2 3 4 5 Tam. Población ( 104 ) speed-up Ideal MPI_1 MPI_2 Figura 4.18: Speed-ups de las estrategias del algoritmo KNN en ordenador de propósito general procesos. Al igual que en el algoritmo K-Medias , aumentar el número de procesos provoca que, aunque se reduce el tiempo de ejecución en cada iteración, el tiempo de comunicación (overhead) entre iteraciones aumenta. 4.4. Q-Learning Para el aprendizaje por refuerzo, cuyos dos algoritmos se comentaron en la Sección 2.2, primero se estudia el algoritmo de Q-Learning . El otro algoritmo, Deep Q-Network , se basa 81
0 1 2 3 4 5 6 7 8 9 10 0 200 400 600 Tam. Población ( 104 ) Tiempo de ejecución (s) 10 20 35 50 75 100 128 Cores Figura 4.19: Tiempo de la primera estrategia del algoritmo KNN en Cluster en redes neuronales, estudio que se realiza posteriormente en la Sección 4.6. Antes de entrar en profundidad con las estrategias comentadas en la Sección 3.3, primero estudiamos el comportamiento del algoritmo de manera secuencial, con y sin preprocesado del entorno. Este preprocesado consiste en recorrer la matriz entera eliminando estados inaccesibles (el agente se sitúa en un muro) y acciones que no queremos que el agente ejecute, como chocar con una pared. Se ejecuta con tres laberintos diferentes, con 30 , 50 y 100 las. La Figura 4.20 muestra una leve reducción en el tiempo de ejecución. Además, obtiene mejores resultados con una mayor variedad de combinaciones de hiper-parámetros. Al reducir las acciones disponibles, el agente tiene una mayor probabilidad de explorar más el laberinto, generando más combinaciones con las cuales aprender el camino óptimo hasta la meta. Una buena conguración de hiper-parámetros genera que el agente logre alcanzar su objetivo. En entornos de gran tamaño, algunas veces, es complicado encontrar conguraciones que funcionen, lo que provoca un aumento en el tiempo dedicado a la fase de entrenamiento para encontrar estas combinaciones. Por este motivo, se desarrolla una estrategia para encontrar combinaciones de los hiper-parámetros realizando una búsqueda exhaustiva. 82
Cuadro 4.2: Tiempos unitarios de las partes del algoritmo evolutivo para cada individuo garantiza la supervivencia de los mejores individuos en la población general. Si usamos la topología en estrella, hay que reservar un proceso para que actúe como master para que éste realice el proceso de comunicación cada X generaciones. Las demás topologías (red y anillo) no tienen un proceso master por lo que se optimiza de mejor forma los recursos computacionales. Las pruebas realizadas a continuación se han ejecutado con la topología de anillo, con cuatro procesos. La Figura 4.23 muestra los resultados en forma de malla de 2x2 con los tiempos de ejecución de los algoritmos evolutivos con esta estrategia, separando las pruebas de los individuos reales (segunda la) debido a la diferencia de tiempos con respecto al problema con mayor tamaño ( AER3 ). Como se puede apreciar, se logra obtener una reducción del tiempo de ejecución proporcional al número de procesos ejecutados. El estudio de los speed-ups (gura 4.24) para los problemas de mayor tamaño de cada individuo, con- rma la proporcionalidad de la reducción del tiempo de ejecución con respecto al número de procesos ejecutados. La primera gráca de la primera la (ver Figura 4.23) muestra los resultados obtenidos para los individuos binarios, consiguiendo reducir el tiempo de ejecución. La segunda gráca de esta misma la muestra los resultados para los árboles, cuyo tiempo de ejecución de la estrategia sobre el segundo problema ( 1500 ticks ) es aproximadamente igual a los obtenidos para la ejecución secuencial del primer problema ( 150 ticks ). Como se 89
usan cuatro procesos y el primer problema es cuatro veces más rápido que el segundo, los resultados de estas ejecuciones se solapan, provocando que la línea verde y azul coincidan. Las grácas de los individuos reales de la segunda la, muestran un mismo comportamiento que las grácas anteriores con respecto a la reducción del tiempo de ejecución. 25 500 1,000 1,500 2,000 0 5 10 15 Binario P2 P10 P2_MPI(4) P10_MPI(4) 25 500 1,000 1,500 2,000 0 50 100 150 200 250 Árbol M10X10 M100X100 M10X10_MPI(4) M100X100_MPI(4) 25 500 1,000 1,500 2,000 0 5 10 15 Real AER 1 AER 2 AER 1_MPI(4) AER 2_MPI(4) 25 500 1,000 1,500 2,000 0 20 40 60 80 100 Real AER 3 AER 3_MPI(4) Tam. Población Tiempo de ejecución (s) Figura 4.23: Tiempos de ejecución de la estrategia modelo de islas de los algoritmos evolutivos en ordenador de propósito general 90
0 500 1,000 1,500 2,000 0 1 2 3 4 5 Tam. Población speed-up Ideal P10 AER3 M100X100 Figura 4.24: Speed-ups de la estrategia modelo de islas de los algoritmos evolutivos en ordenador de propósito general La estrategia de dividir la población entre los procesos tiene una complejidad mayor en lo que a lógica de programación se trata. Con el modelo de comunicación Master-Worker y una población de individuos, el master se encarga de dividir y enviar a los workers la población sobre la cual tienen que ejecutar las partes del algoritmo: cruce, mutación y evaluación en cada generación. Las siguientes pruebas se ejecutan con cuatro workers , cinco procesos en total contando al master . La Figura 4.25 muestra, en forma de malla 2x2 , los resultados obtenidos para los tres diferentes individuos. La primera gráca de la primera la muestra los resultados de los individuos binarios, unos tiempos de ejecución muy parecidos. Para el primer problema, usando 22 bits, no se logra reducir el tiempo de ejecución, pues se puede ver que empiezan de forma similar, pero con mil individuos se empiezan a distanciar. Esto no ocurre con el segundo problema ( 77 bits por individuo), la estrategia logra reducir levemente el tiempo de ejecución, y con dos mil individuos, la ejecución sigue siendo un poco más rápida. El factor que frena a esta estrategia de reducir el tiempo de ejecución es la complejidad de las operaciones a realizar en cada parte del algoritmo, pues son muy simples. Además, la comunicación entre procesos al enviar y recibir muchos bits aumenta el tiempo de ejecución. La segunda gráca de la misma la (ver Figura 4.25) muestra los resultados de los individuos representados como árboles, 91
siendo resultados parecidos a la anterior gráca comentada. Para el primer problema ( 150 ticks ) no se consigue reducir el tiempo de ejecución, no obstante, para el segundo si se logra, obteniendo, para la última población ( 2000 individuos), un speed-up de 1.84 . Las pruebas en los individuos reales, al igual que para la estrategia anterior, se dividen en dos grácas para poder ver con mayor exactitud los resultados obtenidos, estas grácas se sitúan en la segunda la (ver Figura 4.25). Al contrario que los otros dos individuos, este individuo si alcanza una reducción del tiempo de ejecución con todos los tamaños de problemas. La gráca de la izquierda muestra que la estrategia en los dos primeros tamaños alcanza un buen rendimiento, pero el tercer problema, al ser más grande, tiene una reducción del tiempo de ejecución más notoria. Como muestra la gráca de la derecha, se puede alcanzar un speed-up de 2.81 . Figura 4.25: Tiempo de ejecución de la estrategia dividir población de los algoritmos evolutivos de en ordenador de propósito general 92
La estrategia pipeline mezcla el modelo Master-Worker con segmentación. El proceso master se encarga de generar una población dividida entre N (número de workers ) subpoblaciones que envía al siguiente proceso (primer worker ). Cuando genera todas las subpoblaciones, se queda en un estado de recepción de mejores individuos. Cada proceso envía a su siguiente los datos procesados según su tarea, generando un ujo constante de trabajo. Esta estrategia varía para cada individuo, debido a que los tiempos en cada parte del algoritmo son distintos para cada uno. Estos tiempos se estudiaron previamente en la Tabla 4.2. La primera prueba se realiza sobre los individuos binarios, con precision=10 , cuyos procesos ejecutados se estructuran de la siguiente forma: Con cuatro procesos el master se encarga de inicializar. Los workers se dividen en tres pipes; el primer pipe se encarga de la evaluación y selección, el segundo del cruce y el tercero de la mutación. Con siete procesos: se duplica la ayuda para los workers en cada pipe. Los resultados son plasmados en la Figura 4.26, logrando reducir satisfactoriamente el tiempo de ejecución. El funcionamiento de pipeline reduce el tiempo de paso de mensajes, al optimizar la paralelización de las partes del algoritmo. 25 200 500 1,000 1,500 2,000 0 5 10 15 Tam. Poblacion Tiempo de ejecución (s) P10 MPI(4) MPI(7) Figura 4.26: Tiempo de ejecución de la estrategia pipeline en los individuos binarios del algoritmo evolutivo en ordenador de propósito general 93
Los individuos reales y árboles tienen tiempos de ejecución muy parecidos. Es por eso que se obtendrían los mismos resultados al aplicar la misma repartición de tareas, siendo esta la siguiente: Con seis procesos: el master se encarga de inicializar. Los workers con ids en el intervalo [1-4] se encargan de la evaluación, pues esta parte del algoritmo consume cuatro veces más tiempo que los restantes. El último worker se encarga de la selección, cruce y mutación. Con diez procesos: se duplica la ayuda para los workers en la función de evaluación. Alcanzando, con este reparto de tareas, una igualdad en los tiempos de ejecución de los dos tipos de procesos worker . Es decir, con ocho workers se logra reducir el tiempo de ejecución al mismo tiempo que el del worker que realiza las otras partes del algoritmo. Como muestra la Figura 4.27, los individuos reales también presentan un buen rendimiento. Aunque duplicando los procesos workers de la función de evaluación (linea azul), se obtiene unos tiempos de ejecución similares a los obtenidos con seis procesos. 25 200 500 1,000 1,500 2,000 0 50 100 Tam. Poblacion Tiempo de ejecución (s) AER3 MPI(6) MPI(10) Figura 4.27: Tiempo de ejecución de la estrategia pipeline en los individuos reales del algoritmo evolutivo en ordenador de propósito general En el cluster se han realizado pruebas para las estrategias de dividir la población y pipeline . La estrategia de modelo de islas no se ha realizado debido a que ya se han realizado varias pruebas en el sistema distribuido con esta estructura de dividir el algoritmo secuencial 94
entre varios procesos. Ambas pruebas tienen los siguientes tamaños de poblaciones [ 1000 , 2000 , 5000 , 7000 ]. La estrategia de dividir la población se ejecuta sobre individuos reales, con 10 , 20 , 50 , y 100 procesos. La Figura 4.28 muestra dichos resultados. Como se puede ver en el gráco, a partir de 20 procesos la reducción del tiempo de ejecución empieza a ralentizarse. En el último tamaño de poblaciones, se logra obtener un menor tiempo con 50 procesos que al usar 100 . La sobrecarga producida por la comunicación entre un número elevado de procesos workers y el master generan dichos resultados. La estrategia de pipeline se ejecuta sobre individuos árboles, siguiendo el mismo reparto de tareas que la utilizada para los individuos reales. Como se comentó antes, al llegar a 10 procesos se alcanza una igualdad en los tiempos de ejecución. Es por esos que los procesos ejecutados para esta prueba son múltiplos de este número, siendo 10 , 20 , 40 y 80 . Entre cada prueba se duplican los procesos involucrados en cada tarea, incluyendo la inicialización de los individuos realizada por el proceso master . Los resultados obtenidos son mostrados en la Figura 4.29. Se puede apreciar un comportamiento similar a la Figura 4.28 del párrafo anterior, en el cual al llegar a 40 procesos se obtienen aproximadamente los mismos resultados que duplicando los procesos. 12345678910 0 100 200 Tam. Población ( 103 ) Tiempo de ejecución (s) 10 20 50 100 Cores Figura 4.28: Tiempos de ejecución de la estrategia dividir la población en los individuos reales del algoritmo evolutivo en Cluster 95
12345678910 0 5 10 15 20 Tam. Población ( 103 ) Tiempo de ejecución (s) 10 20 40 80 Cores Figura 4.29: Tiempo de ejecución de la estrategia pipeline en los individuos árboles del algoritmo evolutivo en Cluster 4.6. Redes Neuronales Este modelo de inteligencia articial necesita una cantidad elevada de datos, utilizados en la etapa de entrenamiento para, de manera correcta, predecir los individuos. El algoritmo de DQN, comentado en la Sección 2.2.2, no necesita de un conjunto de datos, al ser un entorno en el cual un agente ejecuta acciones. Su etapa de entrenamiento consiste en ejecutar muchas veces diferentes ejecuciones para que aprenda a moverse por el entorno, modicando la red neuronal. Sin embargo, se pueden cambiar los estados con los cuales el agente comienza cada iteración, cambiando los variables del entorno para que sean accesibles. Ahora bien, para la predicción del índice de masa corporal (IMC) de un individuo, se necesita de una población con la cual enseñar a la red neuronal a predecir. Es por eso que se generan individuos de manera secuencial, variando sus valores para que no sean idénticos, y lograr así una población con la cual poder ejecutar el entrenamiento. Es importante resaltar que estos individuos tendrán una conexión con la realidad. Los individuos tienen alturas dado el siguiente intervalo en centímetros [150, 200] , y el peso varía con valores entre de 25 kilogramos por encima y debajo del peso ideal para cada altura ( IMC = 22.5 ). Esto quiere decir que, si un individuo mide 180 centímetros, su peso se genera aleatoriamente con el siguiente intervalo de kilogramos [55, 105] . 96
La primera estrategia, pipeline de individuos, se logra generando en la capa de salida los individuos, siendo gestionados por el proceso master . Los demás procesos (los workers ) gestionan las posteriores capas creadas. La siguiente prueba tiene una población de 2000 individuos, previamente generados como se comentó en el párrafo anterior. La red neuronal tiene una parte oculta con dos capas y cincuenta neuronas cada una ( 2x50 ). Con cinco repeticiones, se entrena la red neuronal con 10000 individuos en total, dando los resultados que se muestran en la Figura 4.30. Esta estrategia, tanto aplicando mensajes síncronos como asíncronos, no surte mucho efecto, pues en vez de reducir el tiempo de ejecución lo aumenta. En programación evolutiva, el ujo de mensajes es unidireccional, y no se pierde tanto tiempo entre mensajes. Este algoritmo, al tener dos métodos en diferentes direcciones, provoca un ujo bidireccional, y la comunicación entre procesos se ralentiza. Usando mensajes asíncronos, permite a cada proceso ejecutar antes el cálculo de forward (hacia adelante) y cuando recibe los errores los actualiza. Reduce muy poco el tiempo comparándolo con la versión síncrona. Además, hay que tener en cuenta que el ujo de mensajes hace que el modelo aprenda con valores desactualizados. Dependiendo de la población, puede situarse en un bucle en el cual aumenta y reduce los pesos, provocando un entrenamiento erróneo. 012345678910 0 5 10 Num. Repeticiones ( 103 ) Tiempo de ejeución (s) Secuencial Síncrono Asíncrono Figura 4.30: Tiempo de ejecución de la estrategia pipeline de Red Neuronal en ordenador de propósito general La estrategia de dividir el proceso en entrenamiento entre varios procesos, ya se ha 97
comprobado que funciona correctamente en otros algoritmos como pueden ser Q-Learning y programación evolutiva con el modelo de islas, además de basarse ligeramente en la idea de ne-tuning . Esta vez, hay que tener en cuenta que la etapa de entrenamiento es un proceso iterativo en el cual se predice un individuo y se actualiza los errores cometidos, siendo un proceso complicado de lograr satisfactoriamente. La Figura 4.31 muestra la prueba realizada con una población de 80 individuos y 1000 repeticiones, sumando un total de 80000 individuos predichos en el entrenamiento. Se aplica el modelo Master-Worker para paralelizar el entrenamiento con 3 y 5 procesos, y una vez terminado enviar los pesos al master para realizar la media, intentando maximizar las predicciones nales. El master se encarga de dividir la población, siguiendo alguno de los métodos comentados en el nal de la Sección 3.5. Se puede apreciar una reducción del tiempo de ejecución proporcional al número pe procesos worker ejecutados. 012345678910 0 50 100 150 200 250 Num. Repeticiones ( 103 ) Tiempo de ejeución (s) Secuencial MPI(2) MPI(4) Figura 4.31: Tiempo de ejecución de la estrategia de dividir el trabajo de la Red Neuronal en ordenador de propósito general La repartición de individuos es crucial para un correcto aprendizaje de la red. No obstante, esta estrategia no converge en buenas predicciones. Hacer la media de los pesos de las neuronas obtenidos en cada proceso, no da buenos resultados. Si comprobamos la efectividad de una red sin entrenar, únicamente inicializados los pesos de manera aleato98
One of the most important things I have learned throughout this work is that more is not always better . Increasing the computational resources does not always have a proportional impact on the overall system performance. The overhead of processes in implementations is a fundamental thing to take into account when executing programs, and in life itself. As future work, it is proposed to investigate other algorithms of the developed techniques, in addition to investigating and improving other AI techniques, such as natural language processing. 105
Bibliografía [1] Bloom AI. Último acceso: 2024-02-08. https://bloomai.co/ . [2] ChlouisPy - Maze generator. Último acceso: 2024-02-21. https://github.com/ ChlouisPy/maze-generator-maze-solver . [3] Marcel R. Ackermann, Johannes Blömer, Daniel Kuntze, and Christian Sohler. Analysis of agglomerative clustering. Algorithmica , 69:184215, 2014. [4] Nicolas Auger, Cyril Nicaud, and Carine Pivoteau. Merge strategies: from merge sort to timsort. 2015. [5] Brandon Barker. Message passing interface (mpi). In Workshop: high performance computing on stampede , volume 262. Cornell University Publisher Houston, TX, USA, 2015. [6] Marco A. Contreras-Cruz, Víctor Ayala-Ramírez, and Uriel H. Hernandez-Belmonte. Mobile robot path planning using articial bee colony and evolutionary programming. Applied Soft Computing , 30:319328, 2015. [7] Flor A. Espinoza, Janet M. Oliver, Bridget S. Wilson, and Stanly L. Steinberg. Using hierarchical clustering and dendrograms to quantify the clustering of membrane proteins. Bulletin of mathematical biology , 74:190211, 2012. [8] Frédérick Garcia and Emmanuel Rachelson. Markov decision processes. Markov Decision Processes in Articial Intelligence , pages 138, 2013. [9] Henrik Jeppesen. Carbon tracker initiative. In World Scientic Encyclopedia of Climate Change: Case Studies of Climate Risk, Action, and Opportunity Volume 1 , pages 6369. World Scientic, 2021. 106
[10] Keith Kirkpatrick. The carbon footprint of articial intelligence. Communications of the ACM , 66(8):1719, 2023. [11] Frances Y Kuo and Ian H Sloan. Lifting the curse of dimensionality. Notices of the AMS , 52(11):13201328, 2005. [12] Giuseppe Lugano. Virtual assistants and self-driving cars. In 2017 15 th International Conference on ITS Telecommunications (ITST) , pages 15. IEEE, 2017. [13] Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D Lee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes. Advances in Neural Information Processing Systems , 36:5303853075, 2023. [14] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602 , 2013. [15] Surender Mor, Sonu Madan, and Kumar Dharmendra Prasad. Articial intelligence and carbon footprints: Roadmap for indian agriculture. Strategic Change , 30(3):269280, 2021. [16] Silviu Pitis. Rethinking the discount factor in reinforcement learning: A decision theoretic approach. In Proceedings of the AAAI conference on articial intelligence , volume 33, pages 79497956, 2019. [17] Je Pool. Accelerating sparsity in the nvidia ampere architecture. GTC 2020 , 2020. [18] José Jaime Ruz Ortiz. Multiprocesadores de memoria compartida y distribuida. Universidad Complutense de Madrid (UCM), 12/01/2016. [19] Mohd Shamrie Sainin. Best programming languages for AI. 2021. [20] Harold S Stone. High-performance computer architecture . Addison-Wesley Longman Publishing Co., Inc., 1990. 107
[21] Christopher A Thomas and Xander Wu. How global tech executives view us-china tech competition. 2021. [22] Yi Wang, Kok Sung Won, David Hsu, and Wee Sun Lee. Monte carlo bayesian reinforcement learning. arXiv preprint arXiv:1206.6449 , 2012. 108
Acrónimos MPAI Message Passing Articial Inteligence AI Articial Intelligence MPI Message Passing Interface CPU Central Processing Unit GB Giga-Byte RAM Random Access Memory CO2 Carbon Dioxide HPC High Performance Computing SPMD Single Program Multiple Data RL Reinforcement Learning MDP Markov Decision Process DQN Deep Q-Network KNN K-Nearest Neighbors PEV Programación EVolutiva 109