Kolektivní provoz - Collective operation
Kolektivní operace jsou stavební kameny pro vzory interakce, které se často používají v SPMD algoritmy v paralelní programování kontext. Z tohoto důvodu existuje zájem o efektivní realizaci těchto operací.
Realizaci kolektivních operací zajišťuje Rozhraní pro předávání zpráv[1] (MPI).
Definice
Ve všech asymptotických runtime funkcích označujeme latenci , komunikační náklady na slovo , počet procesorových jednotek a velikost vstupu na uzel . V případech, kdy máme počáteční zprávy na více než jednom uzlu, předpokládáme, že všechny místní zprávy mají stejnou velikost. K oslovení jednotlivých zpracovatelských jednotek používáme .
Pokud nemáme rovnoměrné rozdělení, tj. Uzel má zprávu velikosti , nastavíme horní mez pro dobu běhu .
A model distribuované paměti předpokládá se. Koncepty jsou podobné pro model sdílené paměti. Systémy sdílené paměti však mohou poskytovat hardwarovou podporu pro některé operace, jako je vysílání (§ Vysílání ) například, který umožňuje pohodlné souběžné čtení.[2] Tak mohou být k dispozici nové možnosti algoritmu.
Přenos [3]
Vysílací vzor se používá k distribuci dat z jedné procesorové jednotky do všech procesorových jednotek, což je často potřeba SPMD paralelní programy pro výdej vstupních nebo globálních hodnot. Broadcast lze interpretovat jako inverzní verzi redukčního vzoru (§ Zmenšit ). Zpočátku pouze root s ukládá zprávu . Během vysílání se odešle zbývajícím procesorovým jednotkám, takže nakonec je k dispozici všem procesorovým jednotkám.
Vzhledem k tomu, implementace pomocí sekvenční pro smyčky s iterace se stávají úzkým místem, přístupy rozděl a panuj jsou běžné. Jednou z možností je použít binomickou stromovou strukturu s požadavkem, že musí to být síla dvou. Když je za odeslání odpovědná zpracovatelská jednotka do zpracovatelských jednotek , pošle do zpracovatelské jednotky a deleguje odpovědnost za zpracovatelské jednotky jeho vlastní odpovědnost je omezena na .
Binomické stromy mají problém s dlouhými zprávami . Přijímající jednotka může zprávu šířit na jiné jednotky až poté, co obdrží celou zprávu. Mezitím není komunikační síť využívána. Proto potrubí dál binární stromy se používá, kde je rozdělena do řady balíčky velikosti . Pakety jsou poté vysílány jeden po druhém, takže data jsou rychle distribuována v komunikační síti.
Pipeline vysílání na vyvážené binární strom je možné v .
Snížit [4]
Vzor zmenšení se používá ke shromažďování dat nebo částečných výsledků z různých jednotek zpracování a ke kombinování je do globálního výsledku vybraným operátorem. Snížení lze vnímat jako inverzní verzi vysílání (§ Vysílání ). Dáno jednotky zpracování, zpráva je na procesorové jednotce zpočátku. Všechno jsou agregovány podle a výsledek se nakonec uloží . Operátor redukce musí být alespoň asociativní. Některé algoritmy vyžadují komutativní operátor s neutrálním prvkem. Provozovatelé mají rádi , , jsou běžné.
Vzhledem k tomu, že redukci lze interpretovat jako inverzní vysílání, platí stejné podmínky implementace (§ Vysílání ). Pro potrubí na binární stromy zpráva musí být reprezentovatelná jako vektor menšího objektu pro redukci po komponentách.
Potrubní redukce na vyvážené binární strom je možné v .
Vše zmenšit [5]
Vzor všeho zmenšení se použije, pokud je výsledkem operace zmenšení (§ Zmenšit ) musí být distribuovány do všech zpracovatelských jednotek. Dáno jednotky zpracování, zpráva je na procesorové jednotce zpočátku. Všechno jsou agregovány operátorem a výsledek je nakonec uložen na všech . Analogicky k redukční operaci, operátor musí být alespoň asociativní.
All-redukovat lze interpretovat jako operaci redukce s následným vysíláním (§ Vysílání ). U dlouhých zpráv je vhodná odpovídající implementace, zatímco u krátkých zpráv lze latenci snížit pomocí a hyperkrychle (Hypercube (komunikační vzor) § All-Gather / All-Reduce ) topologie, pokud je síla dvou.
All-redukovat je možné v , protože redukce a vysílání jsou možné v s vyváženým potrubím binární stromy.
Prefix-Sum / Scan [6]
Operace součtu prefixů nebo skenování se používá ke shromažďování dat nebo částečných výsledků z různých jednotek zpracování a k výpočtu mezivýsledků operátorem, které jsou uloženy na těchto jednotkách zpracování. Lze to považovat za zobecnění operace zmenšení (§ Zmenšit ). Dáno jednotky zpracování, zpráva je na procesorové jednotce . Operátor musí být alespoň asociativní, zatímco některé algoritmy vyžadují také komutativní operátor a neutrální prvek. Běžní operátoři jsou , a . Nakonec zpracovatelská jednotka ukládá součet prefixů . V případě tzv. Exkluzivního prefixového součtu zpracovatelská jednotka ukládá součet prefixů . Některé algoritmy vyžadují kromě součtů předpon uložit i celkovou částku na každou jednotku zpracování.
U krátkých zpráv toho lze dosáhnout pomocí hypercube topologie if je síla dvou. U dlouhých zpráv se zobrazí hyperkrychle (Hypercube (komunikační vzor) § Součet předpon, Součet prefixů § Distribuovaná paměť: Algoritmus Hypercube ) topologie není vhodná, protože všechny procesní jednotky jsou aktivní v každém kroku, a proto nelze použít pipeline. A binární strom topologie je vhodnější pro libovolné a dlouhé zprávy (Součet prefixů § Velké velikosti zpráv: Pipeline binární strom ).
Součet předpon na binárním stromu lze implementovat s fází nahoru a dolů. Ve vzestupné fázi se provádí redukce, zatímco sestupná fáze je obdobou vysílání, kde se součty předpon vypočítávají zasláním různých dat levému a pravému dítěti. S tímto přístupem je možné pipeline, protože operace se rovnají redukci (§ Zmenšit ) a vysílání (§ Vysílání ).
Součet předpony pipeline na binárním stromu je možný v .
Bariéra [7]
Bariéra jako kolektivní operace je zevšeobecněním pojmu a bariéra, které lze použít v distribuovaných výpočtech. Když procesorová jednotka volá bariéru, čeká, až všechny ostatní procesorové jednotky zavolají také bariéru. Bariéra se tak používá k dosažení globální synchronizace v distribuovaných výpočtech.
Jedním ze způsobů implementace bariéry je volání all-redukovat (§ Vše zmenšit ) s prázdným / fiktivním operandem. Víme, že runtime All-redukovat je . Použití fiktivního operandu zmenšuje velikost na konstantní faktor a vede k době běhu .
Shromáždit [8]
Shromážděný komunikační vzor se používá k ukládání dat ze všech procesorových jednotek na jedné procesorové jednotce. Dáno jednotky zpracování, zpráva na procesorové jednotce . Pro pevnou procesorovou jednotku , chceme uložit zprávu na . Shromáždění lze považovat za redukční operaci (§ Zmenšit ), který používá operátor zřetězení. To funguje kvůli skutečnosti, že zřetězení je asociativní. Použitím stejného algoritmu redukce binomického stromu získáme runtime . Vidíme, že asymptotický běh je podobný asymptotickému běhu redukce , ale s přidáním faktoru p k termínu . Tento další faktor je způsoben zvětšením velikosti zprávy v každém kroku, jak se zprávy zřetězují. Porovnejte to a zmenšete, kde je velikost zprávy pro operátory jako konstanta .
Shromážděte se [8]
Komunikační vzor all-collect se používá ke shromažďování dat ze všech zpracovatelských jednotek ak ukládání shromážděných dat na všechny zpracovatelské jednotky. Dáno procesní jednotky , zpráva původně uloženo , chceme uložit zprávu na každém .
Lze na to myslet několika způsoby. První je jako operace all-redukovat (§ Vše zmenšit ) se zřetězením jako operátor, stejně jako shromáždění může být reprezentováno redukcí. Druhým je operace shromažďování, po které následuje vysílání nové zprávy o velikosti . Díky tomu vidíme, že se všichni shromáždili je možné.
Rozptyl [9]
Rozptylový komunikační vzor se používá k distribuci dat z jedné procesorové jednotky do všech procesorových jednotek. Liší se od vysílání v tom, že neposílá stejnou zprávu všem zpracovatelským jednotkám. Místo toho rozděluje zprávu a doručuje jednu její část do každé zpracovatelské jednotky.
Dáno procesní jednotky , pevná procesorová jednotka který drží zprávu . Chceme zprávu přenést na . Stejné implementační obavy jako pro shromáždění (§ Shromážděte se ) aplikovat. To vede k optimální době běhu v .
Všichni na všechny [10]
All-to-all je nejobecnější komunikační vzor. Pro , zpráva je zpráva, která je původně uložena v uzlu a musí být doručen do uzlu . Můžeme vyjádřit všechna komunikační primitiva, která nepoužívají operátory, všichni. Například vysílání zprávy z uzlu je emulován nastavením pro a nastavení prázdné pro .
Za předpokladu, že máme plně připojenou síť, je k dispozici nejlepší možná doba běhu pro všechny . Toho je dosaženo prostřednictvím kola přímé výměny zpráv. Pro síla 2, v komunikačním kole , uzel vyměňuje zprávy s uzlem .
Pokud je velikost zprávy malá a v komunikaci dominuje latence, lze k distribuci zpráv v čase použít algoritmus hyperkrychle .
Runtime Overview [11]
Tato tabulka poskytuje přehled nejznámějších asymptotických runtime, za předpokladu, že máme svobodnou volbu topologie sítě.
Ukázkové topologie, které chceme pro optimální běh, jsou binární strom, binomický strom, hyperkrychle.
V praxi se musíme přizpůsobit dostupným fyzickým topologiím, např. vážka, tlustý strom, síťová síť (odkazuje také na jiné topologie).
Více informací pod Topologie sítě.
Pro každou operaci může optimální algoritmus záviset na velikostech vstupu . Například vysílání pro krátké zprávy je nejlépe implementováno pomocí binomického stromu, zatímco pro dlouhé zprávy je optimální zřetězená komunikace na vyváženém binárním stromu.
Složitost uvedená v tabulce závisí na latenci a náklady na komunikaci za slovo kromě počtu procesorových jednotek a velikost vstupní zprávy na uzel . The # odesílatelů a # přijímače sloupce představují počet odesílatelů a příjemců, kteří jsou do operace zapojeni. The # zprávy sloupec uvádí počet vstupních zpráv a Výpočty? sloupec označuje, zda se u zpráv provádějí nějaké výpočty nebo zda jsou zprávy doručeny pouze bez zpracování. Složitost dává asymptotickou běhovou složitost optimální implementace při svobodné volbě topologie.
název | # odesílatelů | # přijímače | # zprávy | Výpočty? | Složitost |
---|---|---|---|---|---|
Přenos | Ne | ||||
Snížit | Ano | ||||
Vše-snížit | Ano | ||||
Součet prefixů | Ano | ||||
Bariéra | Ne | ||||
Shromáždit | Ne | ||||
Shromážděte se | Ne | ||||
Rozptyl | Ne | ||||
Všichni na všechny | Ne | nebo |
Poznámky
- ^ Kolektivní operace mezi komunikátory. Standard rozhraní pro předávání zpráv (MPI), kapitola 7.3.1. Divize matematiky a informatiky, Argonne National Laboratory.
- ^ Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, s. 395
- ^ Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, str. 396-401
- ^ Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, str. 402-403
- ^ Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, str. 403-404
- ^ Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, str. 404-406
- ^ Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, s. 408
- ^ A b Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, str. 412-413
- ^ Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, s. 413
- ^ Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, str. 413-418
- ^ Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, s. 394
Reference
Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019). Sekvenční a paralelní algoritmy a datové struktury - základní sada nástrojů. Springer Nature Switzerland AG. ISBN 978-3-030-25208-3.