Diseño de redes de interconexión
Un interconnection networken una máquina paralela transfiere información desde cualquier nodo fuente a cualquier nodo destino deseado. Esta tarea debe completarse con la menor latencia posible. Debería permitir que un gran número de transferencias de este tipo se realicen simultáneamente. Además, debería ser económico en comparación con el costo del resto de la máquina.
La red está compuesta por enlaces y conmutadores, lo que ayuda a enviar la información desde el nodo de origen al nodo de destino. Una red se especifica por su topología, algoritmo de enrutamiento, estrategia de conmutación y mecanismo de control de flujo.
Estructura organizativa
Las redes de interconexión se componen de los siguientes tres componentes básicos:
Links- Un enlace es un cable de una o más fibras ópticas o cables eléctricos con un conector en cada extremo conectado a un conmutador o puerto de interfaz de red. A través de esto, se transmite una señal analógica desde un extremo, se recibe en el otro para obtener el flujo de información digital original.
Switches- Un interruptor se compone de un conjunto de puertos de entrada y salida, una "barra transversal" interna que conecta todas las entradas a todas las salidas, almacenamiento interno en búfer y lógica de control para efectuar la conexión de entrada y salida en cada momento. Generalmente, el número de puertos de entrada es igual al número de puertos de salida.
Network Interfaces- La interfaz de red se comporta de manera bastante diferente a los nodos de conmutación y puede conectarse mediante enlaces especiales. La interfaz de red formatea los paquetes y construye la información de enrutamiento y control. Puede tener almacenamiento en búfer de entrada y salida, en comparación con un interruptor. Puede realizar una comprobación de errores y un control de flujo de un extremo a otro. Por lo tanto, su costo está influenciado por su complejidad de procesamiento, capacidad de almacenamiento y número de puertos.
Red de interconexión
Las redes de interconexión están compuestas por elementos de conmutación. La topología es el patrón para conectar los conmutadores individuales a otros elementos, como procesadores, memorias y otros conmutadores. Una red permite el intercambio de datos entre procesadores en el sistema paralelo.
Direct connection networks- Las redes directas tienen conexiones punto a punto entre nodos vecinos. Estas redes son estáticas, lo que significa que las conexiones punto a punto son fijas. Algunos ejemplos de redes directas son anillos, mallas y cubos.
Indirect connection networks- Las redes indirectas no tienen vecinos fijos. La topología de comunicación se puede cambiar dinámicamente según las demandas de la aplicación. Las redes indirectas se pueden subdividir en tres partes: redes de bus, redes multietapa y conmutadores de barras cruzadas.
Bus networks- Una red de bus está compuesta por una serie de líneas de bits a las que se adjuntan varios recursos. Cuando los buses utilizan las mismas líneas físicas para datos y direcciones, los datos y las líneas de direcciones se multiplexan en el tiempo. Cuando hay varios maestros de bus conectados al bus, se requiere un árbitro.
Multistage networks- Una red de varias etapas consta de varias etapas de conmutadores. Se compone de interruptores 'axb' que se conectan mediante un patrón de conexión entre etapas (ISC) particular. Los elementos de conmutador pequeños de 2x2 son una opción común para muchas redes de varias etapas. El número de etapas determina el retraso de la red. Al elegir diferentes patrones de conexión entre etapas, se pueden crear varios tipos de red de múltiples etapas.
Crossbar switches- Un interruptor de barra transversal contiene una matriz de elementos de interruptor simples que se pueden encender y apagar para crear o romper una conexión. Al encender un elemento conmutador en la matriz, se puede establecer una conexión entre un procesador y una memoria. Los interruptores de barra transversal no bloquean, es decir, todas las permutaciones de comunicación se pueden realizar sin bloqueo.
Evaluación de compensaciones de diseño en topología de red
Si la principal preocupación es la distancia de enrutamiento, entonces se debe maximizar la dimensión y hacer un hipercubo. En el enrutamiento de almacenamiento y reenvío, suponiendo que el grado de conmutación y la cantidad de enlaces no fueron un factor de costo significativo, y que la cantidad de enlaces o el grado de conmutación son los costos principales, la dimensión debe minimizarse y una malla construido.
En el peor de los casos, el patrón de tráfico de cada red, se prefiere tener redes de alta dimensión donde todos los caminos son cortos. En los patrones en los que cada nodo se comunica con solo uno o dos vecinos cercanos, se prefiere tener redes de baja dimensión, ya que solo se utilizan algunas de las dimensiones.
Enrutamiento
El algoritmo de enrutamiento de una red determina cuál de las posibles rutas desde el origen al destino se usa como rutas y cómo se determina la ruta seguida por cada paquete en particular. El enrutamiento de orden de dimensión limita el conjunto de rutas legales para que exista exactamente una ruta desde cada origen a cada destino. La obtenida viajando primero la distancia correcta en la dimensión de orden superior, luego la siguiente dimensión y así sucesivamente.
Mecanismos de enrutamiento
La aritmética, la selección de puerto basada en la fuente y la búsqueda de tablas son tres mecanismos que utilizan los conmutadores de alta velocidad para determinar el canal de salida a partir de la información del encabezado del paquete. Todos estos mecanismos son más simples que el tipo de cálculos de enrutamiento general implementados en los enrutadores LAN y WAN tradicionales. En redes de computadoras en paralelo, el conmutador debe tomar la decisión de enrutamiento para todas sus entradas en cada ciclo, por lo que el mecanismo debe ser simple y rápido.
Enrutamiento determinista
Un algoritmo de enrutamiento es determinista si la ruta tomada por un mensaje está determinada exclusivamente por su origen y destino, y no por otro tráfico en la red. Si un algoritmo de enrutamiento solo selecciona las rutas más cortas hacia el destino, es mínimo; de lo contrario, no es mínimo.
Libertad de punto muerto
El interbloqueo puede ocurrir en varias situaciones. Cuando dos nodos intentan enviarse datos entre sí y cada uno comienza a enviarse antes de que cualquiera de los dos los reciba, puede producirse un bloqueo "frontal". Otro caso de interbloqueo ocurre cuando hay varios mensajes que compiten por recursos dentro de la red.
La técnica básica para probar que una red está libre de interbloqueo es eliminar las dependencias que pueden ocurrir entre canales como resultado de los mensajes que se mueven a través de las redes y mostrar que no hay ciclos en el gráfico general de dependencia de canales; por tanto, no existen patrones de tráfico que puedan conducir a un punto muerto. La forma común de hacer esto es numerar los recursos del canal de manera que todas las rutas sigan una secuencia particular creciente o decreciente, de modo que no surjan ciclos de dependencia.
Diseño de interruptor
El diseño de una red depende del diseño del conmutador y de cómo se conectan entre sí. El grado del conmutador, sus mecanismos de enrutamiento internos y su almacenamiento en búfer interno decide qué topologías se pueden admitir y qué algoritmos de enrutamiento se pueden implementar. Como cualquier otro componente de hardware de un sistema informático, un conmutador de red contiene una ruta de datos, control y almacenamiento.
Puertos
El número total de pines es en realidad el número total de puertos de entrada y salida multiplicado por el ancho del canal. A medida que el perímetro del chip crece lentamente en comparación con el área, los interruptores tienden a estar limitados por pines.
Ruta de datos interna
La ruta de datos es la conectividad entre cada uno del conjunto de puertos de entrada y cada puerto de salida. Generalmente se le conoce como la barra transversal interna. Una barra transversal sin bloqueo es aquella en la que cada puerto de entrada se puede conectar a una salida distinta en cualquier permutación simultáneamente.
Búferes de canal
La organización del almacenamiento intermedio dentro del conmutador tiene un impacto importante en el rendimiento del conmutador. Los enrutadores y conmutadores tradicionales tienden a tener grandes búfer SRAM o DRAM externos a la estructura del conmutador, mientras que en los conmutadores VLSI el almacenamiento en búfer es interno al conmutador y proviene del mismo presupuesto de silicio que la ruta de datos y la sección de control. A medida que aumenta el tamaño y la densidad del chip, hay más almacenamiento en búfer disponible y el diseñador de la red tiene más opciones, pero aún así, el espacio del búfer es una opción principal y su organización es importante.
Control de flujo
Cuando varios flujos de datos en la red intentan utilizar los mismos recursos de red compartidos al mismo tiempo, se deben tomar algunas medidas para controlar estos flujos. Si no queremos perder ningún dato, algunos de los flujos deben bloquearse mientras otros continúan.
El problema del control de flujo surge en todas las redes y en muchos niveles. Pero es cualitativamente diferente en las redes de computadoras paralelas que en las redes de área local y amplia. En las computadoras paralelas, el tráfico de red debe entregarse con la misma precisión que el tráfico a través de un bus y hay una gran cantidad de flujos paralelos en una escala de tiempo muy pequeña.