PDF de programación - BUFFER AUTOCOMPACTANTE PARA SWITCHES Y RUTEADORES EN SISTEMAS PARALELOS

CENTRO DE INVESTIGACIÓN Y DE ESTUDIOS AVANZADOS

DEL INSTITUTO POLITÉCNICO NACIONAL

DEPARTAMENTO DE INGENIERÍA ELÉCTRICA

SECCIÓN DE COMPUTACIÓN













BUFFER AUTOCOMPACTANTE PARA SWITCHES

Y RUTEADORES EN SISTEMAS PARALELOS

Tesis que presenta

Armando Jiménez Flores

Para Obtener el Grado de
Doctor en Ciencias



En la Especialidad de
Ingeniería Eléctrica
Opción Computación

Director de la Tesis: Dr. Adriano De Luca Pennacchia

México D. F. Marzo 2006



Resumen



Para resolver grandes problemas, los arquitectos de computadoras buscan satisfacer la
creciente demanda de capacidad de cómputo. Aún con el uso del paralelismo, el desempeño
de estas máquinas está limitado por los retardos de comunicación entre sus elementos de
procesamiento. Por lo que, el diseño de la red de interconexión es un factor decisivo en el
desempeño de las computadoras paralelas. Típicamente, el diseño de la red se reduce al
diseño del elemento de comunicación, conocido como switch o ruteador. Existen
condiciones que hacen necesario el almacenamiento temporal de los datos de comunicación
entre procesadores. Para ello se utilizan buffers, dentro del elemento de comunicación, que
mejoran su desempeño. No obstante, si la administración del buffer es ineficiente, el
desempeño del switch o ruteador se decrementa seriamente.







El objetivo de esta tesis es diseñar una memoria especial de alto desempeño que
permita reducir los tiempos de comunicación de datos entre los elementos de procesamiento
de un sistema paralelo. Esta memoria es utilizada como buffer donde se almacenan
temporalmente los datos que se transfieren entre los procesadores del sistema, y es
aplicable a switches y ruteadores en sistemas de procesamiento paralelo para mejorar la
latencia de comunicación. Se diseña un modelo de buffer que administra dinámicamente los
espacios de almacenamiento y permite la concurrencia de operaciones de escritura y
lectura. Su modelo se basa en un conjunto de cinco operaciones fundamentales que incluye
escrituras o lecturas simples y operaciones paralelas que combinan una escritura con una
lectura. Al buffer lo hemos denominado BAC (Buffer Auto-Compactante), porque mantiene
compactado su espacio de almacenamiento. El BAC es implementado en código VHDL
(Very-High-Speed-Integrated-Circuit Hardware Description Language) y simulado a nivel
lógico con una herramienta computacional basada en dicho lenguaje. Se busca que el
modelo del BAC administre eficientemente los espacios y tenga propiedades de baja
latencia que puedan ser aprovechadas en la implementación.

Para resaltar las propiedades de alto desempeño del BAC, se diseñó completamente en
hardware, con un tipo de control distribuido paralelo que utiliza una celda de control por
cada localidad del buffer. La capacidad del BAC es expandible: puede crecer en ancho y
largo, manteniendo constantes la complejidad de sus celdas de control y el tamaño del bus
de direcciones. Cada una de las cinco operaciones fundamentales del BAC se realiza
durante un solo ciclo de reloj. Estas consideraciones en el diseño reducen los retardos de
comunicación debidos a la administración de los buffers e incrementan el desempeño de los
elementos de comunicación.

Las contribuciones de esta tesis son las siguientes: Un análisis de las posibles
configuraciones arquitecturales para un buffer de propósito específico desde la perspectiva
de su desempeño, un diseño específico completo de un modelo de buffer (BAC) de baja
latencia y acceso concurrente, una implementación en VHDL del BAC, un diseño y
verificación funcional de los componentes que integran el BAC.
Palabras clave: paralelismo, switch, ruteador, buffer, autocompactante, latencia, VHDL.





ii

Abstract


In order to solve large problems, the goal of computer architects is to satisfy the
growing computational demand. Even with the use of parallel computing, the performance
of these machines is limited by communication delays among its processing elements. That
is why interconnection network design is a decisive factor in parallel computer
performance. Typically, the design of the network focusses on the design of the
communication element known as switch or router. There are conditions that make
necessary to keep communication data in temporary storage. Such storage is provided by
buffers inside the communication element to improve network performance. Nevertheless,
when buffer management is inefficient, the switch or router performance may seriously
deteriorate.


The goal of this thesis is to design a high performance special memory that allows the
reduction of data communication delays among the processing elements of a parallel
system. This special memory is used as buffer where the data transferred among system
processors is temporarily stored and can be used by switches and routers in parallel
processing systems to improve communication latency. A buffer model is designed to
dynamically manage the storage spaces allowing concurrent writing and reading operations.
Such model is based on a group of five fundamental operations that include simple writings
or readings and parallel operations that combine one writing with one reading. The buffer is
referred to as BAC (“Buffer Auto-Compactante”–Self-Compacting Buffer), because it
maintains compacted its storage space. The BAC is implemented in VHDL code (Very-
High-Speed-Integrated-Circuit Hardware Description Language) and is simulated at logical
level with a CAD tool based on this language. The aim of the BAC model is to manage the
storage spaces efficiently and to have low latency properties, that can be taken advantage of
by the implementation.


To reach the BAC performance full potential, the buffer was totally designed in
hardware with a parallel distributed control type that uses a control cell for each buffer
locality. The BAC capacity is expandable: it can grow both in width and length,
maintaining constant the complexity of the control cells and the address bus size. Each one
of the five BAC’s fundamental operations is carried out during a single clock cycle. These
design considerations reduce the communication delays caused by buffers' management
and increase the performance of the communication elements.


The contributions of this thesis are the following: An analysis of architectural possible
configurations for a specific purpose buffer from the perspective of their performance, a
complete specific design of a buffer model (BAC) of low latency and concurrent access, a
BAC implementation on VHDL, and a design and functional verification of the
components that integrate the BAC.


Keywords: parallelism, switch, router, buffer, self-compacting, latency, VHDL.



iii

























A mis adorables hijas: Abigail, Diana y Angélica



A mi amada esposa: Mary



A mis queridos padres: Santa e Ignacio



A mis entrañables hermanos: Mina, Nacho y Gaby





GRACIAS

iv



Agradecimientos



Agradezco ampliamente a mi director de tesis Dr. Adriano De Luca Pennacchia, el
haberme aceptado como su discípulo en la sugestiva aventura de realizar un doctorado. El
tema de investigación que me planteó, así como, su guía y asesoría me permitieron
desarrollar este trabajo de tesis.

Igualmente, estoy agradecido con el Dr. Sergio V. Chapa Vergara porque, durante su
gestión como jefe de la Sección de Computación del Centro de Investigación y de Estudios
Avanzados (CINVESTAV) del Instituto Politécnico Nacional (IPN), me apoyó para
ingresar como docente y para ser aceptado como alumno de doctorado. Sus observaciones
durante el examen predoctoral y sus recomendaciones finales mejoraron la estructura y el
contenido de este documento.

De manera muy especial, agradezco al Dr. Héctor Ruiz Barradas por su permanente
interés que, como compañero y profesor, ha mostrado por mi trabajo. Por su valioso tiempo
dedicado en la revisión y corrección de este documento. Por la asesoría sobre la notación
utilizada y sus invaluables consejos.

Mi profundo agradecimiento a las autoridades, profesores y personal administrativo
del CINVESTAV del IPN, así como, a las autoridades del Consejo Nacional de Ciencia y
Tecnología, por los apoyos recibidos durante la realización de mis estudios de Maestría y
Doctorado.

Reconozco mi deuda con las autoridades del IPN, por todas las facilidades otorgadas.
Particularmente, el Ing. Jorge E. Martínez Rodríguez y el Dr. Cornelio Robledo Sosa
quienes, durante su gestión como directores de la Escuela Superior de Ingeniería Mecánica
y Eléctrica (ESIME) del IPN, depositaron en mí su confianza. Asimismo, agradezco al Dr.
José Madrid Flores y al M. en C. Salvador Saucedo Flores por los apoyos otorgados para
ingresar a la planta docente de la ESIME.



v

Debo agradecer a las autoridades de la Universidad Autónoma Metropolitana, Unidad
Azcapotzalco (UAM-Azc.), por su comprensión durante la realización de este proyecto.
Gracias también al Dr. Armando Maldonado Talamantes, quien me ayudó a ingresar a la
planta docente del Departamento de Electrónica de la División de Ciencias Básicas e
Ingeniería de la UAM-Azc.

Agradezco al Dr. José G. Delgado Frías sus recomendaciones para mejorar este
documento y el interés mostrado en nuestro proyecto desde que se