All-to-all (paralelní vzor) - All-to-all (parallel pattern) - Wikipedia

Vizualizace pro komunikaci typu all-to-all se čtyřmi procesory am = 1.

v paralelní výpočty, všichni na všechny (také známý jako operace indexu nebo celková výměna) je kolektivní provoz, kde každý procesor odesílá samostatnou zprávu každému dalšímu procesoru.

Zpočátku každý procesor drží p zprávy o velikosti m každý a cílem je vyměnit i-tou zprávu procesoru j s j-tou zprávou procesoru i.

Počet komunikačních kol a celkový objem komunikace jsou měřítkem k vyhodnocení kvality algoritmu typu „všichni na všechny“. V celém tomto článku považujeme plně portovaný stroj s jedním portem. Na takovém stroji vyžaduje algoritmus vše v každém přinejmenším ${ displaystyle lceil log _ {2} n rceil}$ komunikační kola. Dále minimálně ${ displaystyle left lceil { frac {m (n-1)} {k}} right rceil}$ jsou přeneseny jednotky dat. Optimální pro obě tato opatření nelze dosáhnout současně.^[1]

Záleží na topologie sítě (plně připojeno, hyperkrychle, prsten ), jsou vyžadovány různé all-to-all algoritmy.

All-to-all algoritmy založené na topologii

Vizualizace all-to-all algoritmu v kruhové topologii.

Vizualizace all-to-all algoritmu v topologii sítě.

Považujeme stroj s jedním portem. Způsob, jakým jsou data směrována po síti, závisí na podkladové topologii. Podíváme se na všechny algoritmy pro běžné topologie sítě.

Hypercube

A hyperkrychle je síťová topologie, kde dva procesory sdílejí spojení, pokud je Hammingova vzdálenost jejich společností jedna. Myšlenkou all-to-all algoritmu je kombinovat zprávy patřící do stejné dílčí krychle a poté je distribuovat.

Prsten

Algoritmus vše v jednom v a kruhová topologie je velmi intuitivní. Zpočátku procesor pošle zprávu o velikosti m (p-1) jednomu ze svých sousedů. Komunikace probíhá na všech procesorech stejným směrem. Když procesor přijme zprávu, extrahuje část, která mu patří, a předá zbytek zprávy dalšímu sousedovi. Po (p-1) komunikačních kolech je každá zpráva distribuována na místo určení.

Čas potřebný tímto algoritmem je ${ displaystyle (t_ {s} + { frac {1} {2}} t_ {w} mp) (p-1)}$ .^[2] Tady ${ displaystyle t_ {s}}$ je počáteční cena za komunikaci a ${ displaystyle t_ {w}}$ jsou náklady na přenos jednotky dat. Tento termín lze dále vylepšit, když je polovina zpráv odeslána v jedné a druhá polovina v opačném směru. Tímto způsobem zprávy dorazí dříve na místo určení.

Pletivo

Pro pletivo podíváme se na ${ displaystyle { sqrt {p}} krát { sqrt {p}}}$ pletivo. Tento algoritmus je snadno přizpůsobitelný pro jakoukoli síť. Algoritmus all-to-all v síti se skládá ze dvou komunikačních fází. Nejprve každý procesor seskupí zprávy do ${ displaystyle { sqrt {p}}}$ skupiny, z nichž každá obsahuje ${ displaystyle { sqrt {p}}}$ zprávy. Zprávy jsou ve stejné skupině, pokud jejich určené procesory sdílejí stejný řádek. Dále se provede operace typu „všichni na všechny“ mezi řádky. Každý procesor nyní ve svém sloupci uchovává všechny relevantní informace pro procesory. Zprávy je třeba znovu uspořádat. Po další operaci all-to-all, tentokrát s ohledem na sloupce, každý procesor končí se svými zprávami.

Celková doba komunikace pro tento algoritmus je ${ displaystyle (2t_ {s} + t_ {w} mp) ({ sqrt {p}} - 1)}$ . Kromě toho čas na místní přeskupení zpráv zvyšuje celkovou dobu běhu algoritmu.

1faktorový algoritmus

Vizualizace 1faktorového algoritmu.

Znovu považujeme stroj s jedním portem. Triviálním algoritmem je odesílání (p-1) asynchronních zpráv do sítě pro každý procesor. Výkon tohoto algoritmu je špatný, což je způsobeno zahlcením, které vzniká kvůli šířce půlící sítě.^[3] Sofistikovanější algoritmy kombinují zprávy, aby snížily počet operací odesílání a pokusily se řídit zahlcení.

U velkých zpráv jsou náklady na spuštění malé ve srovnání s náklady na přenos užitečného zatížení. Je rychlejší posílat zprávy přímo na místo určení. V následujícím algoritmu se provádí algoritmus typu „vše proti všem“ pomocí (p-1) individuálních rutin.

  // p odd: // pe index  ${ displaystyle j in {0, tečky, p-1 }}$   for i: = 0 to p-1 do Exchange data with PE  ${ displaystyle (i-j) , mod , p}$

  // p even: // pe index  ${ displaystyle j in {0, tečky, p-1 }}$   pro i: = 0 až p-2 nečinný: = ${ displaystyle { frac {p} {2}} i , mod , (p-1)}$    pokud j = p-1, pak si vyměňte data s nečinností PE, pokud j = nečinnost, pak si vyměňte data s pe p-1, jinak si vyměňte data s PE  ${ displaystyle (i-j) mod (p-1)}$

Algoritmus má jiné chování, ať už je p liché nebo sudé. V případě, že p je liché, je v každé iteraci jeden procesor nečinný. Pro sudé p tento nečinný procesor komunikuje s procesorem s indexem p-1. Celková doba je ${ displaystyle (p-1) (t_ {s} + t_ {w} m)}$ pro sudé p a ${ displaystyle p (t_ {s} + t_ {w} m)}$ pro liché p, resp.

Místo párování procesoru j s procesorem ${ displaystyle (i-j) { bmod {p}}}$ v iteraci i můžeme k určení mapování použít výlučné nebo nebo j a i. Tento přístup vyžaduje, aby p byla mocninou dvou. V závislosti na základní topologii sítě může být jeden přístup lepší než druhý. Výhradní přístup nebo přístup je lepší, když provádíte párování individuálních postupů v hyperkrychli nebo tlustém stromu.^[4]

Reference

^ Bruck, Jehoshua; Ho, Ching-Tien; Kipnis, Shlomo; Weathersby, Derrick (1997). „Efektivní algoritmy pro komunikaci typu all-to-all v systémech s více porty pro předávání zpráv“ (PDF). Transakce IEEE na paralelních a distribuovaných systémech. 8 (11): 1143–1156. doi:10.1109/71.642949.
^ Grama, Ananth (2003). Úvod do paralelních výpočtů.
^ Hambrusch, Susanne E .; Hameed, Farooq; Khokhar, Ashfaq A. (květen 1995). „Komunikační operace na hrubozrnných síťových architekturách“. Parallel Computing. 21 (5): 731–751. doi:10.1016 / 0167-8191 (94) 00110-V.
^ Thakur, Rajeev; Choudhary, Alok (26. – 29. Dubna 1994). All-to-All Communication on Meshes with Wormhole Routing. Sborník příspěvků z 8. mezinárodního sympozia o paralelním zpracování. Cancun, Mexiko.

[1] Bruck, Jehoshua; Ho, Ching-Tien; Kipnis, Shlomo; Weathersby, Derrick (1997). „Efektivní algoritmy pro komunikaci typu all-to-all v systémech s více porty pro předávání zpráv“ (PDF). Transakce IEEE na paralelních a distribuovaných systémech. 8 (11): 1143–1156. doi:10.1109/71.642949.

[2] Grama, Ananth (2003). Úvod do paralelních výpočtů.

[3] Hambrusch, Susanne E .; Hameed, Farooq; Khokhar, Ashfaq A. (květen 1995). „Komunikační operace na hrubozrnných síťových architekturách“. Parallel Computing. 21 (5): 731–751. doi:10.1016 / 0167-8191 (94) 00110-V.

[4] Thakur, Rajeev; Choudhary, Alok (26. – 29. Dubna 1994). All-to-All Communication on Meshes with Wormhole Routing. Sborník příspěvků z 8. mezinárodního sympozia o paralelním zpracování. Cancun, Mexiko.

[1]

[2]

[3]

[4]