Design and implementation of efficient topology agnostic routing algorithms for interconnection networks

Abstract

Esta tesis se enfoca en el diseño e implementación de algoritmos de encaminamiento para redes de interconexión (HPCs, Clusters, SoC y NoC). Más especificamente, cubriendo el diseño de algoritmos de encaminamiento agnósticos a la topología. Con este fin, se realiza un repaso a los algoritmos de encaminamiento agnósticos a la topología propuestos en la literatura, así mismo, se introduce una taxonomía para caracterizarlos en base a características similares de diseño que tienen en común. Como principal contribución, se propone una novedosa metodología para calcular algoritmos de encaminamiento agnósticos a la topología para redes de interconexión denominado Segment-based Routing algorithm (SR). Así mismo, se propone también, una plataforma de encaminamiento denominada Region-based Routing (RbR) que permite a sistemas y redes dentro del chip soportar topologías irregulares reemplazando las costosas tablas de encaminamiento (en términos de consumo de energía y área) por rápidos y eficientes bloques de lógica.