N-dimensional twin torusformalization, routing strategies and optimal configuration

Resum

La red de interconexión es un componente clave de los supercomputadores actuales. Puesto que estos sistemas suelen estar compuestos por miles de nodos, es necesario emplear redes de interconexión de altas prestaciones para poder manejar de forma eficiente la comunicación generada por esta enorme cantidad de nodos. Existen diversos parámetros a tener en cuenta en el diseño de la red de interconexión, pero la elección de un topología adecuada determinará en gran parte el rendimiento global del sistema. Una de las topologías más populares en los supercomputadores actuales es el toro n-dimensional. Las propiedades de esta topología facilitan su implementación, además de proveer una buena escalabilidad. Por estas razones, los toros n-dimensionales son ampliamente utilizados en muchos de los supercomputadores más potentes de la actualidad. El rendimiento de una red toro n-dimensional depende directamente del número de puertos de los switches que componen la red. Cuanto mayor es el número de puertos, mayor puede ser el número de dimensiones. Aumentar el número de dimensiones conlleva una reducción de las distancias entre los nodos de la red, reduciendo la latencia de los mensajes y por lo tanto, incrementando el rendimiento de la red. Sin embargo, la complejidad del hardware es directamente proporcional al número de puertos, por lo que el coste económico de los switches también aumenta. Una posible solución para aumentar el número de puertos de los switches sin aumentar significativamente la complejidad del hardware consiste en combinar dos o más switches de pocos puertos para formar un único switch con muchos puertos. Esta estrategia permite superar las limitaciones impuestas por la tecnología actual. No solo eso, esta estrategia también continuará siendo válida cuando en el futuro la tecnología permita desarrollar switches con más puertos que los actuales. Esta propuesta se ha aplicado con éxito en redes indirectas, concretamente, en topologías fat-tree. Mediante el uso de C-switches, los cuales están formados por dos o más switches de menor tamaño, se puede reducir el número de etapas del fat-tree, y por lo tanto, reducir las latencias de red y aumentar el tráfico aceptado por la red. Esta misma estrategia puede aplicarse para aumentar el número de puertos de los switches en redes directas; o más concretamente, en toros n-dimensionales. Para analizar la viabilidad de la propuesta, se ha estudiado el caso más simple: combinar dos switches para construir un switch con más puertos. Como resultado, se ha propuesto una nueva topología llamada n-dimensional twin torus (o toro nDT). Cada nodo del toro nDT está compuesto por dos switches idénticos de (n+1) puertos. Estos switches se interconectan por un puerto denominado enlace interno, mientras que los 2n puertos restantes se utilizan para constituir el nodo de n dimensiones. Esta estrategia permite construir un toro con n dimensiones en lugar de solamente (n+1)/2 dimensiones, aumentado las prestaciones de la red. Sin embargo, el diseño de la topología toro nDT presenta varios retos, siendo los más importantes la obtención de una configuración óptima de los nodos del toro nDT y el diseño de algoritmos de encaminamiento libres de bloqueo. Dado que los nodos del toro nDT están compuestos por dos switches, existirán mensajes que forzosamente tendrán que utilizar los dos switches para atravesar el nodo. Esto aumenta la latencia de estos mensajes, lo cual repercute en una degradación de las prestaciones. Por esta razón, es de vital importancia determinar cuál de las posibles configuraciones del nodo minimiza el tráfico que hace uso del enlace interno. Además, el uso del enlace interno puede provocar bloqueos en la red, por lo que determinar cómo aparecen estos bloqueos y cómo evitarlos es otro aspecto fundamental en el diseño del toro nDT. La definición del toro nDT, además de los aspectos de diseño comentados previamente, son discutidos en esta tesis. También se presenta una posible implementación del toro nDT utilizando hardware comercial. Por último, y no menos importante, se han evaluado las prestaciones de diversos toros nDT y se han comparado mediante simulación con las prestaciones de toros de (n+1)/2 dimensiones, con el objetivo de demostrar que la topología nDT obtiene mejores prestaciones utilizando el mismo hardware. Contenido de la obra En esta tesis se discuten principalmente: " Formalización del toro nDT. " Metodología para la obtención de la configuración óptima del toro nDT. " Diseño de algoritmos deterministas y adaptativos libres de bloqueo para el toro nDT. " Posible implementación del toro nDT usando hardware comercial. " Evaluación de rendimiento del toro nDT. Conclusiones La principal aportación de esta tesis es la definición y diseño de la topología toro nDT. Cada nodo del toro nDT comprende dos conmutadores idénticos de (n+1) puertos interconectados entre sí por un puerto, llamado enlace interno. Por lo tanto, cada nodo tiene un total de 2n puertos, permitiendo construir un toro de n dimensiones en lugar de solamente (n + 1) / 2 dimensiones. Aumentando el número de las dimensiones del toro, las distancias entre los nodos se reducen, aumentando el rendimiento de la red. Sin embargo, el uso del enlace interno aumenta la latencia de los mensajes, y por lo tanto, se debe reducir el uso del enlace interno para maximizar el rendimiento de la red. Por ello, se ha propuesto una metodología para obtener la configuración óptima del nodo del toro nDT. A partir de un encaminamiento determinista y un modelo de tráfico, esta metodología nos permite determinar la configuración óptima; es decir, determinar qué configuración minimiza el número de caminos que pasan a través del enlace interno. Para determinar la configuración óptima, se ha considerado el algoritmo DOR, ampliamente utilizado en supercomputadores debido a su simplicidad; y el patrón de tráfico uniforme. A pesar de no ser el patrón de tráfico más realista, dado que los superordenadores suelen ejecutar aplicaciones que generan cargas de tráfico heterogéneas, el patrón de tráfico uniforme comprende todo los pares de nodos de origen/destino posibles, obteniendo una configuración óptima que logra un buen rendimiento en los diferentes escenarios de carga. En cualquier caso, si un superordenador está diseñado para ejecutar una aplicación con una carga de tráfico muy específico, utilizando nuestra metodología se puede obtener una configuración óptima del nodo nDT para este superordenador. En relación con el algoritmo de encaminamiento, se ha estudiado cómo aparecen los bloqueos en el toro nDT. En base a este estudio, se ha diseñado un algoritmo determinista libre de bloqueo basado en el algoritmo DOR, denominado DORT. El algoritmo DORT requiere dos canales virtuales adicionales en el enlace interno para garantizar la libertad de bloqueo. Además, se ha determinado que la configuración óptima es escalable ya que, independientemente del número de dimensiones y el número de nodos, se requiere el mismo número de canales virtuales adicionales en el enlace interno, lo cual no ocurre utilizando otras configuraciones. También se ha discutido el diseño de algoritmos de encaminamiento adaptativos para el toro nDT. En algunos casos, el enlace interno introduce saltos extra en la ruta de los paquetes, aumentando la latencia de los paquetes y reduciendo el rendimiento de la red. Estas cuestiones han sido estudiadas y, como resultado, hemos obtenido una función de encaminamiento adaptativo y una función de selección que minimizan el efecto adverso causado por el uso del enlace interno, incrementando el rendimiento de la red. Por otra parte, también se ha estudiado cómo implementar un toro nDT utilizando hardware comercial. Se ha estudiado la arquitectura de la tarjeta de interconexión de altas prestaciones EXTOLL con el fin de construir un toro 5DT. Dado que la implementación del algoritmo DORT no es posible usando las tarjetas EXTOLL, se ha diseñado un nuevo algoritmo de encaminamiento libre de bloqueo, demostrando que es posible construir un toro nDT utilizando hardware comercial. Todas las conclusiones obtenidas en los estudios analíticos también han sido corroboradas mediante simulación. En todos los casos, se han llegado a conclusiones similares. Para redes pequeñas, el toro nDT apenas aumenta el rendimiento de la red (o incluso lo disminuye), ya que las distancias son prácticamente las mismas en el toro nDT y en el toro nD. Sin embargo, en redes más grandes, las distancias entre nodos, y por lo tanto las latencias, se reducen significativamente. De hecho, cuando aumenta el tamaño de la red, la reducción de las latencias suele aumentar también. Por ejemplo, la latencia media obtenida por el toro 3DT de 64 elementos de proceso (EPs) es un 12% menor que la latencia media del toro 2D del mismo tamaño; sin embargo, los toro 3DT de 128 EPs y 256 EPs reducen la latencia de red un 25% y un 30%, respectivamente. Resultados similares se obtienen comparando los toros 3D y 5DT con 512, 1024 y 2048 EPs. Además, algunos efectos adversos que aparecen en los toros nD son evitados gracias a la reducción de las distancias en la red. El uso de canales virtuales es suficiente para evitar bloqueos en la red, pero genera la infrautilización de varios buffers en la red. A su vez, estos buffers infrautilizados generan una carga de tráfico no balanceada. En toros de pequeño tamaño el efecto de esta carga no balanceada es insignificante, pero en redes de gran tamaño causa una disminución significativa del tráfico aceptado cuando la red satura. Al tener un mayor número de dimensiones, el toro nDT tiene menos nodos por dimensión que el toro equivalente con (n+1)/2 dimensiones. Por esta razón, el toro nDT puede tener un mayor número de nodos sin sufrir esta degradación de rendimiento. Por ejemplo, el tráfico aceptado por el toro 3D de 1024 EPs es el 30% de la tasa máxima de inyección, pero para las tasas de inyección más altas, la productividad se degrada hasta aceptar sólo el 17% de la tasa máxima de inyección. Sin embargo, el toro 5DT de 1024 EPs no sufre esta degradación de rendimiento después de que la red sature. En resumen, se ha investigado la viabilidad de la topología toro nDT: se ha determinado una configuración óptima del nodo nDT; se han diseñado algoritmos de encaminamiento deterministas y adaptativos para esta topología; se ha investigado una posible implementación del toro nDT utilizando hardware comercial y se ha comprobado que el toro nDT incrementa el rendimiento de la red sin aumentar significativamente la complejidad del hardware.