Sieć wymiany losowej

Sieć wymiany losowej rzędu 4, z wierzchołkami ułożonymi w porządku numerycznym

W teorii grafów sieć wymiany losowej jest nieskierowanym multigrafem sześciennym , którego wierzchołki reprezentują sekwencje binarne o danej długości, a krawędzie reprezentują dwie operacje na tych sekwencjach, przesunięcia kołowe i odwrócenie bitu najniższego rzędu.

Definicja

$displaystyle$ Tomasa Langa i Harolda S. Stone'a w 1976 r., Upraszczającej wcześniejsze prace Stone'a w 1971 r., uporządkowana sieć wymiany losowej składała się z tablicy $2} ^ {d}}$$\ displaystyle d}$ , ponumerowane przez różne liczby binarne , które można przedstawić za pomocą ${$ bity. Komórki te były połączone łączami komunikacyjnymi w dwóch różnych wzorach: łącza „wymiany”, w których każda komórka jest połączona z komórką o przeciwnej wartości w bicie najniższego rzędu, oraz łącza „przemieszane”, w których każda komórka jest połączona z komórka, której numer jest uzyskiwany przez przesunięcie kołowe , które przesuwa każdy bit do następnej bardziej znaczącej pozycji, z wyjątkiem bitu najwyższego rzędu, który przesuwa się do pozycji najniższego rzędu. Łącza „wymiany” są dwukierunkowe, podczas gdy łącza „tasowania” mogą przesyłać informacje tylko w jednym kierunku, od komórki do jej przesunięcia kołowego.

Późniejsze prace nad sieciami o tej topologii usunęły rozróżnienie między jednokierunkowymi i dwukierunkowymi łączami komunikacyjnymi, umożliwiając przepływ informacji w dowolnym kierunku przez każde łącze.

Aplikacje

Zaletą tego wzorca komunikacji w porównaniu z wcześniejszymi metodami jest to, że umożliwia on szybkie przesyłanie informacji w niewielkiej liczbie kroków z dowolnego wierzchołka w sieci do dowolnego innego wierzchołka, wymagając przy tym tylko jednego bitu informacji sterującej (który z dwa łącza komunikacyjne do użycia) dla każdego etapu komunikacji. Szybkie algorytmy równoległe dla podstawowych problemów, w tym sortowania , mnożenia macierzy , obliczania wielomianów i transformat Fouriera, są znane dla systemów równoległych wykorzystujących tę sieć.

Obszar układu

Jeśli ta sieć ma prosty układ w siatce całkowitej , z wierzchołkami umieszczonymi na linii w porządku numerycznym, z każdą krawędzią sieci przenoszącą część co najwyżej jednego łącza komunikacyjnego i z każdym wierzchołkiem lub skrzyżowaniem sieci umieszczonym w sieci $punkt$ , układ wykorzystuje liczby Jednak bardziej zwarte i asymptotycznie optymalne układy z obszarem ${\ Displaystyle O (2 ^ {2d} / d ^ {2})}$ zostały opisane przez F. Thomsona Leightona w jego rozprawie doktorskiej z 1981 roku.

Powiązane sieci

Powiązana sieć komunikacyjna, „sieć omega” lub wieloetapowa sieć wymiany losowej, składa się z określonej liczby etapów, z których każdy składa się z $2$ z łączami losowymi łączącymi pary wierzchołki w kolejnych etapach i wymieniają się linkami łączącymi pary wierzchołków w tym samym etapie.

Te same operacje na słowach binarnych, obracanie i odwracanie pierwszego bitu, mogą być również użyte do generowania cykli połączonych sześcianami , innej sześciennej równoległej sieci komunikacyjnej z większą liczbą wierzchołków. Zamiast samych słów binarnych jako wierzchołków, wierzchołki cykli połączonych sześcianami reprezentują operacje na słowach, które można wygenerować przez obracanie i odwracanie, a krawędzie reprezentują kompozycję jednej z tych operacji z dodatkowym obrotem lub odwróceniem.