Red de intercambio aleatorio

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 cuyas aristas representan dos operaciones sobre estas secuencias: desplazamientos circulares e 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 de mezcla de orden${\displaystyle d}$consistía en una variedad de${\displaystyle 2^{d}}$celdas, numeradas por el${\displaystyle 2^{d}}$diferentes números binarios que se pueden representar con${\displaystyle d}$bits. Estas celdas estaban conectadas por enlaces de comunicación en dos patrones diferentes: enlaces de "intercambio", en los que cada celda se conecta a la celda numerada con el valor opuesto en su bit de orden más bajo, y enlaces de "mezcla", en los que cada celda se conecta a la celda cuyo número se obtiene mediante 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 "mezcla" solo pueden transferir información en una dirección, de una celda a su desplazamiento circular. ^{[ 2 ]}

Trabajos posteriores sobre redes con esta topología eliminaron la distinción entre enlaces de comunicación unidireccionales y bidireccionales, permitiendo que la información fluyera en cualquier dirección a través de cada enlace. ^{[ 1 ] [ 4 ]}

La ventaja de este patrón de comunicación, 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 de la red a cualquier otro vértice, requiriendo solo un bit de información de control (cuál de los dos enlaces de comunicación utilizar) para cada paso de comunicación. ^{[ 2 ]} Se conocen algoritmos paralelos rápidos para problemas básicos como la ordenación , la multiplicación de matrices , la evaluación de polinomios y las transformadas de Fourier para sistemas paralelos que utilizan esta red. ^{[ 4 ]}

Si a esta red se le da una disposición sencilla 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, la disposición utiliza área${\displaystyle O(2^{2d})}$cuadrática en su número de vértices. Sin embargo, diseños más compactos y asintóticamente óptimos con área${\displaystyle O(2^{2d}/d^{2})}$fueron descritas por F. Thomson Leighton en su tesis doctoral de 1981. ^{[ 4 ]}

Una red de comunicaciones relacionada, la "red omega" o red de intercambio de mezcla multietapa , consta de un número determinado de etapas, cada una de las cuales consta de:${\displaystyle 2^{d}}$vértices, con los enlaces de mezcla que conectan pares de vértices en etapas consecutivas y los enlaces de intercambio que conectan pares de vértices en la misma etapa entre sí. ^{[ 5 ]}

Las mismas operaciones sobre palabras binarias, de rotación e inversión del primer bit, también pueden utilizarse para generar los ciclos conectados por cubo , una red de comunicaciones paralela cúbica diferente con un mayor número de vértices. En lugar de tener las propias palabras binarias como vértices, los vértices de los ciclos conectados por cubo representan operaciones sobre palabras que pueden generarse mediante rotación e inversión, y las aristas representan la composición de una de estas operaciones con una rotación o inversión adicional. ^{[ 6 ]}