IB109 Návrh a implementace paralelních systémů Kolektivní komunikační primitiva Jiří Barnat Kvantitativní parametry komunikace Komunikace (interakce) Předávání informací mezi jednotlivými procesy Parametry komunikace Latence — zpoždění související se započetím vlastní komunikace Šířka pásma (bandwidth) — maximální množství dat přenesených za jednotku času Objem — množství předávaných dat Cena komunikace ts – latence, tw – šířka pásma, m – objem ts + m ∗ tw IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 2/55 Kvantitativní parametry komunikace Příklady Za jak dlouho napustím hrníček vodou pomocí 2km dlouhé zahradní hadice? Při konstantním čtení z paměti trvá získání kódu instrukce a příslušných operandů z paměti v průměru 5ns. Jaká je nejvyšší reálná rychlost vykonávání kódu uloženého v paměti 4GHz procesorem? [ 1/(5 ∗ 10−9) = 0.2 ∗ 109 = 200 MHz ] IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 3/55 Efektivita interakce Pozorování Interakce jednotlivých úloh/procesů je nevyhnutelná Interakce způsobuje prodlevy ve výpočtu Režie související s interakcí by neměla být důvodem pro neefektivitu paralelního zpracování Závěr Komunikační primitiva musí být co nejefektivnější V této přednášce Popis různých typů komunikačních operací Odvození ceny pro jednotlivé topologie IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 4/55 Topologie komunikační sítě Topologie Fyzická/logická struktura komunikačních kanálů mezi jednotlivými participanty komunikace. Vlastnosti komunikační sítě Průměr (délka maximální nejkratší cesty) Konektivita (minimální počet disjunktních cest) Stupeň (max. počet linek incidenčních s jedním vrcholem) Cena Výlučnost přístupu (použití jednou úlohou blokuje ostatní) Rozšiřitelnost Škálovatelnost IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 5/55 Sběrnice, Kliky Sběrnice Sdílené médium Propustnost, klesá s počtem uzlů (je třeba cache) Důležitost: model sdíleného adresového prostoru Kliky (úplné sítě) Privátní neblokující spojení každého s každým Cena: počet linek je kvadratický vůči N Cena: stupeň každého uzlu je N − 1 Škálovatelné, za podmínky levného zvyšování stupně uzlu Důležitost: abstraktní představa sítě, logická struktura IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 6/55 Prsteny, Hvězdice Prsten (kruh, řetěz, 1-rozměrná mřížka) Uspořádání na uzlech Privátní neblokující komunikace s 2 nejbližšími uzly Důležitost: logická struktura komunikace, Pipeline model Hvězdice Spojení přes jeden centrální uzel Středový uzel může být úzkým místem Lze hierarchicky vrstvit (hvězdice hvězdic) Důležitost: Master-Slave model IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 7/55 Hyperkostka, Strom s aktivními vnitřními uzly Hyperkostka Spojení n uzlů ve tvaru log2n-rozměrné krychle Stupeň uzlu je log2n Průměr sítě je log2n Počet linek O(N · log(N)) Postup konstrukce binární označení uzlů s identifikátory 0 až 2log2n − 1 linka existuje mezi uzly pokud se označení liší v jednom bitu minimální vzdálenost uzlů odpovídá počtu odlišných bitů v označení uzlů Strom s aktivními vnitřními uzly Strom, kde participanty komunikace jsou listy i vnitřní uzly Kostra hyperkostky — Strom s maximální hloubkou log2n Důležitost: Optimální šíření informací IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 8/55 Další topologie Jiné topologie Z hlediska logického návrhu paralelní aplikace nezajímavé. Příklady Obecné stromy Přepojované sítě Vícevrstvé sítě (ω-síť) Mřížky Cyklické mřížky (torrus) IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 9/55 Sekce Jeden na všechny a všichni na jednoho IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 10/55 Jeden na všechny a všichni na jednoho One-To-All Vysílání (OTA) Úloha posílá několika/všem ostatním identická data Ve výsledku je p kopií originální zprávy v lokálních adresových prostorech adresátů Změna struktury dat: m → p ∗ m (m-je velikost zprávy) All-To-One Redukce (ATO) Duální operace k “One-To-All” Několik/všechny úlohy posílají data jedné úloze Data se kombinují pomocí zvoleného asociativního operátoru Ve výsledku je jedna kopie v adresovém prostoru cílové úlohy m1 ⊗ m2 . . . ⊗ mp m Změna struktury dat: m ∗ p → m IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 11/55 OTA: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 12/55 OTA: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 12/55 OTA: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 12/55 ATO: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 13/55 ATO: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 13/55 ATO: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 13/55 OTA: Pro topologie prsten či řetěz Naivní způsob One-To-All pro p procesů Poslat p − 1 zpráv postupně ostatním procesům Úzké místo: odesílatel Síť je nevyužitá, komunikuje pouze jedna dvojice procesů Technika rekurzivního zdvojení (připomenutí) Nejprve první proces pošle zprávu jinému procesu Poté oba procesy pošlou zprávu jiné dvojici Poté čtveřice procesů pošle zprávu jiné čtveřici . . . První proces pošle nejvýše log(p) zpráv Souběh zpráv na linkách sítě Optimální vzdálenosti adresátů pro jednotlivá kola jsou p/2, p/4, p/8, p/16, . . . IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 14/55 OTA: Pro topologii d-dimenzionální mřížka One-To-All ve 2-rozměrné síti o p uzlech Lze chápat jako √ p řetízků o √ p uzlech V první fázi se propaguje informace do všech řetízků V druhé fázi se souběžně propaguje informace v jednotlivých řetízcích Celková cena: 2(log( √ p)) sekvenčně provedených operací One-To-All v d-rozměrné síti Stejný princip, velikost v jednom rozměru je p1/d Celková cena: d(log(p1/d )) IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 15/55 OTA: Pro topologii 2-dimenzionální mřížka IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 16/55 OTA: Pro topologii 2-dimenzionální mřížka IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 16/55 OTA: Pro topologii 2-dimenzionální mřížka IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 16/55 OTA: Pro topologii 2-dimenzionální mřížka IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 16/55 OTA: Pro topologii 2-dimenzionální mřížka IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 16/55 OTA: Pro topologii 2-dimenzionální mřížka IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 16/55 OTA: Pro topologii hyperkostka Hyperkostka s 2d vrcholy Aplikuje se algoritmus pro síť ve tvaru mřížky d-dimenzionální síť s hloubkou sítě 2 Každá fáze proběhne v konstantním čase (poslání 1 zprávy) Nenastává souběžný přístup na žádnou z komunikačních linek Celková cena: d Příklad Jak proběhne One-To-All na hyperkostce s dimenzí 5? IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 17/55 OTA: Pro hyperkostku o dimenzi 5 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 18/55 OTA: Pro hyperkostku o dimenzi 5 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 18/55 OTA: Pro hyperkostku o dimenzi 5 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 18/55 OTA: Pro hyperkostku o dimenzi 5 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 18/55 OTA: Pro hyperkostku o dimenzi 5 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 18/55 OTA: Pro hyperkostku o dimenzi 5 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 18/55 OTA: Pro hyperkostku o dimenzi 5 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 18/55 OTA: Pro hyperkostku o dimenzi 5 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 18/55 ATO: Duálně k OTA All-To-One Redukce pro p procesů Probíhá duálně k operaci One-To-All Příklad: ATO pro topologie prsten či řetěz Prvně procesy s lichým ID pošlou zprávu procesům s ID o jedna menším, kde se zprávy zkombinují s hodnotou, kterou chtějí vyslat procesy se sudým ID Následně proběhne kombinace informací sousedních procesů se sudým ID na procesech jejichž ID je násobkem čtyř . . . IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 19/55 ATO: Duálně k OTA All-To-One Redukce pro p procesů Probíhá duálně k operaci One-To-All Příklad: ATO pro topologie prsten či řetěz Prvně procesy s lichým ID pošlou zprávu procesům s ID o jedna menším, kde se zprávy zkombinují s hodnotou, kterou chtějí vyslat procesy se sudým ID Následně proběhne kombinace informací sousedních procesů se sudým ID na procesech jejichž ID je násobkem čtyř . . . IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 19/55 ATO: Duálně k OTA All-To-One Redukce pro p procesů Probíhá duálně k operaci One-To-All Příklad: ATO pro topologie prsten či řetěz Prvně procesy s lichým ID pošlou zprávu procesům s ID o jedna menším, kde se zprávy zkombinují s hodnotou, kterou chtějí vyslat procesy se sudým ID Následně proběhne kombinace informací sousedních procesů se sudým ID na procesech jejichž ID je násobkem čtyř . . . IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 19/55 ATO: Duálně k OTA All-To-One Redukce pro p procesů Probíhá duálně k operaci One-To-All Příklad: ATO pro topologie prsten či řetěz Prvně procesy s lichým ID pošlou zprávu procesům s ID o jedna menším, kde se zprávy zkombinují s hodnotou, kterou chtějí vyslat procesy se sudým ID Následně proběhne kombinace informací sousedních procesů se sudým ID na procesech jejichž ID je násobkem čtyř . . . IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 19/55 ATO: Duálně k OTA All-To-One Redukce pro p procesů Probíhá duálně k operaci One-To-All Příklad: ATO pro topologie prsten či řetěz Prvně procesy s lichým ID pošlou zprávu procesům s ID o jedna menším, kde se zprávy zkombinují s hodnotou, kterou chtějí vyslat procesy se sudým ID Následně proběhne kombinace informací sousedních procesů se sudým ID na procesech jejichž ID je násobkem čtyř . . . IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 19/55 Univerzální algoritmy Pozorování One-To-All procedury jsou si podobné Jdou nahradit univerzální procedurou Univerzální algoritmy OTA vysílání a ATO Redukce Předpokládají 2d uzlů (hyperkostka) Každý uzel identifikován bitovým vektorem AND a XOR bitové operace Cena d(ts + mtw ) IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 20/55 Univerzální algoritmy – OTA vysílání (1) proc One-To-All(d, id, X) (2) mask := 2d − 1 (3) for i := d − 1 downto 0 (4) mask := mask XOR 2i (5) if (id AND mask) = 0 (6) then if (id AND 2i ) = 0 (7) then msg_destination := id XOR 2i (8) send X to msg_destination (9) else msg_source := id XOR 2i (10) receive X from msg_source (11) fi (12) fi (13) end (14) end IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 21/55 Univerzální algoritmy – OTA vysílání – libovolný odesílatel (1) proc General-One-To-All(d, id, src, X) (2) virtid := id XOR src (3) mask := 2d − 1 (4) for i := d − 1 downto 0 (5) mask := mask XOR 2i (6) if (virtid AND mask) = 0 (7) then if (virtid AND 2i ) = 0 (8) then virt_destination := virtid XOR 2i (9) send X to (virt_destination XOR src) (10) else virt_source := virtid XOR 2i (11) receive X from (virt_source XOR src) (12) fi (13) fi (14) end (15) end IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 22/55 Univerzální algoritmy – ATO Redukce (1) proc All-To-One(d, id, m, X, sum) (2) for j := 0 to m − 1 do sum[j] := X[j] end (3) mask := 0 (4) for i := to d − 1 (5) if (id AND mask) = 0 (6) then if (id AND 2i ) = 0 (7) then msg_destination := id XOR 2i (8) send sum to msg_destination (9) else msg_source := id XOR 2i (10) receive X from msg_source (11) for j := 0 to m − 1 (12) sum[j] := sum[j] + X[j] (13) end (14) fi fi (15) mask := mask XOR 2i (16) end (17) end IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 23/55 Sekce Všichni všem a všichni od všech IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 24/55 Všichni všem a všichni od všech All-To-All Vysílání Všichni posílají informaci všem Každá úloha posílá jednu zprávu všem ostatním úlohám Ve výsledku je p kopií p originálních zpráv v lokálních adresových prostorech adresátů Změna struktury dat: p ∗ m → p ∗ p ∗ m All-To-All Redukce Všichni posílají informaci všem, příchozí zprávy se kombinují Každá úloha má pro každou jinou úlohu jinou zprávu Změna struktury dat: p ∗ p ∗ m → p ∗ m Naivní řešení Sekvenční/násobné použití One-To-All procedur Neefektivní využití sítě IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 25/55 ATA Vysílání: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 26/55 ATA Vysílání: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 26/55 ATA Vysílání: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 26/55 ATA Redukce: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 27/55 ATA Redukce: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 27/55 ATA Redukce: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 27/55 ATA: Pro topologie Prsten či řetěz Prsten 1. fáze: každý uzel pošle informaci svému sousedovi 2. až n-tá fáze: uzly sbírají a přeposílají příchozí zprávy Všechny linky jsou po celou dobu operace plně využité Optimální algoritmus Řetěz Vysílání zpráv sousedům na obě strany Full-duplex linky ⇒ n − 1 fází Half-duplex linky ⇒ 2(n − 1) fází ATA Redukce Zprávy po jedné posílány po kruhu tak, že zpráva pro nejvzdálenější uzel je poslána jako první Při průchodu uzlem se přikombinuje lokální zpráva pro adresáta právě procházející zprávy IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 28/55 ATA: Pro topologie mřížky či hyperkostky Mřížka 2 fáze – √ p řetízků o √ p uzlech Po první fázi uzly mají uzly √ p částí z celkového počtu p částí zprávy Příklad sítě 4x4, každý posílá své ID každému Hyperkostka Rozšíření algoritmu pro sítě na d dimenzí Po každé fázi (z celkového počtu d) je objem zpráv zdvojnásoben ATA Redukce Duální postup Po každé fázi je objem zpráv zredukován na polovinu IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 29/55 ATA Vysílání: Mřížka 00 01 02 03 04 05 06 07 08 12 09 10 11 13 14 15 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 30/55 ATA Vysílání: Mřížka 00 01 02 03 04 05 06 07 08 12 09 10 11 13 14 15 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 30/55 ATA Vysílání: Mřížka 12x0 x0 x0 x0 05 09 1301 00 04 08x0 = 14100602 03 151107x3 = x2 = x1 = x1 x2 x3 x3 x3 x3 x2 x2 x2 x1 x1 x1 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 30/55 ATA Vysílání: Mřížka 12x0 x0 x0 x0 05 09 1301 00 04 08x0 = 14100602 03 151107x3 = x2 = x1 = x1 x2 x3 x3 x3 x3 x2 x2 x2 x1 x1 x1 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 30/55 ATA Vysílání: Mřížka 141002 x = 01 09 13 00 04 08 12 03 07 11 05 06 15 x x x x x x x x x x x x x x x x IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 30/55 ATA Redukce: Hyperkostka IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 31/55 ATA Redukce: Hyperkostka IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 31/55 ATA Redukce: Hyperkostka IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 31/55 ATA Redukce: Hyperkostka IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 31/55 ATA Redukce: Hyperkostka IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 31/55 ATA Redukce: Hyperkostka IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 31/55 ATA Redukce: Hyperkostka IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 31/55 ATA: Analýza ceny Kruh a lineární pole, p uzlů T = (ts + tw m)(p − 1) 2D mřížka, p uzlů 1. fáze (ts + mtw )( √ p − 1) 2. fáze (ts + m √ ptw )( √ p − 1) Celkem: T = 2ts( √ p − 1) + tw m(p − 1) Hyperkostka, p = 2d uzlů T = log p i=1 (ts + 2i−1tw m) T = tslog p + tw m(p − 1) Pozorování Člen tw m(p − 1) se vyskytuje vždy Pipeline několika OTA operací IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 32/55 Sekce Všichni všem individuální komunikace IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 33/55 Všichni všem individuální komunikace All-To-All individuální komunikace (ATA individuální) Každá úloha posílá různá data ostatním úlohám Dojde k výměně 2D pole zpráv (p × p) v 1D prostoru (p) Také označováno jako "totální výměna" Změna struktury dat: p ∗ (m1, . . . , mp) → p ∗ m1, p ∗ m2, . . . , p ∗ mp Příklad Transpozice matice (AT [i, j] = A[j, i]) Matice n × n mapována po řádcích na n úloh Úloha j má k dispozici prvky [j, 0], [j, 1], . . . [j, n − 1] Úloha j chce znát prvky [0, j], [1, j], . . . [n − 1, j] IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 34/55 ATA Individuální: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 35/55 ATA Individuální: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 35/55 ATA Individuální: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 35/55 ATA Individuální: Pro topologie Prsten či Řetěz Princip Nejprve všechny úlohy pošlou jedním směrem zprávy pro zbývajících p − 1 úloh V každém dalším kole každá úloha vyextrahuje zprávu, která je určena jí a zbývající zprávy přepošle V posledním kole všechny úlohy přeposílají pouze jednu zprávu Analýza ceny Počet kol je p − 1, všechny zprávy mají velikost m T = p−1 i=1 (ts + tw m(p − i)) = ts(p − 1) + p−1 i=1 itw m = (ts + tw mp/2)(p − 1) IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 36/55 ATA Individuální: Pro topologii mřížky Princip Síť je √ p řetízků o délce √ p 1. fáze: mezi řetízky se vymění v jednom směru zprávy tak, aby informace pro každý uzel v řetízku byla někde v řetízku obsažena 2. fáze: v rámci řetízku se informace napropaguje na odpovídající místo Příklad ATA Individuální komunikace na síti 4x4 uzly Cena Každá fáze distribuuje zprávy velikosti m √ p mezi √ p uzly Cena jedné fáze (viz cena pro prsten): (ts + tw mp/2)( √ p − 1) T = (2ts + tw mp)( √ p − 1) IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 37/55 ATA Individuální: Pro topologii hyperkostky Princip Aplikace algoritmu pro d-dimenzionální sítě Podél jedné dimenze se posílá vždy p/2 zpráv Příklad Krychle 2 × 2 × 2 uzlů Cena V každé fázi vyměněno mp/2 dat log p fází T = (ts + tw mp/2)log p Navíc v každé fázi uzly přeuspořádávají/třídí zprávy IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 38/55 ATA Individuální: Pro topologii hyperkostky – optimalita Problém Každý uzel posílá a přijímá m(p − 1) dat Průměrná vzdálenost, na kterou data putují je (log p)/2 Celkový provoz na síti je p × m(p − 1) × (log p)/2 Počet linek v hyperkostce je p(log p)/2 Optimální algoritmus by měl dosáhnout složitosti T = tw pm(p − 1)(log p)/2 (plog p)/2 = tw m(p − 1) Závěr Pro ATA Individuální komunikaci není algoritmus pro sítě ve tvaru mříží optimální na sítích ve tvaru hyperkostky IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 39/55 ATA Individuální: Optimální algoritmus pro hyperkostku (1) proc All-To-All-Personal(d, id) (2) for i := 1to 2d − 1 (3) partner := id XOR i (4) send Mid to partner (5) receive Mpartner from partner (6) end (7) end Pozorování: Systematická a symetrická volba partnera Lze routovat tak, aby nedocházelo k blokování linek E-cube routing: Cesta mezi 2 body je dána pozicí odlišných bitů těchto bodů, routuje se od nejméně významného bitu Vyžaduje duplexní linky Cena: T = (ts + tw m)(p − 1) IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 40/55 E-Cube routing IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 41/55 E-Cube routing IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 41/55 E-Cube routing IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 41/55 E-Cube routing IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 41/55 E-Cube routing IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 41/55 E-Cube routing IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 41/55 E-Cube routing IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 41/55 Sekce Operace kompletní redukce a prefixového součtu IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 42/55 Operace kompletní redukce Kompletní redukce (All reduce) Úlohy si vzájemně vyměňují data, která se kombinují Lze realizovat jako ATO redukci následovanou OTA vysíláním výsledku z předchozí redukce Změna struktury dat: p ∗ m → p ∗ m Sémantika a využití pro účely synchronizace Úloha nemůže dokončit operaci, dokud všechny participující úlohy nepřispějí svým dílem Může být použito pro realizaci synchronizačního primitiva Implementace Naivně pomocí ATO a OTA, nebo Modifikací operace ATA vysílání rozdíl od ATA: zprávy se nekumulují, ale kombinují Cena pro hyperkostku je T = (ts + tw m)log p IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 43/55 Kompletní redukce: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 44/55 Kompletní redukce: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 44/55 Kompletní redukce: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 44/55 Operace prefixového součtu Prefixový součet Úlohy posílají data ostatním úlohám se stejným či menším ID Data se kombinují (redukce) Změna struktury dat: p ∗ m → p ∗ m Příklad Data v jednotlivých uzlech: 3, 1, 4, 0, 2 Kombinace pomocí operace součtu Výsledná data 3, 4, 8, 8, 10 Implementace Použití algoritmu pro ATA Jak se pozná, že zpráva pochází od uzlu s menším ID? Všechny posílaná data obohacena o identifikátor původce IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 45/55 Sekce Scatter and Gather IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 46/55 Scatter and Gather Scatter (též označováno jako "Scan") Jedna úloha posílá unikátní zprávu každé další úloze One-To-All individuální (personalized) komunikace Na rozdíl od OTA vysílání se žádná data neduplikují Změna struktury dat: (m1, . . . , mp) → m1, . . . , mp Gather (též označováno jako "Concatenation") Jedna úloha sbírá unikátní data od ostatních úloh All-To-One individuální (personalized) komunikace Na rozdíl od ATO redukce se nevyskytuje kombinace dat Změna struktury dat: m1, . . . , mp → (m1, . . . , mp) Implementace Využití algoritmů pro ATO a OTA Celkem log p fází, s každou fází se objem dat zvětšuje T = ts(log p) + tw m(p − 1) IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 47/55 Scatter: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 48/55 Scatter: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 48/55 Scatter: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 48/55 Gatter: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 49/55 Gatter: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 49/55 Gatter: Změna struktury dat IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 49/55 Sekce Cyklický posun IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 50/55 Permutace Permutace Obecnější komunikační primitiva Současně probíhající OTO přerozdělování dat Jedna úloha posílá data jedné jiné úloze Příklad Cyklický posun o q (circular q-shift) p úloh Úloha i posílá data úloze (i + q) mod p Použití Specifické maticové operace Vyhledávání vzorů v textu či obrazu IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 51/55 Cyklický posun – Sítě ve tvaru mřížek 1-dimenzionální Intuitivně: rotace o q pozic Směr rotace závislý na q, určí se dle výrazu min(q, p − q) Dvourozměrné sítě Akcelerace cyklického posunu s využitím druhé dimenze než, ve které probíhá posun Jedna dimenze má rozměr √ p uzlů Posun v druhé dimenzi akceleruje o √ p kroků Cena Nejvzdálenější posun v jedné dimenzi je √ p/2 T = (ts + tw m)( √ p) Příklad Síť 4x4 uzly, cyklický posun o 5 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 52/55 Cyklický posun – Síť ve tvaru hyperkostky Princip Mapování lineárního pole na hyperkostku dimenze d Zrcadlený šedý kód (reflected Grey code): i = G(i, d) G(0, 1) = 0 G(1, 1) = 1 G(i, x + 1) = if i < 2x G(i, x) else 2x + G(2x+1 − 1 − i, x) q se vyjádří jako součet mocnin čísla 2 Posun proběhne v tolika fázích, kolik je členů v součtu Cena Uzly ve vzdálenosti mocniny čísla 2, jsou od sebe vzdáleny nejvýše 2 kroky (vlastnost kódu) Členů v součtu je nejvýše log p Komunikace probíhá bez blokování linek T = (ts + mtw )(2log p) Se zpětným posunem je počet sčítanců max. (log p)/2 T = (ts + mtw )(log p) IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 53/55 Binary Reflected Grey code 1 4 6 2 7 3 0 5 IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 54/55 Práce na doma Nebodovaný domácí úkol Projděte si probraná komunikační primitiva, a znovu odvoďte jejich cenu pro jednotlivé topologie. IB109 Návrh a implementace paralelních systémů: Kolektivní komunikační primitiva str. 55/55