Red de intercambio aleatorio
En teoría de grafos , la red de intercambio aleatorio es un multigraph cúbico no dirigido , cuyos vértices representan secuencias binarias de una longitud determinada y cuyos bordes representan dos operaciones en esta secuencia, cambios circulares y voltear el bit de orden más bajo. [1]
En la versión de esta red presentada por Tomas Lang y Harold S. Stone en 1976, [2] simplificando el trabajo anterior de Stone en 1971, [3] la red de orden de intercambio aleatorio consistía en una matriz de celdas, numeradas por los diferentes números binarios que se pueden representar con bits. Estas celdas estaban conectadas por enlaces de comunicaciones en dos patrones diferentes: enlaces de "intercambio" en los que cada celda está conectada a la celda numerada con el valor opuesto en su bit de orden más bajo, y enlaces "aleatorios" en los que cada celda está conectada a la celda cuyo número se obtiene mediante un desplazamiento circularque cambia cada bit a la siguiente posición más significativa, excepto el bit de orden más alto que cambia a la posición de orden más bajo. Los enlaces de "intercambio" son bidireccionales, mientras que los enlaces "aleatorios" solo pueden transferir información en una dirección, desde una celda a su desplazamiento circular. [2]
El trabajo posterior en redes con esta topología eliminó la distinción entre enlaces de comunicación unidireccionales y bidireccionales, permitiendo que la información fluya en cualquier dirección a través de cada enlace. [1] [4]
La ventaja de este patrón de comunicaciones, sobre los métodos anteriores, es que permite que la información se transfiera rápidamente a través de un pequeño número de pasos desde cualquier vértice de la red a cualquier otro vértice, mientras que solo requiere un solo bit de información de control (cuál de los dos enlaces de comunicación para usar) para cada paso de comunicación. [2] Se conocen algoritmos rápidos en paralelo para problemas básicos que incluyen clasificación , multiplicación de matrices , evaluación de polinomios y transformadas de Fourier para los sistemas en paralelo que utilizan esta red. [4]
Si a esta red se le da un diseño sencillo en la celosía entera , con los vértices colocados en una línea en orden numérico, con cada borde de la celosía llevando parte de como máximo un enlace de comunicación, y con cada vértice o cruce de la red colocado en una celosía. punto, el diseño utiliza el área , cuadrática en su número de vértices. Sin embargo, F. Thomson Leighton describió en su tesis doctoral de 1981 diseños más compactos y asintóticamente óptimos con área . [4]
Una red de comunicaciones relacionada, la "red omega" o red de intercambio aleatorio de múltiples etapas , consta de un número determinado de etapas, cada una de las cuales consta de vértices, con los enlaces aleatorios que conectan pares de vértices en etapas consecutivas y los enlaces de intercambio conectan pares de vértices en el mismo escenario entre sí. [5]
