ENCAMINADOR DE MENSAJES PARA REDES DE INTERCONEXION DE SISTEMAS MULTIPROCESADOR.

Encaminador de mensajes para redes de interconexión de sistemas multiprocesador caracterizado por estar especialmente adaptado para el intercambio de información de forma adaptativa e independiente de la topología entre los elementos de proceso integrados en un solo chip.

El encaminador resuelve importantes problemas técnicos que se presentan en la interconexión de un número elevado de procesadores en un único chip cuando actualmente únicamente se dispone de encaminadores especialmente diseñados para la interconexión de dispositivos localizados en chips separados.

El encaminador se caracteriza por los siguientes elementos básicos:

- Dos anillos concéntricos, cada uno esta formado por un grupo de buffers de doble puerto.

- Un conjunto de etapas de entrada y de salida en número igual al grado del encaminador, a través de las cuales entran o salen los paquetes provenientes de los encaminadores vecinos.

- Una etapa de inyección y consumo para su comunicación con el elemento de procesoasociado

Encaminador de mensajes para redes de interconexión de sistemas multiprocesador.

Sector de la técnica

La invención está relacionada con las redes de interconexión de altas prestaciones que puedan ser empleadas en sistemas multiprocesadores a nivel de sistema o a nivel de un solo chip (sistemas conocidos como CMPs) y en general cualquier sistema que emplee un mecanismo de comunicación descentralizado basado en redes punto a punto, conmutación de paquetes y empleando tecnología electrónica. Dada la elevada aplicabilidad de la idea, ejemplificaremos su uso en el caso específico de los sistemas CMP.

Estado de la técnica

La integración de varios procesadores en un solo chip aparece como la vía más efectiva para manejar el enorme incremento de complejidad de las actuales y futuras microarquitecturas. La organización de su jerarquía de memoria es una característica de diseño de primer orden y el subsistema de comunicación para su soporte una parte esencial del mismo. Aunque actualmente en los multiprocesadores en chip (CMP) es común el uso de estructuras de interconexión centralizadas [7][11] el incremento del número de bloques funcionales [2] obligará a la descentralización en el sistema de comunicación y las redes punto a punto se postulan como el mejor candidato [3][4] y en este contexto es en el que se centra la presentación de esta invención. En el caso particular de los CMPs, dentro del chip, la red y los niveles superiores del sistema están mucho más próximos que en las redes fuera del chip. Esto significa menor latencia y mayor anchura de banda, pero a costa de un incremento del coste de implementación en área de silicio y mayores restricciones de potencia y estos son factores decisivos de diseño [1][8][10] por lo que representa un campo de aplicación más exigente que otros fuera del chip.

La invención aquí presentada cumple los principales requerimientos mencionados, manteniendo un coste hardware adecuado. La arquitectura está basada en un encaminador, denominado Rotary Router, que toma ventaja del pequeño tamaño de los paquetes de información en estos entornos, permite el uso de encaminamiento adaptativo en topologías arbitrarias y los paquetes apenas sufren el efecto del bloqueo de cabeza (HOL, head of line blocking).

Actualmente, ninguno de los sistemas multiprocesadores en chip comerciales posee una estructura de interconexión como la que se presenta en esta invención y la bibliografía existente sobre este tipo de sistemas, aunque es profusa, son escasos los trabajos focalizados sobre las redes de interconexión de este tipo de sistemas. Un trabajo reciente en esta línea es [8], pero únicamente se analizan estructuras centralizadas y las redes punto a punto se mencionan como futura línea. Uno los trabajos seminales sobre el empleo de estas redes en los sistemas multiprocesadores en chip con argumentaciones consistentes es [3] y posteriormente ampliado en [1]. No obstante, solo fueron consideradas arquitecturas tradicionales de encaminador. Recientemente Mullins y otros en [9] introducen un nuevo encaminador con un tiempo de paso de un ciclo sin contención, pero con esquemas convencionales de almacenamiento de entrada-salida por lo que no suministra ningún mecanismo especial para el aprovechamiento de los recursos de almacenamiento y mejorar el retraso producido por la congestión, como en el caso de la invención presentada. En [6][2] se propone una organización seccionada para el crossbar, aunque requiere encaminamiento adelantado (look-ahead). Del mismo modo, no existe ninguna propuesta similar en el campo de las redes fuera del chip.

Nuestra invención se basa en el empleo de un encaminador de mensajes que se aparta de las estructuras mencionadas en los trabajos anteriores y habitualmente empleadas en los sistemas multiprocesadores dentro y fuera del chip. Su estructura se asemeja a la de una rotonda de tráfico de automóviles. Los paquetes de información entran en una estructura de almacenamiento circular y avanzan buscando el puerto de salida que les acerque a destino. La principal novedad estriba en que si el puerto de salida deseado no está disponible, el paquete continuará circulando por el interior de la estructura circular hasta encontrar una salida valida. El principal efecto positivo conseguido es que evita el bloqueo de los paquetes que circulan tras él y por consiguiente elimina el efecto tan pernicioso que ello tiene sobre el rendimiento del sistema.

[1] J. Balfour, W. Dally, "Design Tradeoffs for Tiled CMP On-Chip Networks", International Conference on Supercomputing (ICS) 2006.

[2] S. Borkar, et al. "Platform 2015: Intel Platform and Evolution for the Next Decade", Technology@Intel Magazine, March 2005.

[3] W. Dally, B. Towles, "Route Packets, Not Wires: On-Chip Interconnection Networks", Design Automation Conference (DAC) 2001.

[4] W. Daily, B. Towles, "Principles and Practices of Interconnection Networks". Morgan Kaufmann, 2004.

[5] P. Kerman, L. Kleinrock, "Virtual Cut-Through: A New Computer Communication Switching Technique". Computer Networks, Vol. 3, pp. 267-286, September 1979.

[6] J. Kim, D. Park, T. Theocharides, N. Vijaykrishnan, C. It Das. "A low latency router supporting adaptivity for on-chip interconnects". Design Automation Conference (DAC) 2005.

[7] P. Kongetira, K. Aingaran, K. Olukotun, "Niagara: A 32-way Multithreaded SPARC Processor", IEEE Micro. Vol. 25, No. 2, pp. 21-29, March/April 2005.

[8] IL Kumar, V. Zyuban, D. Tullsen, "Interconnections in Multi-Core Architectures: Understanding Mechanisms, Overheads and Scaling", International Symposium on Computer Architecture (ISCA), 2005.

[9] R Mullins, A. West, S. Moore "Low-Latency Virtual-Channel Routers for On-Chip Networks", International Symposium on Computer Architecture (ISCA), 2004.

[10] K. Olukotun, L. Hammond, "The future of Microprocessors" ACM Queue, Vol. 3, No. 7, September 2005.

[11] H. Hofstee, "Power Efficient Processor Architecture and The Cell Processor", International Symposium on High-Performance Computer Architecture (HPCA), 2005.

[12] V. Puente, J.A. Gregorio, J. M. Prellezo, R. Beivide, J. Duato, C. Izu, "Adaptive Bubble Router. a Design to Improve Performance in Torus Networks", International Conference of Parallel Processing (ICPP) 1999.

Descripción de la invención

La invención, denominada Rotary Router, es un encaminador de mensajes con una nueva arquitectura especialmente diseñada para sistemas multiprocesadores en chip. El encaminador emplea una estructura de almacenamiento organizada en dos anillos concéntricos y que establecen sentido de giro opuesto en el flujo de los paquetes de información, permitiendo así un control completamente descentralizado y da lugar a una estructura altamente escalable con el número de puertos de comunicación del dispositivo. Los paquetes de información que entran en el encaminador son obligados a circular por los anillos hasta que encuentran un puerto de salida que les acerque a su destino. 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 será utilizado por uno de los paquetes en circulación por cualquiera de los dos anillos. Adicionalmente, permite evitar los problemas de interbloqueo entre paquetes sin utilizar canales virtuales e independientemente de la topología empleada para la interconexión. Esta estructura puede ser implementada con un costo razonable en términos de área y consumo de potencia adecuados para su empleo fundamentalmente en los sistemas multiprocesadores en chip. No obstante, sus especiales características de independencia topológica pueden hacerle útil para su empleo también en sistemas multiprocesadores fuera del chip.

Figura 1. Diagrama de bloques del encaminador Rotary Router.

Figura 2. Mecanismos de control de flujo empleados.

Figura 3. Estructura de los buffers FIFO de doble puerto.

Figura 4. Ejemplo de multiprocesador en chip (CMP) y detalle del encaminador...

1. Encaminador de mensajes para redes de interconexión de sistemas multiprocesador. Está caracterizado por estar compuesto de los elementos siguientes: