Universidad de Castilla-La Mancha
 
Escuela Superior de Ingeniería Informática

 

  cambiar a curso:   2021-22   2023-24



Grado en Ingeniería Informática


TRABAJOS FIN DE GRADO
curso: 2022-23

Búsqueda de configuraciones eficientes de la topología Dragonfly mediante algoritmos metaheurísticos


Tecnologías Específicas

Ingeniería de Computadores
 


Descripcion y Objetivos

Las redes de interconexión juegan un papel muy importante en los computadores masivamente paralelos de grandes centros de datos y supercomputación. Esta importancia se hace mayor al aumentar el rendimiento de los elementos de cómputo y el ancho de banda de la memoria. Las propiedades clave de las redes de interconexión de altas prestaciones vienen, en buena medida, determinadas por su topología, es decir, la disposición de los nodos (elementos de cómputo y almacenamiento, y conmutadores) y los cables que los interconectan.

Se han realizado numerosas propuestas de topologías para este tipo de redes, y en su diseño se suelen tener en cuenta diferentes métricas, como productividad, latencia, consumo, coste o tolerancia a fallos, entre otras. La red de interconexión tiene que soportar el tráfico generado por las aplicaciones y por tanto debe ofrecer un gran ancho de banda. Todos los componentes de la red suponen un porcentaje significativo tanto del coste total del sistema como de su consumo, por lo que la cantidad de estos componentes debe ser la menor posible, y la energía consumida por ellos también debe minimizarse.

Conseguir el valor óptimo de todos los aspectos que determinan el comportamiento de una topología no es tarea sencilla, e incluso puede resultar imposible debido a la dependencia entre ellos. En general, los diseños de la topología propuestos van acompañados de estudios teóricos y pruebas de simulación para mostrar su rendimiento. Sin embargo, estudios analíticos resultan inviables cuando el tráfico en la red no se adapta a ningún patrón regular y simple. Este es el caso de la mayoría del tráfico que generan aplicaciones que se ejecutan en sistemas multiprocesador.

En estos casos, para un tamaño de red dado, se podría pensar en analizar cada una de las posibles configuraciones de la red, encontrando así su configuración óptima. Pero esta opción es impracticable dado el alto número de configuraciones posibles. Una alternativa consiste en aplicar métodos o técnicas que sin necesidad de analizar todas las posibles configuraciones, ofrecen soluciones muy cercanas a las óptimas, cuando no las óptimas. Dichas técnicas además permiten alcanzar esas soluciones, configuraciones en este caso, en tiempos razonables.

En este Trabajo Fin de Grado (TFG) se ha optado por esta vía, utilizando alguna de las técnicas metaheurísticas que mejor se adapten al tipo de búsqueda que se debe realizar. La idea es explorar posibles soluciones/configuraciones de la red en conjuntos donde es más probable encontrar las mejores. Para no hacer excesivamente complejo el trabajo, se ha acotado el conjunto de configuraciones y las condiciones en las que se realizará la búsqueda.

En concreto, se ha elegido la topología Dragonfly para realizar el estudio, siendo el objetivo principal encontrar, utilizando algoritmos metaheurísticos, una configuración óptima para un conjunto dado de componentes de la red y algunos patrones de tráfico. Se pretende también que el trabajo realizado pueda ser fácilmente aplicado considerando otras condiciones de partida.

 

 


Metodología y Competencias

En el proceso de desarrollo del software, la metodología a utilizar será iterativa e incremental tipo Scrum, ajustando los requisitos de usuario según se vaya avanzando en el diseño e implementación.

Para alcanzar los objetivos del TFG, se han establecido varias actividades principales, las cuales se indican a continuación, señalando para cada una de ellas el tiempo en meses estimado de realización, asumiendo una dedicación total de 6 meses, 50 horas/mes y 300 horas de dedicación total al TFG.

1. Revisión y aprendizaje de los aspectos técnicos. Se deben refrescar los conocimientos generales sobre redes de interconexión, profundizando en aquellos que tienen que ver con la topología Dragonfly. De igual forma se hará con aquellos otros que tienen que ver con los conceptos teórico-prácticos sobre optimización combinatoria y técnicas metaheurísticas. En ambos casos se consultará la bibliografía adecuada: libros de texto, artículos o sitios web. Esta tarea tendrá una duración aproximada de un mes.

2. Definición del problema. En esta fase se especificarán los detalles relevantes que se tendrán en cuenta para elaborar el estudio, y que fundamentalmente serán las características de la topología, la carga que soportará y las métricas que servirán para establecer su comportamiento. De acuerdo con estos datos y el objetivo a lograr, se determinará la técnica metaheurística más adecuada y se diseñará la solución que finalmente será implementada. Esta tarea puede llevar un mes aproximadamente.

3. Implementación de la solución adoptada. En esta etapa, y de acuerdo con la información de la etapa anterior, se elaborará el código que permita alcanzar el objetivo principal del trabajo. Esta es una parte laboriosa y será la que más tiempo requiere, estimando una duración de 2 meses.

4. Obtención y análisis de resultados. En esta última etapa del proceso se diseñará, en primer lugar, un amplio conjunto de pruebas a realizar, indicando para cada caso cuáles serán los datos de entrada y los valores de los parámetros que deban intervenir. A continuación se realizarán las pruebas y se recogerán los resultados de las mismas, para posteriormente ser analizados. Finalmente, a partir de esos resultados se intentará dar respuesta a la cuestión que plantea el objetivo principal del proyecto. Un mes puede ser suficiente para completar esta parte del trabajo.

5. Elaboración de la memoria del TFG. A lo largo del trabajo se podrá ir avanzando en la escritura de la memoria, pero será en el último mes cuando se realiza la mayor parte de esta tarea.

 

Las competencias que se aplican en el caso de la Tecnología de Ingeniería de Computadores son:

[IC3] Capacidad de analizar y evaluar arquitecturas de computadores, incluyendo plataformas paralelas y distribuidas, así como desarrollar y optimizar software para las mismas. El trabajo se centra en redes de interconexión de computadores paralelos, y por tanto el conocimiento de este tipo de plataformas y de aspectos como la evaluación de sus prestaciones es esencial.

[IC7] Capacidad para analizar, evaluar, seleccionar y configurar plataformas hardware para el desarrollo y ejecución de aplicaciones y servicios informáticos. El objetivo del TFG es encontrar configuraciones óptimas de la red de interconexión de plataformas hardware concretas, por lo que se trabajará esta competencia durante el trabajo.

 


Medios a utilizar

El trabajo podrá realizarse en un ordenador personal, pero también se dará acceso al alumno a un servidor de altas prestaciones, con todos los recursos necesarios para editar, depurar y ejecutar el código que deberá desarrollar a lo largo del trabajo. Así mismo, si fuera necesario utilizar un simulador de redes de interconexión, se facilitará al alumno alguno de los simuladores de redes de interconexión disponibles en el grupo de investigación RAAP.

 


Bibliografía

[1]    J. Duato, S. Yalamanchili, L. Ni. "Interconnection Networks: An Engineering Approach". Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. 2002.

[2]    J. Kim, W. Dally, S. Scott, D. Abts. "Technology-Driven, Highly-Scalable Dragonfly Topology". Proc. Int’l Symp. Computer Architecture (ISCA 08), 77-78. 2008.

[3]    E.-G. Talbi. "Metaheuristics: From Design to Implementation". Wiley Publishing. 2009.

[4]    M. Gendreau, J.-Y. Potvin. "Handbook of Metaheuristics". (2nd. ed.). Springer Publishing Company. 2010.

 


Tutores


SÁNCHEZ GARCÍA, JOSÉ LUIS
GAMEZ MARTIN, JOSE ANTONIO
 

Alumno




 

 

Sindicación  Sindicación  Sindicación  Sindicación

Curso: 2022-23
© Escuela Superior de Ingeniería Informática
Edificio Infante Don Juan Manuel
Avda. de España s/n
02071 Albacete

informatica.ab@uclm.es
aviso legal
generar código QR de la página