Técnicas de control de flujo y encaminamiento para mejorar las prestaciones en redes en chip

Abstract

[EN] Interconnection networks are a critical component in most modern systems nowadays. Both off-chip networks, in HPC systems, data centers, and cloud servers, and on-chip networks, in chip multiprocessors (CMPs) and multiprocessors system-on-chip (MPSoCs), play an increasing role as their performance is vital for the performance of the whole system.

One of the key components of any interconnect is the routing algorithm, which steers packets through the network. Adaptive routing algorithms have demonstrated their superior performance by maximizing network resources utilization. However, as systems increase in size (both in off-chip and on-chip), new problems emerge. One of them is congestion where traffic jams inside the network lead to low throughput and high packet latencies, significantly impacting overall system performance. Adaptive routing algorithms produces another problem: the unbalanced resource utilization. Indeed, the adaptive routing algorithm tends to use adaptive channels and only with high traffic the escape channels are used.

In this tesis we propose some mechanisms to eradicate these problems. First, we propose type-based flow control (TBFC) and safe/unsafe routing (SUR), as it achieves a proper balanced utilization of input port buffers. Finally, we propose the End-Point Congestion Filter (EPC) preventing the congestion from spreading through the network.

[ES] Las redes de interconexión son un componente crítico en la mayoría de los sistemas modernos tanto dentro como fuera del chip. En los sistemas de HPC, centros de datos y servidores de la nube, multiprocesadores de chips (CMPS) y multiprocesadores de sistema en chip (MPSoCs), las redes de interconexión desempeñan un papel cada vez más importante, siendo su rendimiento vital para el comportamient de todo el sistema.

El algoritmo de encaminamiento es uno de los componentes clave de cualquier red de interconexión. Estos algoritmos son los encargados de dirigir los paquetes a través de la red. Los algoritmos de encaminamiento adaptativos obtienen un rendimiento superior debido a que maximizan la utilización de recursos de red. Sin embargo, cuando los sistemas aumentan de tamaño (tanto dentro como fuera del chip), surgen nuevos problemas. Uno de ellos es la congestión en la red. Ésta produce altas latencias de los mensajes y una caída en el rendimiento de la red, lo que produce un impacto significativo en el rendimiento general del sistema. Los algoritmos encaminamiento adaptativos producen otro problema: la utilización desequilibrada de los recursos. Debido a que estos algoritmos de encaminamiento tienden a utilizar los canales adaptativos y solo cuando existe una gran cantidad de tráfico utilizan los canales de escape.

En esta tesis se proponen varios mecanismos para evitar estos problemas. En concreto, se propone type-based flow control (TBFC) y safe/unsafe routing (SUR) para el problema del uso desequilibrado de las colas y el Filtro de congestión End-Point (EPC) para evitar la ramificación de la congestión. (español)