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 arquitectura.

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 outing 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-Cbip (INA-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 traffic) 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

-un encaminador vecino conectado a través del puerto de salida del bloque constructivo básico dispone de espacio para al menos un 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 tercera salida conectada al búfer, obligando a dicho paquete a moverse continuamente dentro del lazo formado por el conjunto de bloques constructivos básicos, cuando ninguna de las dos alternativas previas son seleccionables y se cumple al menos una de las siguiente condiciones:

-el paquete pertenece a un tráfico no ordenado, el búfer dispone de espacio para recibir el paquete, y el espacio de almacenamiento de los búferes de los diversos bloques constructivos básicos disponen de espacio para recibir todos los posibles paquetes en tránsito pertenecientes a tráficos con mayor prioridad que el actual; o

-el paquete pertenece a un tráfico ordenado, el búfer dispone de espacio para recibir el paquete y en los búferes de los diversos bloques constructivos básicos no existe otro paquete perteneciente a un tráfico ordenado.

Preferentemente, la etapa de recepción de cada uno de los 2-B bloques constructivos básicos está configurada para almacenar temporalmente al menos un paquete.

Preferentemente, de las tres entradas de la etapa de expulsión de paquetes de cada uno de los 2-B bloques constructivos básicos: una primera entrada comprende un espacio de almacenamiento configurado para almacenar al menos dos paquetes procedentes del búfer FIFO al que se encuentra conectada; una segunda entrada está configurada para conectar la etapa de expulsión a un puerto inyector del nodo local; y una tercera entrada está configurada para conectar la etapa de expulsión con la etapa de recepción.

En otro aspecto de la invención, se proporciona un sistema que comprende una pluralidad de encaminadores de paquetes como el descrito anteriormente, donde esa pluralidad de encaminadores forma una determinada topología, y donde cada encaminador está configurado para girar en un determinado sentido, siendo el sentido de giro de cada encaminador opuesto al sentido de giro de los encaminadores que se encuentren adyacentes al mismo.

Preferentemente, el sistema comprende un camino cíclico que pasa por cada uno de dicha pluralidad de encaminadores una y solo una vez.

En una realización particular, el sistema está configurado para que, para cada bloque constructivo básico de cada encaminador, un paquete almacenado en dicho búfer FIFO abandone el correspondiente encaminador a través del puerto conectado a la etapa de expulsión de paquetes correspondiente, si se cumple al menos una de las siguientes condiciones:

-Si se trata de un paquete de un sólo destino y el puerto de salida del bloque constructivo actual acerca el paquete a destino;

-Si se trata de un paquete multidestino, el puerto de salida del bloque constructivo actual acerca el paquete a al menos uno de sus destinos y el espacio de almacenamiento de la etapa de expulsión asociado al puerto de entrada está vacío;

-Si se trata de un paquete de uno o más destinos, ha dado un número de vueltas en lazo del encaminador superior a un determinado umbral y el puerto de salida del bloque constructivo actual conecta a un enlace de comunicación perteneciente a dicho camino cíclico.

Por último, la invención proporciona un programa informático que comprende medios de código de programa informático adaptados para implementar el encaminador de paquetes descrito anteriormente o el sistema descrito anteriormente, cuando dicho programa se ejecuta en un ordenador, un procesador de señal digital, una disposición de puertas de campo programable, un circuito integrado de aplicación específica, un microprocesador, un microcontrolador, y cualquier otra forma de hardware programable.

Las ventajas de la invención se harán evidentes en la descripción siguiente.

BREVE DESCRIPCIÓN DE LAS FIGURAS

Con objeto de ayudar a una mejor comprensión de las características de la invención, de acuerdo con un ejemplo preferente de realización práctica del mismo, y para complementar esta descripción, se acompaña como parte integrante de la misma, un juego de dibujos, cuyo carácter es ilustrativo y no limitativo. En estos dibujos:

La figura 1A muestra un esquema de encaminador de acuerdo con una implementación de la invención.

La figura IB muestra en detalle una posible implementación de los bloques constructivos básicos del encaminador de la figura 1A.

La figura 2 muestra una posible forma de conectar los ciclos de los distintos encaminadores, de acuerdo con la invención.

La figura 3 muestra un ejemplo esquemático de cómo se evita el interbloqueo extremo a extremos en el encaminador de la invención.

DESCRIPCIÓN DETALLADA DE LA INVENCIÓN

En este texto, el término "comprende" y sus variantes no deben entenderse en un sentido excluyente, es decir, estos términos no pretenden excluir otras características técnicas, aditivos, componentes o pasos.

Además, los términos "aproximadamente", "sustancialmente", "alrededor de", "unos", etc. deben entenderse como indicando valores próximos a los que dichos términos acompañen, ya que por errores de cálculo o de medida, resulte imposible conseguir con total exactitud.

Las siguientes realizaciones preferidas se proporcionan a modo de ilustración, y no se pretende que sean limitativos de la presente invención. Además, la presente invención cubre todas las posibles combinaciones de realizaciones particulares y preferidas aquí indicadas. Para los expertos en la materia, otros objetos, ventajas y características de la invención se desprenderán en parte de la descripción y en parte de la práctica de la invención.

A continuación se describe el encaminador de la invención. La figura 1 A muestra un esquema del encaminador de acuerdo con una realización de la invención. El encaminador se implementa mediante una arquitectura totalmente modular, que no necesita arbitraje ni elemento de conmutación (del inglés, switching f abrió) centralizados. Cada par entrada-salida en la misma dirección y dimensión tiene una estructura similar.

El encaminador puede tener una topología N-dimensional, estando formado por 2-B bloques constructivos básicos. Esta posible implementación es especialmente apta para topologías planas, tales como toros bidimensionales. La figura 1A muestra una implementación para el caso particular de una topología bi-dimensional (B=2), en la que el encaminador está formado por 4 bloques constructivos básicos 101 102 103 104 en torno a un nodo local 100 formando un anillo. La figura IB muestra en detalle uno de los bloques constructivos básicos 101 para este caso particular de topología bi-dimensional, que comprende un búfer FIFO (del inglés, first-in-first-out) de doble puerto (DFIFO) y etapas de recepción RECEPTION y expulsión EJECTION. El bloque constructivo básico se describe en detalle a continuación.

El encaminador emplea una estructura de almacenamiento organizada en forma de anillo en torno a un nodo local 100. A través del anillo se establece un flujo de paquetes de información. Los paquetes de información que entran en el encaminador son obligados a circular por el anillo hasta que encuentren un puerto de salida que les acerque a su destino o el paquete esté habilitado para emplear el camino cíclico establecido en la red. Ello evita el bloqueo por parada de la cabeza, puesto que cuando un puerto de salida se encuentra disponible en un lapso de tiempo breve, es utilizado por uno de los paquetes en circulación.

Como puede observarse en la figura IB, un paquete tiene tres posibles accesos de entrada Injx ₊ , X- y L, al bloque constructivo básico 101 y tres posibles formas de salir Consx ₊ , X+ y L ₀ del mismo.

El búfer FIFO de doble puerto (DFIFO) es un búfer multipuerto con dos puertos de entrada R ₃ y L¡ y dos de salida E ₃ y L ₀ . El búfer DFIFO permite guardar en su interior una pluralidad de paquetes. En la entrada del búfer DFIFO no puede haber paquetes esperando, sino que de tener que esperar, lo hacen dentro del propio búfer. Un ejemplo no limitativo de búfer DFIFO es el descrito en la patente ES2324577B2. Mediante la conexión de un par de entrada-salida (L¡ y L ₀ ) del DFIFO en cada bloque básico 101 102 103 104, se crea un lazo (loop) de búferes como ilustra la referencia "loop" en la figura IB. Para cada paquete almacenado en el búfer DFIFO de cada bloque básico 101 102 103 104, se debe decidir si el paquete debe ser expulsado, en cuyo caso toma la salida E ₃ que lo conduce a la etapa de expulsión EJECTION, o si debe avanzar a través del lazo interno al búfer DFIFO del siguiente bloque constructivo, en cuyo caso toma la salida L ₀ hacia el lazo.

Cada bloque básico 101 102 103 104 tiene también una etapa de recepción RECEPTION. Para el caso particular del bloque 101, esta etapa tiene una entrada X-. En esta etapa de recepción, mediante un multiplexor se elige para cada paquete entre las tres salidas alternativas diferentes R ₂ R ₃ :

-La primera R es la denominada de consumo Consx ₊ , que se elige cuando el nodo local 100 es el destino del paquete.

-La segunda R ₂ es la denominada circunvalación o bypass, que coincide con una entrada E ₂ de la etapa de expulsión EJECTION. Ésta R ₂ se elige 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.

-No hay paquetes en la etapa de expulsión esperando a usar el puerto de salida X+ (aunque puede haber paquetes en el DFIFO moviéndose dentro del lazo). -El encaminador vecino conectado en el puerto de salida tiene hueco para al menos un paquete. Dado que el control de flujo aplicado en el encaminador es el conocido como Cut-through virtual (Virtual Cut-through), como describen por ejemplo P. Kermani y otros en "Virtual Cut-Through: A New Computer Communication Switching Tecnique", Computer Networks, Vol. 3, pp. 267- 286, Sept. 1979", la etapa de recepción RECEPTION debe ser capaz de almacenar al menos un paquete.

Si alguna de estas tres condiciones no se satisface, la etapa de recepción RECEPTION elige la tercera salida R ₃ , enviando el paquete al buffer DFIFO y forzándolo a moverse continuamente dentro del lazo interno (loop) hasta que alcance un puerto de salida disponible y que acerque el paquete a destino.

Cada bloque básico 101 102 103 104 tiene también una etapa de expulsión EJECTION. Esta etapa también realiza la multiplexación del enlace a nivel de paquete, regulando el acceso al puerto de salida X+ desde tres caminos o entradas diferentes E ₂ E ₃ . Utilizando prioridades giratorias, esta etapa de expulsión EJECTION elige qué paquete puede progresar hacia un enlace o puerto de salida X+. Como se observa en la figura IB, la primera entrada Ei es una conexión Inj _x+ desde el nodo central 100. La segunda E ₂ es una conexión directa con la línea de circunvalación o bypass (salida R ₂ de la etapa de recepción RECEPTION) y la tercera E ₃ es una salida de la cola DFIFO. Por tanto, esta etapa de expulsión EJECTION tiene que proporcionar algún tipo de buffer o almacenamiento interno para gestionar posibles conexiones. Sin embargo, para maximizar la utilización del enlace de salida y aplicar otras mejoras, preferentemente solo requiere capacidad de almacenamiento o buffering al camino de entrada E ₃ procedente del búfer DFIFO. Este almacenamiento o buffering se ilustra en la figura IB, donde se muestran dos elementos de almacenamiento de forma meramente ilustrativa, pudiendo elegirse una capacidad de almacenamiento diferente. Los caminos de bypass E ₂ y de inyección de entrada Injx ₊ pueden gestionarse simplemente con un latch. Alternativamente, una de estas dos entradas o ambas pueden tener algún elemento de almacenamiento o buffering.

Para acceder al host o nodo local 100 (que puede ser, por ejemplo, un procesador, un banco de cache, memoria, etc.) es necesario interconectar los caminos de inyección Injx+ y de consumo Consx+ a cada bloque básico 101 102 103 104 respectivo. En una realización particular, esto se realiza con un demultiplexador y multiplexador, respectivamente. Para el multiplexador, preferentemente se asume que si la cola de consumo está temporalmente llena, los paquetes tienen que esperar en la etapa de recepción del puerto de entrada. No merece la pena proporcionar alguna forma de búfer multipuerto en esa cola. De forma similar, preferentemente la cola de inyección del demultiplexador hacia las correspondientes etapas de expulsión de los bloques constructivos no requiere búferes adicionales en la etapa de expulsión. En la figura 1 A, tanto el multiplexador como el demultiplexador del nodo local 100 tienen cuatro entradas y salidas, respectivamente.

La rotación de los paquetes dentro del encaminador puede configurarse en sentido horario, como se ilustra en la figura 1 A, o en sentido antihorario, simplemente rotando adecuadamente los bloques básicos. Ambas posibilidades se muestran en la figura 2, en la que se combinan ambas clases de organización del encaminador como un tablero de ajedrez para un torus bidireccional (parte izquierda de la figura 2). De esta forma, se equilibra la utilización del enlace a través de la utilización implícita de una función de selección en zig-zag. Tanto la figura 2A como la 2B muestran un sistema formado por 16 encaminadores (0...15). En otras topologías puede aplicarse una regla constructiva similar. Sobre la topología previamente definida se selecciona un conjunto de canales de comunicación que conformen un camino cíclico (parte derecha de la Figura 2) que discurra por todos los encaminadores de la red una o más veces. Este camino cíclico, representado en la figura 2B con trazo grueso, representa la ruta de escape que se describe más adelante.

Los paquetes deben moverse en el lazo de los búferes DFIFO hasta que encuentren un puerto de salida disponible y que acerque el paquete a destino o que forme parte del camino cíclico descrito previamente cuando el paquete haya dado un número suficientemente alto de giros en el encaminador, siendo infructuoso el acceso a los canales de comunicación que acercan el paquete a destino. Los paquetes puede ser o bien de un solo destino o bien multidestino. Para los paquetes de un solo destino, el puerto de salida está disponible si el espacio de almacenamiento asociado a la entrada E3 del la etapa de expulsión dispone de espacio para uno o más paquetes. Para los paquetes multidestino que se acercan a parte de los destinos a través de ese puerto de salida, el puerto de salida está disponible si la entrada E3 del la etapa de expulsión dispone de espacio para dos o más paquetes. Cuando este puerto está disponible, el paquete se duplica a través de los dos puertos de salida de la DFIFO en la que se encuentra alojado.

Los paquetes también llevan asociada una clase de tráfico determinada, cuyos detalles quedan fuera del alcance de la presente invención. Un paquete perteneciente a una clase de tráfico ordenada solamente está habilitado para incorporarse al lazo formado por los diferentes DFIFO si no hay ningún otro paquete perteneciente a un tráfico ordenado en su interior.

Cada una de las clases de tráfico del sistema es categorizada y un paquete de una clase particular está habilitado para incorporarse al lazo formado por los diferentes DFIFO si cualquier posible paquete en tránsito de clases superiores tiene espacio suficiente para ser admitido en el lazo con posterioridad.

A continuación se presentan las principales características de la red. En primer lugar, se trata de un encaminador para tráfico de paquetes totalmente adaptativo. Cuando un paquete entra en el lazo o bucle interno, abandona el encaminador por el primer puerto disponible y adecuado para llegar al destino del paquete, maximizando la utilización de puerto y enlace. El encaminador está libre de bloqueo de parada de la cabeza (head-of- line blocking (HoLB)), porque cuando un paquete no puede abandonar el encaminador a través de cualquiera de los puertos adecuados para llegar al destino, se ve forzado a seguir circulando a través del bucle y los paquetes que van entrando por detrás pueden progresar a través de otros puertos de salida disponibles.

El conducto del encaminador que perciben los paquetes se adapta al status del encaminador. Bajo condiciones de baja carga, los paquetes pueden pasar a través del encaminador en un único ciclo, empleado en la etapa de recepción. Durante ese ciclo, la lógica de control evalúa las condiciones de circunvalación y usa el camino dedicado de recepción-expulsión si esas condiciones se cumplen. Usando un único latch en la etapa de expulsión, se hace viable cubrir la longitud cableada al siguiente encaminador en un único ciclo.

Para minimizar lo más posible el área del encaminador, a la vez que se garantice la corrección de red y del protocolo de coherencia, el almacenamiento mínimo por bloque constructivo es de seis paquetes: uno necesario en la etapa de recepción, dos necesarios en la etapa de expulsión y tres necesarios en el búfer DFIFO. La interfaz del nodo local no requiere almacenamiento del lado del encaminador. Por tanto, el encaminador completo debe tener espacio suficiente para albergar un mínimo de 24 paquetes. Suponiendoo un tamaño de paquete de 80 Bytes y un tamaño de flit de 128 bits, esto representa 2 KB por cada encaminador. Nótese que el encaminador de tipo wormhole más simple, como por ejemplo el usado en el prototipo de Intel de S. R. Vangal et al ("An 80-Tile Sub-100-W TeraFLOPS Processor in 65-nm CMOS," IEEE Journal of Solid-State Circuits, vol. 43, pp. 6-20, Jan. 2008), tenía 2.5KB.

A continuación se describe cómo la corrección de red queda garantizada, a través de una explicación relativa al interbloqueo (deadlock), al livelock y a la inanición (starvatiorí).

Interbloqueo {Deadlock)

El interbloqueo de red es la más significativa de las posibles anomalías de red. El encaminador propuesto usa un enfoque característico para tratarlo, basado en lo siguiente: a) Garantía de Movimiento de Paquete Dentro-del-encaminador (Intra-router Packet Movement Guarantee): Los paquetes que se encuentran en un bucle interno del encaminador deben ser capaces de alcanzar cualquiera de los puertos de salida para progresar. Esta condición se cumple simplemente aplicando un control de flujo del tipo Bubble Flow Control (BFC) al tráfico en tránsito (esto es, un paquete almacenado en una etapa de recepción puede progresar a la etapa DFIFO si hay hueco para al menos dos paquetes. Esta regla garantiza que cada encaminador mantienen espacio para al menos un paquete del bucle interno, lo cual es suficiente para asegurar que todos los paquetes del bucle podrían alcanzar todos los puertos de salida. Para aplicar esta condición, las capacidades de almacenamiento mínimas para el DFIFO son dos paquetes. Esta regla es aplicada localmente en cada bloque constructivo por la etapa de recepción. Este bloque arbitra la adición de nuevos paquetes al bucle y garantiza la existencia de N huecos para paquetes en una red de N encaminadores. b) Garantía de Movimiento de Paquete Entre-Enrutadores (Inter-router Packet Movement Guarantee): Cualquier paquete almacenado en la red tiene que ser capaz de avanzar hacia su nodo destino en un número finito de ciclos. Para conseguir este escenario, se necesita: b.l) Subfunción de encaminamiento de escape (Escape routing sub-function): Tras un número predefinido, a través de un cierto umbral, y suficientemente alto de rotaciones infructuosas en cualquier bucle de encaminador, un paquete se marca como en escape (on-escape) y puede abandonar el encaminador usando un puerto de salida de una subfunción de encaminamiento de escape (escape routing sub-function). Estas sub- funciones son conocidas y quedan fuera del alcance de la presente invención. Esta condición se mantiene para un paquete hasta que alcance su destino. La sub-función de encaminamiento se restringe a usar solo los puertos de salida de cada encaminador que pertenecen a un camino cíclico, similar al esquema de la Figura 2 (derecha) para un 2- cubo cuaternario, a través de todos los nodos de la red. El trazo grueso de la Figura 2 (derecha) representa este camino cíclico o ruta de escape. En una red conectada, siempre es posible encontrar un camino cíclico similar. Siguiendo dicho camino, los paquetes en escape (on-escape) llegarán en algún momento a su destino. b.2) Existencia de hueco de salvaguarda (Lifesaver hole existence): Es necesario garantizar la existencia de al menos N+l huecos para paquetes en la totalidad de la red, para permitir a los paquetes en escape (on-escape) que progresen hacia su destino. La Garantía de Movimiento Dentro-del-encaminador (Intra-router Movement Guarantee) asegura la existencia de N huecos para paquetes en la red. Extendiendo la idea que soporta BFC (Bubble Flow Control), es posible asegurar el hueco extra o hueco de salvaguarda mediante la aplicación de la siguiente regla:

"Para inyectar un nuevo paquete en la red, debe haber hueco para al menos tres paquetes (three packet holes) dos en el Bloque Constructivo Básico (Basic Building Block, BBB local) que incluye el puerto de salida donde se produce la inyección y uno en la etapa de recepción del encaminador vecino donde será almacenado".

La restricción en la inyección se aplica usando solo la información del BBB local, porque la señalización del hueco para un paquete en el encaminador vecino la proporcionan las señales de control de flujo VCT (Virtual Cut-Through). Con respecto a esta regla, después de que un nuevo paquete es inyectado, la existencia de N+l huecos para paquetes en la red queda garantizada. En el peor caso, cuando se inyecta un nuevo paquete en la red y simultáneamente dos paquetes llenan el DFIFO local (procedentes del búfer de la etapa de recepción del BBB local y del DFIFO del BBB precedente en el bucle) y el resto de encaminadores tienen espacio para un paquete, en la red existirán N+1 huecos: espacio para dos paquetes en el encaminador precedente y un paquete en los N-l encaminadores restantes.

Incluso en la situación teórica de la existencia de solo N+1 huecos en toda la red, finalmente todos los paquetes se marcan como en escape (on-escape) y siguen el camino cíclico hacia su destino. Nótese que este movimiento es posible por la existencia del hueco de salvaguarda. Frente a otros trabajos (W.Dally, and B. Towles, "Principies and Practices of Interconnection Networks", Morgan Kaufmann Publishers Inc. 2003), se evita el interbloqueo sin necesitar la utilización de canales virtuales para la sub-función de escape (escape routing sub-function), ya que los paquetes en escape no pueden bloquearse por paquetes regulares debido al diseño "crossbar-less". El efecto sobre el rendimiento de la solución es despreciable porque bajo condiciones de trabajo realistas la proporción de paquetes marcados en escape es prácticamente insignificante.

Livelock

La red está también libre de live-lock porque si un paquete no está marcado como "en escape", siempre usará una ruta mínima hacia su destino. Después de que un paquete se marque en cualquier momento como "en escape", sigue una ruta cíclica que, aunque no sea mínima, le hace alcanzar cualquier nodo destino de la red en un tiempo finito.

Inanición (Starvation)

Para los paquetes que se encuentren en el puerto de inyección, el mecanismo de control de acceso al recurso es injusto, porque para ganar acceso al enlace de salida necesitan dos huecos para paquetes en el bloque constructivo en que se encuentre y un hueco en el encaminador vecino (señal de control de flujo VCT habilitada) Por el contrario, para ganar acceso al puerto de salida, los paquetes almacenados en el búfer de la etapa de expulsión solo requieren la señal de control de flujo validada para progresar al encaminador vecino. En situaciones de tráfico adverso o forzado, esto podría retrasar indefinidamente la inyección de nuevos paquetes en la red. Por ejemplo, en patrones de tráfico sintético, tales como la matriz transpuesta persistente, los encaminadores cerca de la diagonal podrían no ser capaces de inyectar nuevos paquetes. No obstante, el tener un camino directo desde el inyector hacia todos los puertos de salida permite sortear la situación. Tras un número de ciclos suficientemente grande esperando para inyectar un nuevo paquete a través de un puerto de salida adecuado (para llegar al destino), se permite la inyección en cualquier puerto de salida disponible (incluso en los no adecuados). Dado que las etapas DFIFO tienen una aceleración de dos y el encaminador tiene solo un bucle interno, no es posible atascar todos los puertos de salida del enrutador con tráfico en tránsito. Por tanto, se garantiza que bajo cualquier condición de tráfico de entrada el paquete es inyectado dentro de una cantidad de tiempo limitado, lo cual es equivalente a decir que el encaminador está libre de inanición.

Nótese que habilitar la utilización de puertos de salida que alejen el paquete de su destino es equivalente a permitir enrutamiento subóptimo en el puerto de inyección. Ésta es una técnica bien conocida [A. Singh, W. J. Daily, A. K. Gupta and B. Towles, "GOAL: A Load-Balanced Adaptive Routing Algorithm for Torus Networks", ISCA 2003] usada para aumentar el ancho de banda de inyección, lo cual mejora el rendimiento. De hecho, aplicando esta estrategia, el rendimiento del encaminador de la invención en patrones de tráfico persistentes se mejora significativamente.

A continuación se describe una serie de características requeridas por los multiprocesadores en chip (CMP) con coherencia hardware:

Soporte adaptativo multidestino (Adaptive Multicast Support)

Añadir al encaminador de la invención soporte adaptativo multidifusión dentro de la red es algo directo a partir de Jerger, N. E., Peh, L. S., & Lipasti, M. (2008). Virtual circuit tree multicasting: A case for on-chip hardware multicast support. Computer Architecture, 2008. ISCA□ 08. 35th International Symposium on (p. 229-240).Ya que la organización del bucle interno es similar, podemos distribuir la tabla de encaminamiento alrededor de los puertos de salida usando máscaras de registro (register marks) como en la cita anterior. De esta forma, mientras que el paquete avanza a través del bucle interno, puede hacerse una réplica del paquete en cada puerto de salida donde las mascaras indiquen que desde ese puerto pueden alcanzarse uno o más destinos. Para soportar la replicación libre de interbloqueo, se necesita espacio para al menos dos paquetes en la etapa de expulsión del camino entrante desde el bucle interno. Si no, se podría agotar el hueco salvavidas en el proceso de replicación. Esto establece la capacidad de almacenamiento mínima de dos paquetes para ese módulo. El encaminador de la invención es capaz de realizar circunvalación (bypass) de enrutamiento con paquetes multidifusión cuando todos los destinos del paquete entrante en la etapa de recepción son alcanzables a través del camino de circunvalación. Si se cumplen las condiciones de circunvalación, el paquete se mueve directamente desde la etapa de recepción hacia el enlace de salida. No merece la pena realizar réplicas de paquetes en la etapa de recepción para también reducir la latencia de contención en los paquetes multidifusión.

Evitación de Interbloqueo Extremo-a-Extremo (End-to-end Deadlock avoidance)

Aunque aplicando las modificaciones de control de flujo propuestas por P. Abad, V. Puente, y J.A. Gregorio en "Reducing the Interconnection Network Cost of Chip Multiprocessors", International Symposium on Networks-on-Chip (NOCS), February 2008, podría reservarse y usarse una porción de capacidad de almacenamiento para cada clase de tráfico, esto no es suficiente para evitar interbloqueo extremo-a-extremo. Ahora el consumo ocurre directamente en la etapa de recepción. Por ejemplo, en la figura 3, un paquete p¡ se localiza en la etapa de recepción del encaminador B Suponemos que p¡ pertenece a una clase de tráfico de prioridad baja y es dirigido al procesador B y su cola de consumo está desbordada. Por tanto, el paquete p„ del encaminador A dirigido hacia el procesador B no puede avanzar a través del enlace directo incluso si pertenece a una clase de tráfico de una prioridad más alta. Si ocurre la misma situación en el resto de etapas de recepción del procesador B, podría ocurrir interbloqueo de protocolo (protocol-deadlock) ya que el paquete a la cabeza de la cola de consumo, Consl, podría requerir que el paquete p„ se consumiese por el controlador y no es posible encontrar un camino disponible hacia la cola de consumo. No obstante, la solución es que tras detectarse la situación mostrada (proporcionando a la etapa de recepción de conocimiento sobre el estado de la cola de consumo de la interfaz de red) en la figura podemos desviar p¡ al bucle interno del encaminador B. Como no hay camino entre el bucle interno y la cola de consumo local, este paquete se marca como en escape y abandonará el encaminador. Desde el encaminador adyacente, el paquete podría re-entrar al nodo destino e intentaría acceder al consumidor otra vez. Como puede observarse, el método es equivalente al empleado para evitar interbloqueo a nivel de red y, de forma similar, tiene un impacto despreciable en el rendimiento porque la probabilidad de desbordamiento del consumidor es muy baja (Y.H. Song, T.M. Pinkston, "A Progressive Approach to Handling Message-Dependent Deadlock in Parallel Computer Systems", IEEE Transactions on Parallel and Distributed Systems, Vol. 14, no. 3, 2003).

Nótese que para todos los posibles paquetes almacenados en la etapa de expulsión del encaminador A, el control de flujo garantiza que pueden almacenarse en el bucle del encaminador B (P. Abad, V. Puente, y J. A. Gregorio en "Reducing the Interconnection Network Cost of Chip Multiprocessors", International Symposium on Networks-on- Chip (NOCS), February 2008). Por tanto, independientemente de su prioridad y destino, aplicando el método previo, el paquete p _n podría avanzar.

Soporte de Entrega Ordenada (In-order Delivery Support)

Como solo hay un bucle interno y con capacidad de almacenamiento reducida, es rentable restringir el acceso al bucle a un solo paquete ordenado por puerto de entrada. En consecuencia, no hay necesidad de hacerle un seguimiento con tablas que indiquen el orden de salida de cada paquete (P. Abad, V. Puente, y J.A. Gregorio en "Reducing the Interconnection Network Cost of Chip Multiprocessors", International Symposium on Networks-on-Chip (NOCS), February 2008). La única restricción impuesta por el encaminador de la invención es que para aplicar circunvalación de baja carga, es necesario no tener ningún paquete ordenado (in-order packet) en el anillo. Esto garantiza que un paquete entrante, del mismo puerto de entrada, no sea adelantado. Aunque esta decisión es muy conservadora, una vez más no es rentable añadir complejidad para usar una política más agresiva.

Además, ya que el mecanismo propuesto para evitar el bloqueo del puerto de entrada tras el desbordamiento de la cola de consumo podría perturbar el orden de los paquetes, la señal de control de flujo generada de acuerdo con P. Abad y otros ("Reducing the Interconnection Network Cost of Chip Multiprocessors", International Symposium on Networks-on-Chip (NOCS), February 2008) para clases ordenadas de tráfico (in-order classes of traffic) se oculta con la ocupación de cola de la interfaz de red para clases ordenadas de tráfico. Si hay hueco para menos de cuatro paquetes, se impone la señal de stop a todos los encaminadores adyacentes. Se trabaja bajo la suposición razonable de que el tráfico ordenado representa un porcentaje pequeño del tráfico, lo cual es cierto para la mayoría de los protocolos coherentes usados actualmente (Y.H. Song, T.M. Pinkston, "A Progressive Approach to Handling Message-Dependent Deadlock in Parallel Computer Systems", IEEE Transactions on Parallel and Distributed Systems, Vol. 14, no. 3, 2003).