Balanceo Distribuido del Encaminamiento en Redes de Interconexión de Computadores Paralelos

Abstract

En esta investigación, partimos de la observación del funcionamiento de las redes de interconexión en aplicaciones paralelas en los campos de la ciencia y la tecnologia. Esta observación nos dice que la saturación se produce a tasas bajas de carga de la red(menos del 50% de capacidad de carga) y aparece de manera subita en forma de recta vertical con un cambio muy repentino("host-sptos") debido a la no-coincidencia de la distribución de la carga de comunicaciones presenta en la red de interconexion con la topologia de la red. Con objeto de conocer las causas de dicho comportamiento, hemos realizado un estudio del modelado de las redes de interconexion presentando dos modelos diferentes. El primero es un modelo analitico del comportamiento dinamico de las redes de interconexión y el segundo es un modelo funcional que simula el comportamiento de los encaminadores de las redes de interconexion. A partir de la definición de los objetivos y del analisis del comportamiento de las redes de interconexion realizado anteriormente hemos introducido cual deberia ser el tipo de solucion necesaria y hemos definido el concepto de balanceo del trafico para conseguir un uso uniforme del ancho de banda de la red y eliminar los "hot-spots". Esta solucion consiste, según nuestra propuesta, en el balanceo de la carga de comunicaciones en la red de interconexión, por lo que hemos presentado el mecanismo introducido en este trabajo para conseguir los objetivos propuestos consistente en el Balanceo Distribuido del Encamienamiento o DRB por sus siglas en ingles("Distributed Routing Balancing"). La tecnica del balanceo se basa en la distribución del trafica usando nuevos caminos alternativos. Es un metodo dinamico que usa informacion del comportamiento de la red obtenida a un nivel local. Este mecanismo se basa en la expansión de los caminos controlada por la carga de comunicaciones. Con este metodo se pretende conseguir una uniformizacion de la latencia, lo que es a su vez un metodo de eliminar los "hot-spots" y evitar la contención de mensajes. El metodo de DRB pretende desacoplar el patron de trafico de la aplicación de la topologia fisica de la red de interconexión. Se ha realizado el estudio y el analisis de las propuestas introducidas mediante la comparacion via simulacion con las tecnicas estatica (tomada como base a mejorar)y completamente adaptativo(tomada como la tecnica que ofrece mejores prestaciones en la literatura), donde se ha mostrado la idoneidad de la propuesta frente a un numeroso grupo de casos. Se ha realizado una experimentacion en la que se ha evaluado para un conjunto de redes de interconexión (toros e hipercubos) de diversos tamaños (16 y 64 nodos) y para un conjunto de patrones estandar de comunicación("Butterfly", "Bit-Reversal","Perfect Shuffle" y "Matrix Transpose"), la respuesta en latencia, desviacion estandar de la latencia y "throughput". Se ha encontrado que, para la mayoria de casos, DRB ofrece mejores prestaciones que el metodo adaptivo, considerado el metodo de la literatura que es capaz de dar los mejores resultados y en general, DRB mejora al caso adaptivo, en un 50% , tanto en resultados de latencia como de "throughput". Todos estos resultados demuestran la validez del metodo DRB como metodo de encaminamiento de mensajes en redes de interconexion de computadores paralelos de proposito general, el cual es capaz de reducir la latencia y aumentar el rango de carga en el cual la red es operativa. Con todo ello, se espera haber contribuido a definir las caracteristicas de los computadores paralelos o de altas prestaciones del futuro.