En teoría de grafos , la red de intercambio aleatorio es un multigrafo cúbico no dirigido , cuyos vértices representan secuencias binarias de una longitud dada y cuyos bordes representan dos operaciones sobre estas secuencias, desplazamientos circulares y la inversión del bit de orden más bajo. [1]
En la versión de esta red introducida por Tomas Lang y Harold S. Stone en 1976 [2], simplificando el trabajo anterior de Stone en 1971 [3] , la red de intercambio aleatorio de orden consistía en una matriz de celdas, numeradas por los diferentes números binarios que pueden representarse 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 de "intercambio aleatorio" en los que cada celda está conectada a la celda cuyo número se obtiene por un desplazamiento circular que desplaza cada bit a la siguiente posición más significativa, excepto el bit de orden más alto que se desplaza a la posición de orden más bajo. Los enlaces de "intercambio" son bidireccionales, mientras que los enlaces de "intercambio aleatorio" sólo pueden transferir información en una dirección, desde una celda a su desplazamiento circular. [2]
Los trabajos posteriores en redes con esta topología eliminaron 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 transferir información rápidamente a través de un pequeño número de pasos desde cualquier vértice en la red a cualquier otro vértice, mientras que solo requiere un único bit de información de control (cuál de los dos enlaces de comunicaciones utilizar) para cada paso de comunicaciones. [2] Se conocen algoritmos paralelos rápidos para problemas básicos que incluyen clasificación , multiplicación de matrices , evaluación de polinomios y transformadas de Fourier para sistemas paralelos que utilizan esta red. [4]
Si a esta red se le da un diseño sencillo en la red entera , con los vértices colocados en una línea en orden numérico, con cada arista de la red llevando parte de como máximo un enlace de comunicación, y con cada vértice o cruce de la red colocado en un punto de la red, el diseño utiliza área , cuadrática en su número de vértices. Sin embargo, F. Thomson Leighton describió diseños más compactos y asintóticamente óptimos con área en su tesis doctoral de 1981. [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 conectando pares de vértices en etapas consecutivas y los enlaces de intercambio conectando pares de vértices en la misma etapa entre sí. [5]
Las mismas operaciones sobre palabras binarias, de rotación y volteo del primer bit, también se pueden utilizar para generar los ciclos cúbicos conexos , una red de comunicaciones paralelas cúbicas diferente con un mayor número de vértices. En lugar de tener las propias palabras binarias como sus vértices, los vértices de los ciclos cúbicos conexos representan operaciones sobre palabras que se pueden generar por rotación y volteo, y las aristas representan la composición de una de estas operaciones con una rotación o volteo adicional. [6]
