Projektowanie sieci połączeń międzysystemowych
Na interconnection networkw maszynie równoległej przesyła informacje z dowolnego węzła źródłowego do dowolnego pożądanego węzła docelowego. To zadanie powinno być wykonane z jak najmniejszym opóźnieniem. Powinno to pozwolić na równoczesne dokonywanie dużej liczby takich transferów. Co więcej, powinno być niedrogie w porównaniu z kosztem reszty maszyny.
Sieć składa się z łączy i przełączników, które pomagają przesyłać informacje z węzła źródłowego do węzła docelowego. Sieć jest określana na podstawie jej topologii, algorytmu routingu, strategii przełączania i mechanizmu kontroli przepływu.
Struktura organizacyjna
Sieci połączeń składają się z trzech podstawowych elementów -
Links- Łącze to kabel składający się z co najmniej jednego włókna światłowodowego lub przewodu elektrycznego ze złączami na każdym końcu podłączonymi do przełącznika lub portu interfejsu sieciowego. Dzięki temu sygnał analogowy jest przesyłany z jednego końca, a odbierany z drugiego w celu uzyskania oryginalnego cyfrowego strumienia informacji.
Switches- Przełącznik składa się z zestawu portów wejściowych i wyjściowych, wewnętrznej „poprzeczki” łączącej wszystkie wejścia ze wszystkimi wyjściami, wewnętrznego buforowania i logiki sterującej, która zapewnia połączenie wejścia-wyjścia w każdym momencie. Ogólnie liczba portów wejściowych jest równa liczbie portów wyjściowych.
Network Interfaces- Interfejs sieciowy zachowuje się zupełnie inaczej niż węzły przełączające i może być połączony za pomocą specjalnych łączy. Interfejs sieciowy formatuje pakiety i konstruuje informacje o routingu i sterowaniu. W porównaniu z przełącznikiem może mieć buforowanie wejścia i wyjścia. Może wykonywać kompleksowe sprawdzanie błędów i kontrolę przepływu. W związku z tym na jego koszt wpływa złożoność przetwarzania, pojemność pamięci masowej i liczba portów.
Sieć połączeń
Sieci połączeń składają się z elementów przełączających. Topologia to wzorzec łączenia poszczególnych przełączników z innymi elementami, takimi jak procesory, pamięci i inne przełączniki. Sieć umożliwia wymianę danych między procesorami w systemie równoległym.
Direct connection networks- Sieci bezpośrednie mają połączenia typu punkt-punkt między sąsiednimi węzłami. Sieci te są statyczne, co oznacza, że połączenia typu punkt-punkt są stałe. Niektóre przykłady sieci bezpośrednich to pierścienie, oczka i kostki.
Indirect connection networks- Sieci pośrednie nie mają stałych sąsiadów. Topologię komunikacji można zmieniać dynamicznie w zależności od wymagań aplikacji. Sieci pośrednie można podzielić na trzy części: sieci magistralne, sieci wielostopniowe i przełączniki poprzeczne.
Bus networks- Sieć magistrali składa się z szeregu linii bitowych, do których dołączonych jest wiele zasobów. Gdy magistrale używają tych samych linii fizycznych dla danych i adresów, linie danych i adresów są multipleksowane czasowo. Gdy do magistrali jest podłączonych wiele urządzeń nadrzędnych magistrali, potrzebny jest arbiter.
Multistage networks- Sieć wielostopniowa składa się z wielu stopni przełączników. Składa się z przełączników „axb”, które są połączone za pomocą określonego schematu połączeń międzystopniowych (ISC). Małe elementy przełączające 2x2 są powszechnym wyborem w wielu sieciach wielostopniowych. Liczba etapów określa opóźnienie sieci. Wybierając różne wzorce połączeń międzystopniowych, można tworzyć różne typy sieci wielostopniowych.
Crossbar switches- Przełącznik poprzeczny zawiera macierz prostych elementów przełącznika, które można włączać i wyłączać w celu utworzenia lub przerwania połączenia. Włączając element przełączający w matrycy, można wykonać połączenie między procesorem a pamięcią. Przełączniki poprzeczne nie blokują się, to znaczy wszystkie permutacje komunikacji mogą być wykonywane bez blokowania.
Ocena kompromisów projektowych w topologii sieci
Jeśli głównym problemem jest odległość trasowania, to wymiar musi zostać zmaksymalizowany i wykonać hipersześcian. W przypadku routingu typu store and forward, przy założeniu, że stopień przełączenia i liczba łączy nie stanowiły istotnego czynnika kosztowego, a liczba łączy lub stopień przełącznika są głównymi kosztami, wymiar należy zminimalizować, a siatka wybudowany.
W najgorszym przypadku wzorzec ruchu dla każdej sieci, preferowane są sieci wielowymiarowe, w których wszystkie ścieżki są krótkie. We wzorcach, w których każdy węzeł komunikuje się tylko z jednym lub dwoma pobliskimi sąsiadami, preferowane jest posiadanie sieci niskowymiarowych, ponieważ w rzeczywistości używanych jest tylko kilka wymiarów.
Wytyczanie
Algorytm routingu sieci określa, która z możliwych ścieżek od źródła do miejsca przeznaczenia jest używana jako trasy oraz w jaki sposób jest określana trasa, po której następuje każdy pakiet. Routing według kolejności wymiarów ogranicza zestaw dozwolonych ścieżek, dzięki czemu istnieje dokładnie jedna trasa z każdego źródła do każdego miejsca docelowego. Ten uzyskany przez pokonanie najpierw odpowiedniej odległości w wymiarze wyższego rzędu, następnie w następnym wymiarze i tak dalej.
Mechanizmy routingu
Arytmetyka, wybór portu na podstawie źródła i przeglądanie tabeli to trzy mechanizmy, których szybkie przełączniki używają do określania kanału wyjściowego na podstawie informacji w nagłówku pakietu. Wszystkie te mechanizmy są prostsze niż rodzaj ogólnych obliczeń routingu stosowanych w tradycyjnych routerach sieci LAN i WAN. W równoległych sieciach komputerowych przełącznik musi podejmować decyzję o routingu dla wszystkich swoich wejść w każdym cyklu, więc mechanizm musi być prosty i szybki.
Deterministyczny routing
Algorytm routingu jest deterministyczny, jeśli trasa obrana przez komunikat jest określana wyłącznie przez jego źródło i miejsce docelowe, a nie przez inny ruch w sieci. Jeśli algorytm routingu wybiera tylko najkrótsze ścieżki do miejsca docelowego, jest on minimalny, w przeciwnym razie nie jest minimalny.
Zakleszczenie wolności
W różnych sytuacjach może wystąpić impas. Gdy dwa węzły próbują wysłać do siebie dane i każdy z nich rozpoczyna wysyłanie, zanim którykolwiek z nich odbierze, może dojść do impasu „czołowego”. Inny przypadek zakleszczenia występuje, gdy istnieje wiele wiadomości konkurujących o zasoby w sieci.
Podstawową techniką udowodnienia, że sieć jest wolna od zakleszczeń, jest usunięcie zależności, które mogą wystąpić między kanałami w wyniku komunikatów przepływających przez sieci, i pokazanie, że nie ma cykli na ogólnym wykresie zależności kanału; stąd nie ma wzorców ruchu, które mogłyby prowadzić do impasu. Powszechnym sposobem wykonywania tego jest numerowanie zasobów kanału w taki sposób, aby wszystkie trasy przebiegały według określonej sekwencji rosnącej lub malejącej, tak że nie pojawiają się cykle zależności.
Projekt przełącznika
Projekt sieci zależy od projektu przełącznika i sposobu połączenia przełączników. Stopień przełącznika, jego wewnętrzne mechanizmy routingu i wewnętrzne buforowanie decydują o tym, jakie topologie mogą być obsługiwane i jakie algorytmy routingu można zaimplementować. Jak każdy inny element sprzętowy systemu komputerowego, przełącznik sieciowy zawiera ścieżkę danych, sterowanie i pamięć.
Porty
Całkowita liczba pinów to w rzeczywistości całkowita liczba portów wejściowych i wyjściowych pomnożona przez szerokość kanału. Ponieważ obwód chipa rośnie powoli w porównaniu z obszarem, przełączniki są zwykle ograniczone pinami.
Wewnętrzna ścieżka danych
Ścieżka danych to łączność między każdym zestawem portów wejściowych i każdym portem wyjściowym. Nazywa się go ogólnie poprzeczką wewnętrzną. Nieblokująca poprzeczka to taka, w której każdy port wejściowy może być podłączony do odrębnego wyjścia w dowolnej permutacji jednocześnie.
Bufory kanałów
Organizacja pamięci buforowej w przełączniku ma istotny wpływ na wydajność przełącznika. Tradycyjne routery i przełączniki mają zwykle duże bufory SRAM lub DRAM poza strukturą przełącznika, podczas gdy w przełącznikach VLSI buforowanie jest wewnętrzne dla przełącznika i pochodzi z tego samego budżetu krzemowego, co ścieżka danych i sekcja sterowania. Wraz ze wzrostem rozmiaru i gęstości chipa dostępnych jest więcej buforowania, a projektant sieci ma więcej opcji, ale nadal najważniejszym wyborem jest bufor nieruchomości, a jego organizacja jest ważna.
Kontrola przepływu
Gdy wiele przepływów danych w sieci próbuje jednocześnie korzystać z tych samych współdzielonych zasobów sieciowych, należy podjąć pewne działania, aby kontrolować te przepływy. Jeśli nie chcemy stracić żadnych danych, niektóre przepływy muszą zostać zablokowane, podczas gdy inne kontynuują.
Problem kontroli przepływu pojawia się we wszystkich sieciach i na wielu poziomach. Ale jakościowo różni się w równoległych sieciach komputerowych niż w sieciach lokalnych i rozległych. W komputerach równoległych ruch sieciowy musi być dostarczany mniej więcej tak dokładnie, jak ruch przez magistralę, a istnieje bardzo duża liczba równoległych przepływów w bardzo małej skali czasu.