Přepínání červí díry - Wormhole switching - Wikipedia

Řízení toku červí díry, také zvaný přepínání červí díry nebo směrování červí díry, je systém jednoduchých řízení toku v počítačové sítě na základě známých pevných odkazů. Jedná se o podmnožinu metod řízení toku, která se nazývá Flit-Buffer Flow Control.[1]:Kapitola 13.2.1

Přepnutí je vhodnější termín než směrování, protože „směrování“ definuje trasu nebo cestu k dosažení cíle.[2][3] Technika červí díry nediktuje cestu k cíli, ale rozhoduje, kdy se paket posune vpřed ze směrovače.

Přepínání červí díry je široce používáno ve více počítačích kvůli jeho nízké latenci a malým požadavkům na uzly.[3]:376

Směrování červí díry velmi podporuje nízká latence, vysokorychlostní, garantovaná dodávka paketů vhodných pro komunikace v reálném čase.[4]

Princip mechanismu

V řízení toku červí díry je každý paket rozdělen na malé kousky, které se nazývají flits (jednotky řízení toku).

První flity, nazývané flitry v záhlaví, běžně obsahují informace o trase tohoto paketu (například cílová adresa) a nastavují chování směrování pro všechny následující flity spojené s paketem. Po záhlaví záhlaví následuje nula nebo více záhybů těla, které obsahují skutečné užitečné zatížení dat. Některé závěrečné záběry, nazývané záďové záběry, provádějí nějaké účetnictví, aby uzavřely spojení mezi dvěma uzly.

Při přepínání červí díry je každá vyrovnávací paměť buď nečinná, nebo přidělená jednomu paketu. Flit záhlaví lze předat do vyrovnávací paměti, pokud je tato vyrovnávací paměť nečinná. To přiděluje vyrovnávací paměť paketu. Tělo nebo přívěs může být předáno do vyrovnávací paměti, pokud je tato vyrovnávací paměť přidělena jeho paketu a není plná. Poslední flit uvolní vyrovnávací paměť. Pokud je flit záhlaví blokován v síti, vyrovnávací paměť se zaplní a jakmile je plná, nelze odesílat žádné další flity: tento efekt se nazývá „protitlak“ a lze jej šířit zpět ke zdroji.

Název „červí díra“ hraje na způsobu odesílání paketů přes odkazy: adresa je tak krátká, že ji lze přeložit před přijetím samotné zprávy. To umožňuje routeru rychle nastavit směrování skutečné zprávy a poté se „poklonit“ zbytku konverzace. Vzhledem k tomu, že je paket přenášen flitem po flitu, může na své cestě zabírat několik flitových vyrovnávacích pamětí a vytvářet tak obraz podobný červu.

Toto chování je docela podobné mezní přepínání,[5] běžně nazývaný „virtuální cut-through“, hlavní rozdíl spočívá v tom, že řízení toku cut-through přiděluje vyrovnávací paměti a šířku pásma kanálu na úrovni paketu, zatímco řízení toku červí díry to dělá na úrovni flit.

V případě kruhové závislosti může tento protitlak vést k zablokování.

Ve většině ohledů je červí díra velmi podobná bankomat nebo MPLS spedice, s tou výjimkou, že buňka nemusí být ve frontě.

Zvláštní věcí v řízení toku červí díry je implementace virtuálních kanálů:

Virtuální kanál obsahuje stav potřebný ke koordinaci zpracování pohybů paketu přes kanál. Minimálně tento stav identifikuje výstupní kanál aktuálního uzlu pro další směrování trasy a stav virtuálního kanálu (nečinný, čekající na zdroje nebo aktivní). Virtuální kanál může také obsahovat ukazatele na pohyby paketu, které jsou ukládány do vyrovnávací paměti na aktuálním uzlu, a počet vyrovnávacích pamětí k dispozici na dalším uzlu.[1]:237

Příklad

Animace přepínání červí díry se třemi toky.
Tři toky v síti 2x2 pomocí přepínání červí díry

Vezměme si síť 2x2 na obrázku vpravo, se 3 odesílanými pakety: růžový, vyrobený ze 4 flits, 'UVWX', z C do D; modrý, vyrobený ze 4 blits 'abcd', od A do F; a zelený, vyrobený ze 4 flits 'ijkl', od E po H. Předpokládáme, že směrování bylo vypočítáno, jak bylo nakresleno, a implikuje konflikt vyrovnávací paměti, v levém dolním routeru. Propustnost je jeden flit za časovou jednotku.

Nejprve zvažte růžový tok: v čase 1 je poslán flit 'U' do první vyrovnávací paměti; v čase 2 prochází flit 'U' další vyrovnávací pamětí (za předpokladu, že výpočet trasy netrvá dlouho) a flit 'V' je odeslán do první vyrovnávací paměti atd.

Modrý a zelený tok vyžaduje prezentaci krok za krokem:

  • Čas 1: Modrý i zelený tok posílají své první záblesky „i“ a „a“.
  • Čas 2: Flit 'i' může pokračovat do dalšího bufferu. Vyrovnávací paměť je ale vyhrazena pro paket od prvního do posledního flitu, takže flit „a“ nelze přeposlat. Toto je začátek a protitlak účinek. Flitr „j“ může nahradit flit „i“. Lze odeslat „b“ flit.
  • Čas 3: Zelený paket pokračuje. Modrý flit „c“ nelze přeposlat (vyrovnávací paměť je obsazena blity „b“ a „a“): tento efekt protitlaku dosáhne zdroje paketu.
  • Čas 4: Stejně jako v čase 3
  • Čas 5: Zelený paket již nepoužívá vyrovnávací paměť zleva dolů. Modrý paket je odblokován a lze jej přeposlat (za předpokladu, že „odblokované“ informace lze přeposlat v čase null)
  • Čas 6–10: Modrý paket prochází sítí.

Výhody

  • Řízení toku červí díry efektivněji využívá vyrovnávací paměti než průřez. Tam, kde cut-through vyžaduje mnoho paketů ve vyrovnávací paměti, vyžaduje metoda červí díry velmi málo flit buffers (srovnatelně).
  • Celý paket nemusí být ukládán do vyrovnávací paměti, aby se přesunul k dalšímu uzlu, zmenšuje se latence sítě ve srovnání s uložit a předat dál přepínání.
  • Šířka pásma a přidělení kanálu jsou odděleny

Používání

Techniky červí díry se používají hlavně v víceprocesorový systémy, zejména hyperkrychle. V počítači hypercube každý procesor je připojena k několika sousedům pevným vzorem, což snižuje počet přeskoků z jednoho CPU na druhý. Každému CPU je přiděleno číslo (obvykle pouze 8-bit na 16-bit ), což je jeho síťová adresa, a pakety do CPU jsou odesílány s tímto číslem v záhlaví. Když paket dorazí k mezilehlému směrovači pro předávání, směrovač prozkoumá záhlaví (velmi rychle), nastaví obvod k dalšímu směrovači a poté se pokloní konverzaci. Tím se znatelně snižuje latence (zpoždění) ve srovnání s uložit a předat dál přepínání, které čeká na celý paket před přeposláním. V poslední době si řízení toku červí díry našlo cestu k aplikacím v Síť na čipu systémy (NOC), z nichž vícejádrové procesory jsou jednou příchutí. Zde lze do sítě připojit více procesorových jader nebo na nižší úrovni dokonce i funkční jednotky IC balík. Jelikož se zpoždění drátu a mnoho dalších neškálovatelných omezení na propojených prvcích zpracování stávají dominantním faktorem designu, inženýři hledají zjednodušení organizovaných propojovacích sítí, ve kterých hrají důležitou roli metody řízení toku.

The IEEE 1355 a SpaceWire technologie využívají červí díru.

Virtuální kanály

Rozšíření řízení toku červí díry je Virtuální kanál řízení toku, kde může být multiplexováno několik virtuálních kanálů přes jeden fyzický kanál. Každý jednosměrný virtuální kanál je realizován nezávisle spravovanou dvojicí (flit) vyrovnávacích pamětí. Různé pakety pak mohou sdílet fyzický kanál po jednotlivých krocích. Virtuální kanály byly původně zavedeny, aby se zabránilo problému zablokování, ale lze je také použít ke snížení blokování červí díry, zlepšení latence a propustnosti sítě. Blokování červí díry nastane, když paket získá kanál, čímž zabrání jiným paketům v používání kanálu a nutí je zastavit se. Předpokládejme, že paket P0 získal kanál mezi dvěma směrovači. Při absenci virtuálních kanálů by byl paket P1 přicházející později blokován, dokud nebude dokončen přenos P0. Pokud jsou implementovány virtuální kanály, jsou možná následující vylepšení:

  • Po příchodu P1 může být mezi nimi fyzický kanál multiplexován na bázi flit-by-flit, takže oba pakety pokračují poloviční rychlostí (v závislosti na arbitrážním schématu).
  • Pokud P0 je paket plné délky, zatímco P1 je jen malý kontrolní paket o velikosti několika flitů, pak toto schéma umožňuje P1 projít oběma směrovači, zatímco P0 je na krátkou dobu zpomalen, což odpovídá přenosu několika paketů. To snižuje latenci pro P1.
  • Předpokládejme, že P0 je dočasně blokován po proudu od aktuálního routeru. Propustnost se zvyšuje tím, že P1 může pokračovat při plné rychlosti fyzického kanálu. Bez virtuálních kanálů by P0 obsadil kanál, aniž by skutečně využil dostupnou šířku pásma (protože je blokován).[6]

Použití virtuálních kanálů ke snížení blokování červí díry má mnoho podob s použitím virtuální výstupní fronta snížit head-of-line blokování.

Směrování

Ve stejném paketu přepínaném červí dírou lze použít kombinaci směrování zdroje a logického směrování. Hodnota prvního bajtu Myrinet nebo paket SpaceWire je adresa paketu SpaceWire přepínač použije adresu k rozhodnutí, jak směrovat paket.[7]

Směrování zdroje

Hlavní článek: směrování zdroje

Při směrování zdroje si odesílatel paketu vybere, jak je paket směrován přes přepínač.

Pokud je první bajt příchozího paketu SpaceWire v rozsahu 1 až 31, znamená to odpovídající port 1 až 31 přepínače Spacewire. Přepínač SpaceWire poté zahodí tento směrovací znak a odešle zbytek paketu z tohoto portu. vystaví další bajt původního paketu dalšímu přepínači SpaceWire. Odesílatel paketu se může rozhodnout použít směrování zdroje tímto způsobem explicitně specifikovat úplnou cestu přes síť k cílovému cíli.[7]

Logické směrování

S logickým směrováním samotný přepínač Spacewire rozhoduje o tom, jak směrovat paket.

Pokud je adresa (první bajt) příchozího paketu SpaceWire v rozmezí 32 až 255, přepínač SpaceWire použije tuto hodnotu jako index do interní směrovací tabulky, která označuje, které porty mají odeslat paket a zda mají být odstraněny nebo ponechat ten první bajt.[7]

Adresa 0 se používá pro přímou komunikaci s přepínačem a lze ji použít k nastavení položek směrovací tabulky pro tento přepínač.[7]

Viz také

Reference

  1. ^ A b William James Dally; Brian Towles (2004). „13.2.1“. Zásady a praxe propojovacích sítí. Morgan Kaufmann Publishers, Inc. ISBN  978-0-12-200751-4.
  2. ^ John L. Hennessy a David A. Patterson (2006). „Dodatek E.5“. Počítačová architektura: kvantitativní přístup (Čtvrté vydání). Morgan Kaufmann Publishers, Inc. ISBN  978-0-12-370490-0.
  3. ^ A b Mohapatra, Prasant (1998), „Techniky směrování červí díry pro přímo připojené systémy více počítačů“ (PDF), ACM Computing Surveys, 30 (3): 374–410, CiteSeerX  10.1.1.11.9098, doi:10.1145/292469.292472
  4. ^ Sharad Sundaresan; Riccardo Bettati.„Správa distribuovaného připojení pro komunikaci v reálném čase přes sítě červí díry“. 1997.
  5. ^ Stefan Haas. „Standard IEEE 1355: Vývoj, výkon a aplikace ve fyzice vysokých energií“. 1998. s. 59.
  6. ^ Pavel Tvrdík.„Proč je směrování červí díry důležitou přepínací technikou“
  7. ^ A b C d Dr. Barry M Cook; Paul Walker.„Ethernet over SpaceWire - problémy se softwarem“.2007.p. 2.