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
Tipo: Patente de Invención. Resumen de patente/invención. Número de Solicitud: P200701403.
Solicitante: UNIVERSIDAD DE CANTABRIA.
Nacionalidad solicitante: España.
Provincia: CANTABRIA.
Inventor/es: PUENTE VARONA,VALENTIN, GREGORIO MONASTERIO,JOSE ANGEL, ABAD FIDALGO,PABLO, PRIETO TORRALBO,PABLO.
Fecha de Solicitud: 10 de Mayo de 2007.
Fecha de Publicación: .
Fecha de Concesión: 19 de Enero de 2010.
Clasificación Internacional de Patentes:
- H04L12/56C
Clasificación PCT:
- H04L12/56
![ENCAMINADOR DE MENSAJES PARA REDES DE INTERCONEXION DE SISTEMAS MULTIPROCESADOR.](https://patentados.com/img/2010/02/encaminador-mensajes-redes-interconexion-sistemas-multiprocesador.jpg)
Fragmento de la descripción:
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...
Reivindicaciones:
1. Encaminador de mensajes para redes de interconexión de sistemas multiprocesador. Está caracterizado por estar compuesto de los elementos siguientes:
- - Una etapa de entrada por cada uno de los enlaces de interconexión, incluido el del elemento de proceso al que esté asociado.
- - Una etapa de salida por cada uno de los enlaces de interconexión, incluido el del elemento de proceso al que esté asociado.
- - Una estructura de búferes de almacenamiento interconectados formando dos anillos concéntricos de direcciones opuestas a través de los cuales son obligados a circular los paquetes de información hasta que alcancen un puerto de salida libre que los acerque a su destino.
- - Mecanismo para la limitación del número máximo de paquetes que pueden introducirse en cada anillo.
- - Un mecanismo para la cuenta y limitación del número de giros que podrán dar los paquetes de información en el interior de cada anillo.
2. Encaminador de mensajes para redes de interconexión de, según reivindicación 1ª, caracterizado porque cualquiera de sus etapas de entrada está formada por un buffer de almacenamiento de tipo FIFO, conectado a un multiplexor que permite dirigir los paquetes a cualquiera de los dos anillos de conforman el encaminador.
3. Encaminador de mensajes para redes de interconexión, según reivindicación 1ª, caracterizado porque cualquiera de sus etapas de salida está formada por dos buffer de almacenamiento de tipo FIFO que recoge los paquetes de cada uno de los anillos que conforman el encaminador que deseen utilizar esta salida y los multiplexa en el único canal de salida.
4. Encaminador de mensajes para redes de interconexión, según reivindicación 1ª, caracterizado porque cualquiera de sus etapas intermedias de almacenamiento está formada por dos búferes de doble puerta, cada uno de los cuales forman parte de uno de los anillos y se encargan de almacenar los paquetes provenientes tanto del puerto de entrada asociado, como de los que circulan por el mismo anillo.
5. Encaminador de mensajes para redes de interconexión, según reivindicación 1ª, caracterizado porque el número de paquetes que puede ser introducido en cada anillo nunca será superior a su capacidad máxima menos dos por lo que evitará el interbloqueo de paquetes en el interior de cada anillo.
6. Encaminador de mensajes para redes de interconexión de sistemas multiprocesador en chip, según reivindicación 1ª, caracterizado porque contabilizará el número de giros que vaya dando cualquier paquete de información en el interior de cualquiera de sus anillos. Si transcurrido un número máximo de vueltas a cualquiera de los anillos, un paquete no ha encontrado libre uno de sus puertos deseados, será obligado a abandonar el encaminador por el primer puerto de salida libre que se encuentre en su camino de giro.
Patentes similares o relacionadas:
MÉTODO Y SISTEMA PARA OBTENER INFORMACIÓN DE RUTA Y ELEMENTO DE SU CÁLCULO, del 28 de Diciembre de 2011, de HUAWEI TECHNOLOGIES CO., LTD.: Un método para obtener información de ruta que comprende las etapas que consisten en: calcular, por un Elemento de Cálculo de Ruta origen, PCE, una ruta más corta […]
MÉTODO Y DISPOSITIVO PARA LA CREACIÓN DE UNA PASARELA DE ENLACE EN UNA RED PUNTO A MULTIPUNTO, del 22 de Noviembre de 2011, de HUAWEI TECHNOLOGIES CO., LTD.: Un método para poner en práctica una Pasarela de Enlace (Link Pass Through) en una red punto a multipunto, siendo el método aplicable en la red que tiene una puerta de acceso […]
MÉTODO, EQUIPO Y SISTEMA PARA EL REENVIO DE UN FLUJO DE MULTIDIFUSIÓN, del 18 de Noviembre de 2011, de HUAWEI TECHNOLOGIES CO., LTD.: Un método para el reenvío de un flujo de multidifusión cuando una ruta de unidifusión hasta una fuente de multidifusión o punto de encuentro cambia desde una primera ruta […]
MÉTODO Y SISTEMA PARA IMPLEMENTACIÓN DE SBLP PARA UN SISTEMA INTEGRADO WLAN-GSM/3G, del 14 de Noviembre de 2011, de TELEFONAKTIEBOLAGET L M ERICSSON (PUBL): La pasarela de paquetes de datos (PDG) en una red central integrada WLAN - GSM/3G, que comprende un encaminador (R) que tiene una serie de pasarelas […]
MÉTODO Y APARATO PARA PROPORCIONAR UN SERVICIO MULTIDIFUSIÓN CON MÚLTIPLES TIPOS DE PROTECCIÓN Y RECUPERACIÓN, del 21 de Septiembre de 2011, de HUAWEI TECHNOLOGIES CO., LTD.: Un método para proteger un servicio multidifusión, que comprende: dividir un servicio multidifusión en una pluralidad de servicios punto a punto unidireccionales […]
MÉTODO, DISPOSITIVO Y SISTEMA PARA LA CONMUTACIÓN DE TRÁFICO EN INGENIERÍA DE TRÁFICO DE CONMUTACIÓN MULTIPROTOCOLO POR ETIQUETA, del 3 de Agosto de 2011, de HUAWEI TECHNOLOGIES CO., LTD.: Un método para conmutación de tráfico en Ingeniería de Tráfico con Conmutación de Etiqueta Multiprotocolo MPLS TE, que comprende: la transmisión, por un Proveedor […]
PROCEDIMIENTO DE CONMUTACIÓN AUTOMÁTICA DE PROTECCIÓN, del 20 de Julio de 2011, de ZTE CORPORATION: Procedimiento para la conmutación automática de protección en una red, en el que la red comprende nodos y enlaces entre los nodos cuando se produce un fallo en un canal físico […]
TRATAMIENTO DE LLAMADAS TERMINALES EN UN SISTEMA DISTRIBUIDO, del 7 de Junio de 2011, de TELEFONAKTIEBOLAGET LM ERICSSON (PUBL): Un conmutador adaptado para enrutamiento de llamada en una red de comunicaciones móvil, incluyendo el conmutador al menos un clúster , comprendiendo […]