Vícestupňové propojovací sítě - Multistage interconnection networks

Vícestupňové propojovací sítě (MIN) jsou třídou vysokorychlostních počítačové sítě obvykle se skládá z zpracovává se prvky (PE) na jednom konci sítě a Paměť prvky (ME) na druhém konci, spojené pomocí přepínání prvky (SE). Samotné spínací prvky jsou obvykle navzájem spojeny v několika fázích, odtud název.

MIN se obvykle používají ve vysoce výkonných nebo paralelních počítačích jakolatence propojení (na rozdíl od tradičního přepínání paketů sítě), i když by mohly být implementovány přes síť pro přepojování paketů. Ačkoli se síť obvykle používá pro účely směrování, mohla by být také použita jako koprocesor pro skutečné procesory pro takové účely, jako je třídění; cyklické řazení, jako v a perfektní shuffle síť; a bitonické třídění.

Pozadí

Propojovací síť se používá k připojení uzlů, kde uzly mohou být jeden procesor nebo skupina procesorů, k dalším uzlům.

Propojovací sítě lze kategorizovat na základě jejich topologie. Topologie je vzor, ​​ve kterém je jeden uzel připojen k jiným uzlům.

Existují dva hlavní typy topologie: statická a dynamická.

Statické propojovací sítě jsou pevně propojené a nemohou měnit své konfigurace. Pravidelné statické propojení se používá hlavně v malých sítích tvořených volně párovanými uzly. Pravidelná struktura znamená, že uzly jsou uspořádány do konkrétního tvaru a tvar je udržován v sítích.

Některé příklady pravidelných statických propojení jsou:[1]

  • Zcela připojená síť
    Zcela připojená síť
    V síťové síti je více uzlů vzájemně propojeno. Každý uzel v síti je připojen ke každému dalšímu uzlu v síti. Toto uspořádání umožňuje správnou komunikaci dat mezi uzly. Existuje však spousta režijních nákladů komunikace kvůli zvýšenému počtu připojení uzlů.
  • Sdílený autobus
    Síť sdílené sběrnice
    Tato topologie sítě zahrnuje vzájemné propojení uzlů po sběrnici. Každý uzel komunikuje se všemi ostatními uzly pomocí sběrnice. Obslužný program sběrnice zajišťuje, že žádná data nebudou odeslána do nesprávného uzlu. Provoz na sběrnici je ale důležitým parametrem, který může ovlivnit systém.
  • Prsten
    Ring Network
    Toto je jeden z nejjednodušších způsobů vzájemného propojení uzlů. Uzly jsou navzájem spojeny a tvoří kruh. Aby uzel mohl komunikovat s jiným uzlem, musí posílat zprávy svému sousedovi. Proto datová zpráva prochází řadou dalších uzlů před dosažením cíle. To zahrnuje zvýšenou latenci v systému.
  • Strom
    Síť stromů
    Tato topologie zahrnuje připojení uzlů k vytvoření stromu. Uzly jsou připojeny k vytvoření klastrů a klastry jsou zase připojeny k vytvoření stromu. Tato metodika způsobuje zvýšenou složitost v síti.
  • Hypercube
    4 * 4 Hypercube
    Tato topologie se skládá z připojení uzlů k vytvoření kostek. Uzly jsou také spojeny s uzly na ostatních kostkách.
  • Motýl
    Síť motýlů
    Toto je jedno z nejsložitějších spojení uzlů. Jak naznačuje obrázek, existují uzly, které jsou spojeny a uspořádány podle jejich řad. Jsou uspořádány ve formě matice.

V dynamických propojovacích sítích jsou uzly propojeny prostřednictvím řady jednoduchých spínacích prvků.[2] Toto propojení lze poté změnit pomocí směrovacích algoritmů, takže lze měnit cestu z jednoho uzlu do dalších uzlů. Dynamická propojení lze klasifikovat jako:

  • Jednostupňová propojovací síť
  • Vícestupňová propojovací síť
  • Připojení příčného spínače

Připojení přepínače příčníku

V příčném přepínači existuje vyhrazená cesta z jednoho procesoru do jiných procesorů. Pokud tedy existuje n vstupů a m výstupů, budeme potřebovat n * m přepínačů k realizaci příčníku.

Jak se zvyšuje počet výstupů, zvyšuje se počet přepínačů o faktor n. Pro velkou síť to bude problém.

Síť příčníku

Alternativou k tomuto schématu je postupné přepínání.

Jednostupňová propojovací síť

V jednostupňové propojovací síti jsou vstupní uzly připojeny k výstupu prostřednictvím jediného stupně přepínačů.

Obrázek ukazuje použití 8 * 8 jednostupňového přepínače náhodná výměna.

Jednostupňová síť 8x8

Jak je vidět, z jediného náhodného míchání ne všechny vstupy mohou dosáhnout všech výstupů. Pro všechny vstupy, které mají být připojeny ke všem výstupům, je zapotřebí několik náhodných kroků.

Vícestupňová propojovací síť

Vícestupňová propojovací síť je tvořena kaskádováním více jednostupňových přepínačů. Přepínače pak mohou použít svůj vlastní směrovací algoritmus nebo je ovládat centralizovaným směrovačem a vytvořit tak zcela propojenou síť.

Vícestupňovou propojovací síť lze rozdělit do tří typů:[3]

  1. Neblokující: Neblokující síť může připojit jakýkoli vstup nečinnosti k jakémukoli výstupu nečinnosti, bez ohledu na připojení, která již byla v síti vytvořena. Příkladem tohoto typu sítě je příčka.
  2. Přeskupitelné neblokující: Tento typ sítě může navázat všechna možná spojení mezi vstupy a výstupy přeskupením svých stávajících připojení.
  3. Blokování: Tento typ sítě nemůže realizovat všechna možná spojení mezi vstupy a výstupy. Důvodem je, že spojení mezi jedním volným vstupem do jiného volného výstupu je blokováno existujícím připojením v síti.

Počet spínacích prvků potřebných k realizaci neblokující sítě na nejvyšší úrovni, následovaný přeskupitelným neblokováním. Blokovací síť používá nejméně spínacích prvků.

Příklady

Existuje několik typů vícestupňových propojovacích sítí.

Síť Omega

Hlavní článek: Síť Omega
Síť Omega

Síť Omega se skládá z několika stupňů 2 * 2 spínacích prvků. Každý vstup má vyhrazené připojení k výstupu. Síť N * N omega má log (N) počet stupňů a N / 2 počet spínacích prvků v každém stupni pro dokonalé zamíchání mezi stupni. Síť má tedy složitost 0 (N log (N)). Každý spínací prvek může využívat svůj vlastní spínací algoritmus. Zvažte 8 * 8 omega síť. Je jich 8! = 40320 mapování 1: 1 ze vstupu na výstup. Existuje 12 spínacích prvků pro celkovou permutaci 2 ^ 12 = 4096. Jedná se tedy o blokovací síť.

Clos síť

Hlavní článek: Clos síť
Clos síť

Síť Clos používá 3 stupně k přepínání z N vstupů na N výstupů. V první fázi jsou příčné spínače r = N / n a každý přepínač má velikost n * m. Ve druhém stupni jsou m přepínače velikosti r * r a nakonec poslední stupeň je zrcadlem prvního stupně s r přepínači velikosti m * n. Uzavřená síť bude zcela neblokující, pokud m> = 2n-1. Počet připojení, i když více než síť omega, je mnohem menší než u příčné sítě.

Benešova síť

Benešova síť

Síť Beneš je přeskupitelně neblokující síť odvozená od uzavírací sítě inicializací n = m = 2. Existují (2log (N) - 1) stupně, přičemž každý stupeň obsahuje N / 2 2 * 2 příčné spínače. Síť Beneš 8 * 8 má 5 stupňů spínacích prvků a každý stupeň má 4 spínací prvky. Centrum tři etapy má dvě sítě 4 * 4 Benes. Síť Beneš 4 * 4 může rekurzivně připojit jakýkoli vstup k jakémukoli výstupu.

Reference

  1. ^ Solihin, Yan (2009). Základy paralelní počítačové architektury. USA: OmniPress. ISBN  978-0-9841630-0-7.
  2. ^ Blake, J. T .; Trivedi, K. S. (1989-11-01). "Vícestupňová spolehlivost propojovací sítě". Transakce IEEE na počítačích. 38 (11): 1600–1604. doi:10.1109/12.42134. ISSN  0018-9340.
  3. ^ „Vícestupňové propojovací sítě“ (PDF).

Zdroje