Wielostopniowe sieci połączeń

Wielostopniowe sieci połączeń ( MIN ) to klasa szybkich sieci komputerowych , które zwykle składają się z elementów przetwarzających (PE) na jednym końcu sieci i elementów pamięci (ME) na drugim końcu, połączonych elementami przełączającymi (SE). Same elementy przełączające są zwykle połączone ze sobą etapami, stąd nazwa.

MIN są zwykle używane w obliczeniach o wysokiej wydajności lub równoległych jako połączenia międzysieciowe o niskim opóźnieniu (w przeciwieństwie do tradycyjnych sieci z komutacją pakietów ), chociaż można je zaimplementować na szczycie sieci z komutacją pakietów. Chociaż sieć jest zwykle używana do celów routingu, może być również używana jako koprocesor rzeczywistych procesorów do takich zastosowań, jak sortowanie ; cykliczne przesuwanie , jak w idealnej sieci losowej ; i sortowanie bitoniczne .

Tło

Sieci połączeń międzysieciowych służą do łączenia węzłów, gdzie węzły mogą być pojedynczym procesorem lub grupą procesorów, z innymi węzłami.

Sieci połączeń międzysieciowych można podzielić na kategorie na podstawie ich topologii. Topologia to wzór, w którym jeden węzeł jest połączony z innymi węzłami.

Istnieją dwa główne typy topologii: statyczna i dynamiczna.

Statyczne sieci międzysieciowe są zbudowane na stałe i nie mogą zmieniać swojej konfiguracji. Zwykły interkonekt statyczny jest używany głównie w małych sieciach składających się z luźno powiązanych węzłów. Regularna struktura oznacza, że ​​węzły są ułożone w określony kształt, a kształt jest utrzymywany w całej sieci.

Niektóre przykłady statycznych regularnych połączeń to:

• Całkowicie połączona sieć
  

  Całkowicie połączona sieć
  W sieci kratowej wiele węzłów jest ze sobą połączonych. Każdy węzeł w sieci jest połączony z każdym innym węzłem w sieci. Taki układ umożliwia prawidłową komunikację danych między węzłami. Istnieje jednak wiele ogólnych kosztów komunikacji ze względu na zwiększoną liczbę połączeń węzłowych.
• Wspólny autobus
  

  Wspólna sieć autobusowa
  Ta topologia sieci polega na łączeniu węzłów ze sobą za pośrednictwem magistrali. Każdy węzeł komunikuje się z każdym innym węzłem za pomocą magistrali. Narzędzie magistrali gwarantuje, że żadne dane nie zostaną wysłane do niewłaściwego węzła. Ale ruch autobusowy jest ważnym parametrem, który może wpływać na system.
• Pierścień
  

  Sieć pierścieniowa
  Jest to jeden z najprostszych sposobów łączenia ze sobą węzłów. Węzły są ze sobą połączone, tworząc pierścień. Aby węzeł mógł komunikować się z innym węzłem, musi wysyłać wiadomości do swojego sąsiada. Dlatego wiadomość z danymi przechodzi przez szereg innych węzłów, zanim dotrze do miejsca docelowego. Wiąże się to ze zwiększonym opóźnieniem w systemie.
• Drzewo
  

  Sieć drzew
  Ta topologia obejmuje łączenie węzłów w celu utworzenia drzewa. Węzły są połączone, tworząc klastry, a klastry są z kolei połączone, tworząc drzewo. Ta metodologia powoduje zwiększoną złożoność w sieci.
• hipersześcian
  

  4*4 hipersześcian
  Ta topologia składa się z połączeń węzłów w celu utworzenia sześcianów. Węzły są również połączone z węzłami na innych kostkach.
• Motyl
  

  Sieć motyli
  Jest to jedno z najbardziej złożonych połączeń węzłów. Jak sugeruje rysunek, istnieją węzły, które są połączone i rozmieszczone pod względem ich rang. Ułożone są one w formie matrycy.

W dynamicznych sieciach wzajemnych węzły są połączone za pomocą szeregu prostych elementów przełączających. To wzajemne połączenie można następnie zmienić za pomocą algorytmów trasowania, tak aby można było zmieniać ścieżkę z jednego węzła do innych węzłów. Połączenia dynamiczne można podzielić na:

• Jednostopniowa sieć połączeń
• Wielostopniowa sieć połączeń
• Połączenia przełączników poprzecznych

Połączenia przełącznika poprzecznego

W przełączniku krzyżowym istnieje dedykowana ścieżka z jednego procesora do innych procesorów. Tak więc, jeśli jest n wejść i m wyjść, będziemy potrzebować n*m przełączników, aby zrealizować poprzeczkę.

Wraz ze wzrostem liczby wyjść liczba przełączników wzrasta o współczynnik n. W przypadku dużej sieci będzie to problem.

Sieć poprzeczna

Alternatywą dla tego schematu jest przełączanie etapowe.

Jednostopniowa sieć połączeń międzysieciowych

W jednostopniowej sieci połączeń węzły wejściowe są połączone z wyjściem za pośrednictwem jednego stopnia przełączników.

Rysunek przedstawia jednostopniowy przełącznik 8*8 z wymianą losową .

Sieć jednostopniowa 8x8

Jak widać, z pojedynczego przetasowania nie wszystkie dane wejściowe mogą dotrzeć do wszystkich danych wyjściowych. Wymagane jest wielokrotne przetasowanie, aby wszystkie wejścia zostały połączone ze wszystkimi wyjściami.

Wielostopniowa sieć połączeń

Wielostopniowa sieć połączeń jest tworzona przez kaskadowanie wielu jednostopniowych przełączników. Przełączniki mogą następnie korzystać z własnego algorytmu routingu lub być kontrolowane przez scentralizowany router, tworząc w pełni połączoną sieć.

Wielostopniową sieć połączeń międzysieciowych można podzielić na trzy typy:

1. Nieblokowanie: Sieć nieblokująca może łączyć dowolne nieaktywne wejście z dowolnym nieaktywnym wyjściem, niezależnie od połączeń już ustanowionych w sieci. Przykładem tego typu sieci jest Crossbar.
2. Rearanżacja bez blokowania: Ten typ sieci może ustanowić wszystkie możliwe połączenia między wejściami i wyjściami poprzez zmianę kolejności istniejących połączeń.
3. Blokowanie: Ten typ sieci nie może realizować wszystkich możliwych połączeń między wejściami i wyjściami. Dzieje się tak dlatego, że połączenie między jednym wolnym wejściem a drugim wolnym wyjściem jest blokowane przez istniejące połączenie w sieci.

Najwyższa liczba elementów przełączających wymaganych do realizacji sieci nieblokującej, a następnie nieblokująca z możliwością przestawiania. Sieć blokująca wykorzystuje najmniej elementów przełączających.

Przykłady

Istnieje wiele rodzajów wielostopniowych sieci połączeń.

Sieć Omegi

Główny artykuł: sieć Omega

Sieć Omega z 8 elementami przetwarzającymi

Sieć Omega składa się z wielu etapów 2*2 elementów przełączających. Każde wejście ma dedykowane połączenie z wyjściem. Sieć omega N*N ma liczbę log(N) stopni i liczbę N/2 elementów przełączających na każdym etapie, co zapewnia idealne przetasowanie między etapami. Zatem sieć ma złożoność równą 0(N log(N)). Każdy element przełączający może wykorzystywać własny algorytm przełączania. Rozważ sieć omega 8*8. Jest 8! = 40320 odwzorowań 1-do-1 z wejścia na wyjście. Istnieje 12 elementów przełączających dla całkowitej permutacji 2^12 = 4096. Jest to zatem sieć blokująca.

Sieć Clos

Główny artykuł: sieć Clos

Sieć Clos

Sieć Clos wykorzystuje 3 etapy do przełączania z N wejść na N wyjść. W pierwszym etapie są r= N/n przełączników poprzecznych, a każdy przełącznik ma rozmiar n*m. W drugim etapie znajduje się m przełączników o rozmiarze r*r, aw końcu ostatni stopień jest lustrzanym odbiciem pierwszego stopnia z r przełącznikami o rozmiarze m*n. Sieć zamknięta będzie całkowicie nieblokująca, jeśli m >= 2n-1. Liczba połączeń, choć większa niż w sieci omega, jest znacznie mniejsza niż w przypadku sieci typu crossbar.

Sieć Benesza

Sieć Benes

Sieć Beneša jest siecią nieblokującą z możliwością przestawiania, wywodzącą się z sieci clos przez inicjalizację n = m = 2. Istnieje (2log(N) - 1) etapów, z których każdy zawiera N/2 2*2 przełączników poprzecznych. Sieć Beneša 8*8 ma 5 stopni elementów przełączających, a każdy stopień ma 4 elementy przełączające. Środkowe trzy sceny mają dwie sieci benes 4 * 4. Sieć 4*4 Beneša może rekurencyjnie łączyć dowolne wejście z dowolnym wyjściem.