Un encaminador de paquetes para redes de interconexión de un sistema multiprocesador que comprende 2 B bloques constructivos básicos (101,

102, 103, 104) dispuestos en anillo en torno a un nodo local (100), donde B es un número natural mayor que 1. El encaminador está configurado para que cada paquete que entra al encaminador circule a través de un lazo que atraviesa dichos bloques constructivos básicos (101, 102, 103, 104) hasta que encuentre un puerto de salida que lo acerque a su destino. Cada bloque constructivo básico (101) comprende una etapa de recepción de paquetes (RECEPTION), una etapa de expulsión de paquetes (EJECTION) y un búfer FIFO (DFIFO), donde dicho búfer FIFO (DFIFO) tiene dos puertos de entrada (R3, Li) y dos puertos de salida (E3, Lo), donde uno de los puertos de entrada (R3) está conectado a una salida de dicha etapa de recepción de paquetes (RECEPTION), y el otro puerto de entrada (Li) está conectado a un puerto de salida de un búfer FIFO de un bloque constructivo básico anterior (104), y donde uno de los puertos de salida (E3) está conectado a una entrada de dicha etapa de expulsión de paquetes (EJECTION), y el otro puerto de salida (Lo) está conectado a un puerto de entrada de un búfer FIFO de un bloque constructivo básico posterior (102), estando dicho búfer FIFO (DFIFO) configurado para que o bien un paquete abandone el encaminador a través del puerto (E3) conectado a dicha etapa de expulsión de paquetes (EJECTION), o bien un paquete abandone el búfer FIFO (DFIFO) a través del puerto (Lo) conectado a dicho bloque constructivo básico posterior (102) para que siga circulando a través de dicho lazo

Encaminador de paquetes para sistemas multiprocesador.

Campo de la invención

La presente invención pertenece al campo de las redes de interconexión que pueden usarse en sistemas multiprocesador, tanto en un solo chip (multiprocesadores en chip, del inglés on-Chip multiprocessors, CMP) como en sistemas en varios chips. Más concretamente, la invención se refiere a un encaminador de paquetes para los sistemas multiprocesador.

Antecedentes de la invención

Los sistemas multiprocesador transfieren datos entre procesadores, memorias o cualquier otro componente del sistema. Los procesadores suelen ir interconectados para compartir y transferir datos. Los encaminadores (del inglés, routers) se usan, entre otras cosas, para interconectar sistemas multiprocesador.

Como sustrato cohesivo, una red de interconexión juega un papel principal en los multiprocesadores en chip (CMP). Aunque la escalabilidad de los CMP impone la utilización de redes punto-a-punto, actualmente no hay un consenso en cuanto a cuáles son las mejores elecciones de diseño. Está claro que las restricciones tecnológicas en este contexto son bastante diferentes de las típicas del dominio off-chip: mientras que deben restringir el coste de implementación y el consumo de energía, la disponibilidad de ancho de banda disponible es abundante. La combinación de esos factores ha establecido como principio del diseño más común la minimización de la complejidad de la arqui- tectura.

Hay muchas propuestas con soluciones simples para la arquitectura de un encaminador y una topología de red que garanticen un coste mínimo par la red, minimizando latencia en condiciones de baja carga y restringiendo los requisitos de potencia. Un ejemplo es el encaminador sin buffer descrito por M. Hayenga y otros, en "SCARAB: A Single Cycle Adaptive Routing and Bufferless Network", MICRO 2009. Sin embargo, la mayoría de estas soluciones tienden a subestimar o ignorar el comportamiento del sistema bajo condiciones de carga alta y las características requeridas por otros niveles de la jerarquía de memoria del sistema.

Centrar el diseño de la red en aspectos de rendimiento en condiciones de carga baja o de energía por ciclo y al mismo tiempo subestimar la contención puede ser un enfoque peligroso, como apuntan P. Abad y otros en "Impact of Interconnection Network Resources on CMP Performance", Workshop on Interconnection Network Architectures: On-Chip, Multi-Chip (EMA-OCMC), February 2010. Cuando las características inherentes de la carga de trabajo y las propiedades del sistema aumentan sustancialmente la carga aplicada en la red, los efectos de la contención están lejos de ser despreciables. Bajo esas condiciones, la latencia de acceso percibida por los procesadores se ve agravada porque la contribución de la red a ese retraso aumenta en función de la carga aplicada. Cerca de la saturación de red, el incremento de latencia es de órdenes de magnitud superior a la latencia base, alcanzándose un punto tal que podría inducir el colapso del rendimiento del sistema completo. Cambios en el comportamiento de la carga de trabajo pueden llevar a un rendimiento del sistema errático: en aplicaciones con demandas de red reducidas el sistema podría funcionar bien, pero con aplicaciones que estresen la red más allá de sus capacidades, funcionará de forma pobre. Para evitar un escenario así, es necesario garantizar que el punto de saturación de la red esté lejos del punto de operación del sistema. Por tanto, se necesita mejorar la productividad de la red usando técnicas conocidas, como encaminamiento adaptativo, utilización de almacenamiento libre de bloqueo de cabeza de línea (del inglés, buffering free of head-of-line blocking (HoLB)), etc. Sin embargo, es comúnmente aceptado que la mayoría de estas características aumentan la complejidad de la red y pueden sobrepasar las restricciones de coste de implementación o hacen peligrar la latencia bajo condiciones de baja carga, lo cual podría penalizar el rendimiento en algunas aplicaciones. Además, las características requeridas por el protocolo de coherencia para que funcione correctamente, tales como evitar el interbloqueo (deadlock) entre clases de mensajes, no son una opción. Por eso, propuestas para la red de interconexión que minimicen o ignoren su relevancia podrían ser poco prácticas.

La patente española 2324577 B2 describe un encaminador de mensajes para redes de interconexión de sistemas multiprocesador que soporta tráfico ordenado (en inglés, in-order trafile) y elude interbloqueo sin requerir el empleo de canales virtuales. Además, soporta multidestino en árbol adaptativo (en inglés, adaptive tree multicast). El encaminador se propuso con el fin de minimizar la contención. En concreto, esta patente describe un encaminador construido a partir de unos búferes de doble puerto (del inglés Dual-port FIFO Buffers, DBF). Sin embargo, este encaminador presenta algunos inconvenientes, tales como que el área de implementación es relativamente alta.

Por otra parte, N.E. Jerger y otros, en "Virtual Circuit Tree Multicasting: A Case for On-Chip Hardware Multicast Support", 35th International Symposium on Computer Architecture (ISCA), June 2008, describen un encaminador VCTM (del inglés, Virtual Circuit Tree Multicasting). Sin embargo, este encaminador requiere una cantidad elevada de canales virtuales para evitar el interbloqueo entre clases de mensajes y solo soporta paquetes multidestino de un solo flit.

Resumen de la invención

La presente invención trata de resolver los inconvenientes mencionados anteriormente mediante un encaminador que equilibra latencia y throughput (rendimiento), tanto en redes de interconexión CMP, como en otras redes, como las redes off-chip.

Concretamente, en un primer aspecto de la presente invención, se proporciona un encaminador de paquetes para redes de interconexión de un sistema multiprocesador, donde el encaminador de paquetes comprende 2•B bloques constructivos básicos dispuestos en anillo en torno a un nodo local, donde B es un número natural mayor que 1 y que corresponde al número de dimensiones de la topología a emplear. El encaminador está configurado para que cada paquete que entra al encaminador circule a través de un lazo que atraviesa los bloques constructivos básicos hasta que encuentre un puerto de salida que lo acerque a su destino. Cada bloque constructivo básico comprende una etapa de recepción de paquetes, una etapa de expulsión de paquetes y un búfer FIFO, donde el búfer FIFO tiene dos puertos de entrada y dos puertos de salida, donde uno de los puertos de entrada está conectado a una salida de la etapa de recepción de paquetes, y el otro puerto de entrada está conectado a un puerto de salida de un búfer FIFO de un bloque constructivo básico anterior, y donde uno de los puertos de salida está conectado a una entrada de la etapa de expulsión de paquetes, y el otro puerto de salida está conectado a un puerto de entrada de un búfer FIFO de un bloque constructivo básico posterior, estando dicho búfer FIFO configurado para que o bien un paquete abandone el encaminador a través del puerto conectado a la etapa de expulsión de paquetes, o bien un paquete abandone el búfer FIFO a través del puerto conectado al bloque constructivo básico posterior para que siga circulando a través del lazo.

Preferentemente, la etapa de recepción de cada uno de los 2•B bloques constructivos básicos, comprende una entrada y tres salidas, donde la entrada y salidas se conectan a través de un demultiplexador de paquetes; y la etapa de expulsión de paquetes comprende tres entradas y una salida, donde las entradas y salida se conectan a través de un multiplexador de paquetes.

En una posible realización, de esas tres salidas de la etapa de recepción de cada uno de los 2•B bloques constructivos básicos, se elige, para un paquete entrante, una primera salida cuando el nodo local conectado al encaminador es el destino del paquete.

Alternativamente, de esas tres salidas de la etapa de recepción de cada uno de los 2•B bloques constructivos básicos, se elige, para un paquete entrante, una segunda salida conectada a la etapa de expulsión de paquetes, si se dan simultáneamente las tres siguientes condiciones:

- el destino del paquete se puede alcanzar siguiendo la dimensión y dirección del movimiento del actual paquete, es decir, el puerto de salida del bloque constructivo básico acerca el paquete a destino;

- no hay ningún paquete en la etapa de expulsión esperando a usar el puerto de salida; y

1. Un encaminador de paquetes para redes de interconexión de un sistema multiprocesador, donde dicho encaminador de paquetes comprende 2•B bloques constructivos básicos (101, 102, 103, 104) dispuestos en anillo en torno a un nodo local (100), donde B es un número natural mayor que 1 y que corresponde al número de dimensiones de la topología a emplear, estando el encaminador configurado para que cada paquete que entra al encaminador circule a través de un lazo que atraviesa dichos bloques constructivos básicos (101, 102, 103, 104) hasta que encuentre un puerto de salida que lo acerque a su destino,

donde cada bloque constructivo básico (101) comprende una etapa de recepción de paquetes (RECEPTION), una etapa de expulsión de paquetes (EJECTION) y un búfer FIFO (DFIFO), donde dicho búfer FIFO (DFIFO) tiene dos puertos de entrada (R₃, L_i) y dos puertos de salida (E₃, L_o), donde uno de los puertos de entrada (R₃) está conectado a una salida de dicha etapa de recepción de paquetes (RECEPTION), y el otro puerto de entrada (L_i) está conectado a un puerto de salida de un búfer FIFO de un bloque constructivo básico anterior (104), y donde uno de los puertos de salida (E₃) está conectado a una entrada de dicha etapa de expulsión de paquetes (EJECTION), y el otro puerto de salida (L_o) está conectado a un puerto de entrada de un búfer FIFO de un bloque constructivo básico posterior (102), estando dicho búfer FIFO (DFIFO) configurado para que o bien un paquete abandone el encaminador a través del puerto (E₃) conectado a dicha etapa de expulsión de paquetes (EJECTION), o bien un paquete abandone el búfer FIFO (DFIFO) a través del puerto (L_o) conectado a dicho bloque constructivo básico posterior (102) para que siga circulando a través de dicho lazo,

estando el encaminador caracterizado por que dicha etapa de recepción (RECEPTION) de cada uno de dichos 2•B bloques constructivos básicos (101, 102, 103, 104), comprende una entrada (X-) y tres salidas (R₁ R₂ R₃), donde dicha entrada y salidas se conectan a través de un demultiplexador de paquetes; y dicha etapa de expulsión de paquetes (EJECTION) comprende tres entradas (E₁ E₂ E₃) y una salida (X+), donde dichas entradas y salida se conectan a través de un multiplexador de paquetes.

2. El encaminador de la reivindicación 1, donde, de dichas tres salidas (R₁ R₂ R₃) de la etapa de recepción (RECEPTION) de cada uno de dichos 2•B bloques constructivos básicos (101, 102, 103, 104), se elige, para un paquete entrante, una primera salida (R₁, Cons_x+) cuando el nodo local (100) conectado al encaminador es el destino del paquete.

3. El encaminador de cualquiera de las reivindicaciones anteriores, donde, de dichas tres salidas (R₁ R₂ R₃) de la etapa de recepción (RECEPTION) de cada uno de dichos 2•B bloques constructivos básicos (101, 102, 103, 104), se elige, para un paquete entrante, una segunda salida (R₂) conectada a dicha etapa de expulsión de paquetes (EJECTION), si se dan simultáneamente las tres siguientes condiciones: