Paralelnost na úrovni smyčky - Loop-level parallelism

Paralelnost na úrovni smyčky je forma rovnoběžnost v softwarové programování který se týká získávání paralelních úkolů z smyčky. Příležitost paralelismu na úrovni smyčky se často objevuje ve výpočetních programech, kde jsou uložena data náhodný přístup datové struktury. Pokud bude sekvenční program iterovat nad datovou strukturou a pracovat na indexech jeden po druhém, program využívající paralelismus na úrovni smyčky použije více vlákna nebo procesy které fungují na některých nebo všech indexech současně. Takový paralelismus poskytuje a zrychlit na celkovou dobu provádění programu, obvykle v souladu s Amdahlův zákon.

Popis

Pro jednoduché smyčky, kde každá iterace je nezávislá na ostatních, může být paralelismus na úrovni smyčky trapně paralelní, protože paralelizace vyžaduje pouze přiřazení procesu ke zpracování každé iterace. Mnoho algoritmů je však navrženo tak, aby běžely postupně a selhaly při paralelních procesech závod kvůli závislosti v kódu. Sekvenční algoritmy jsou někdy použitelné pro paralelní kontexty s malou modifikací. Obvykle však vyžadují synchronizace procesu. Synchronizace může být buď implicitní, prostřednictvím předávání zpráv, nebo explicitní, pomocí synchronizačních primitiv jako semafory.

Příklad

Zvažte následující kód fungující na seznamu L délky n.

pro (int i = 0; i 
Každá iterace smyčky přebírá hodnotu z aktuálního indexu L, a zvýší jej o 10. Pokud příkaz S1 bere T čas na provedení, pak smyčka nějakou dobu trvá n * T provádět postupně, ignorovat čas potřebný konstrukty smyčky. Nyní zvažte systém s p procesory kde p> n. Li n vlákna běží paralelně, je čas provést vše n kroky se sníží na T.
Méně jednoduché případy vytvářejí nekonzistentní, tj. neserializovatelný výsledky. Zvažte následující smyčku fungující na stejném seznamu L.
pro (int i = 1; i 
Každá iterace nastaví aktuální index na hodnotu předchozího plus deset. Při postupném spouštění je každá iterace zaručena, že předchozí iterace již bude mít správnou hodnotu. S více vlákny, plánování procesů a další úvahy zabraňují tomu, aby příkaz provedení zaručil, že se iterace provede až po splnění jeho závislosti. Může se to velmi dobře stát dříve, což povede k neočekávaným výsledkům. Serializovatelnost lze obnovit přidáním synchronizace, aby se zachovala závislost na předchozích iteracích.
Závislosti v kódu
V kódu je několik typů závislostí.[1][2]
Typ
Zápis
Popis
Pravá (toková) závislost
S1 -> T S2
Skutečná závislost mezi S1 a S2 znamená, že S1 zapisuje na místo, které později přečte S2
Proti závislosti
S1 -> A S2
Anti-závislost mezi S1 a S2 znamená, že S1 čte z místa později zapsaného do S2.
Závislost na výstupu
S1 -> O S2
Závislost výstupu mezi S1 a S2 znamená, že S1 a S2 zapisují na stejné místo.
Závislost vstupu
S1 -> I S2
Závislost vstupu mezi S1 a S2 znamená, že S1 a S2 čtou ze stejného místa.
Aby bylo možné zachovat sekvenční chování smyčky při paralelním spuštění, musí být zachována True Dependence. Anti-Dependence and Output Dependence lze řešit tak, že každému procesu dáte vlastní kopii proměnných (známou jako privatizace).[1]
Příklad skutečné závislosti
S1: int a, b; S2: a = 2; S3: b = a + 40;
S2 -> T S3, což znamená, že S2 má skutečnou závislost na S3, protože S2 zapisuje do proměnné A, ze kterého S3 čte.
Příklad proti závislosti
S1: int a, b = 40; S2: a = b - 38; S3: b = -1;
S2 -> A S3, což znamená, že S2 má závislost na S3, protože S2 čte z proměnné b než na ni S3 zapíše.
Příklad výstupní závislosti
S1: int a, b = 40; S2: a = b - 38; S3: a = 2;
S2 -> O S3, což znamená, že S2 má výstupní závislost na S3, protože oba zapisují do proměnné A.
Příklad závislosti na vstupu
S1: int a, b, c = 2; S2: a = c - 1; S3: b = c + 1;
S2 -> I S3, což znamená, že S2 má vstupní závislost na S3, protože S2 i S3 oba čtou z proměnné C.
Závislost ve smyčkách
Závislost přenášená na smyčce vs nezávislá na smyčce
Smyčky mohou mít dva typy závislostí:
Závislost přenášená smyčkou
Závislost nezávislá na smyčce
V závislosti na smyčce mají smyčky závislost mezi iteracemi, ale nemají závislost mezi iteracemi. Každá iterace může být považována za blok a prováděna paralelně bez dalšího synchronizačního úsilí.
V následujícím příkladu kódu použitého pro výměnu hodnot dvou polí délky n existuje závislost nezávislá na smyčce S1 -> T S3.
pro (int i = 1; i 
V závislosti na smyčce závisejí příkazy v iteraci smyčky na příkazech v jiné iteraci smyčky. Loop-Carried Dependence používá upravenou verzi notace závislosti, kterou jsme viděli dříve.
Příklad závislosti na smyčce kde S1 [i] -> T S1 [i + 1], kde i označuje aktuální iteraci a i + 1 označuje další iteraci.
pro (int i = 1; i 
Graf závislosti nesený smyčkou
Graf závislosti na smyčce graficky zobrazuje závislosti na smyčce mezi iteracemi. Každá iterace je uvedena jako uzel v grafu a směrované hrany ukazují skutečné, anti a výstupní závislosti mezi každou iterací.
Typy
Existuje řada metodik pro paralelizaci smyček.
DISTRIBUOVANÁ smyčka
DOALL paralelismus
DOACROSS paralelismus
SPIRÁLA [3]
DOPIPE paralelismus
Každá implementace se mírně liší v tom, jak se vlákna synchronizují, pokud vůbec. Kromě toho je třeba nějakým způsobem mapovat paralelní úkoly na proces. Tyto úkoly lze přidělit staticky nebo dynamicky. Výzkum ukázal, že vyrovnávání zatížení lze lépe dosáhnout pomocí některých algoritmů dynamické alokace, než když se provádí staticky.[4]
Proces paralelizace sekvenčního programu lze rozdělit do následujících samostatných kroků.[1] Každá konkrétní paralelizace smyčky níže je implicitně provádí.
Typ
Popis
Rozklad
Program je rozdělen na úkoly, nejmenší využitelná jednotka souběžnosti.
Úkol
Úkoly jsou přiřazeny procesům.
Orchestrace
Přístup k datům, komunikace a synchronizace procesů.
Mapování
Procesy jsou vázány na procesory.
DISTRIBUOVANÁ smyčka
Když má smyčka závislost nesenou smyčkou, jedním ze způsobů, jak ji paralelizovat, je distribuce smyčky do několika různých smyček. Příkazy, které na sobě nejsou vzájemně závislé, jsou odděleny, aby bylo možné tyto distribuované smyčky provádět paralelně. Zvažte například následující kód. 
pro (int i = 1; i 
Smyčka má závislost nesenou smyčkou S1 [i] -> T S1 [i + 1] ale S2 a S1 nemají závislost na smyčce, takže můžeme kód přepsat následujícím způsobem. 
loop1: for (int i = 1; i 
Všimněte si, že nyní lze smyčku1 a smyčku2 provádět paralelně. Místo toho, aby se jedna instrukce prováděla paralelně na různých datech jako v paralelismu na úrovni dat, zde různé smyčky provádějí různé úkoly na různých datech. Řekněme, že je čas provedení S1 a S2 ${displaystyle Ts1}$ a ${displaystyle Ts2}$ pak je čas provedení pro sekvenční formu výše uvedeného kódu ${displaystyle n * (Ts1 + Ts2)}$„Nyní, protože jsme rozdělili dva příkazy a umístili je do dvou různých smyček, nám dává čas provedení ${displaystyle n * Ts1 + Ts2}$. Tento typ paralelismu nazýváme funkčnost nebo paralelismus úlohy.
DOALL paralelismus
DOALL paralelismus existuje, když lze příkazy ve smyčce provádět nezávisle (situace, kdy neexistuje závislost přenášená smyčkou).[1] Například následující kód z pole nečte Aa neaktualizuje pole před naším letopočtem. Žádné iterace nemají závislost na žádné jiné iteraci.
pro (int i = 0; i 
Řekněme, že čas jednoho provedení S1 bude ${displaystyle Ts1}$ pak je čas provedení pro sekvenční formu výše uvedeného kódu ${displaystyle n * Ts1}$, Protože DOALL Parallelism existuje, když jsou všechny iterace nezávislé, zrychlení lze dosáhnout provedením všech iterací paralelně, což nám dává čas provedení ${displaystyle Ts1}$, což je čas potřebný pro jednu iteraci v postupném provádění.
Následující příklad, pomocí zjednodušeného pseudokódu, ukazuje, jak může být smyčka paralelizována k provádění každé iterace nezávisle.
begin_parallelism (); for (int i = 0; i 
DOACROSS paralelismus
DOACROSS Paralelismus existuje tam, kde jsou iterace smyčky paralelizovány extrakcí výpočtů, které lze provádět nezávisle, a jejich současným spuštěním.[5]
Existuje synchronizace k vynucení závislosti přenášené smyčkou.
Zvažte následující synchronní smyčku se závislostí S1 [i] -> T S1 [i + 1].
pro (int i = 1; i 
Každá iterace smyčky provádí dvě akce
Vypočítat a [i - 1] + b [i] + 1
Přiřaďte hodnotu a [i]
Výpočet hodnoty a [i - 1] + b [i] + 1, a poté provedení přiřazení lze rozložit na dva řádky (příkazy S1 a S2):
S1: int tmp = b [i] + 1; S2: a [i] = a [i - 1] + tmp;
První řádek, int tmp = b [i] + 1;, nemá závislost na smyčce. Smyčka může být poté paralelizována paralelním výpočtem dočasné hodnoty a následnou synchronizací přiřazení a [i].
post (0); for (int i = 1; i 
Řekněme, že je čas provedení S1 a S2 ${displaystyle Ts1}$ a ${displaystyle Ts2}$ pak je doba provedení pro sekvenční formu výše uvedeného kódu ${displaystyle n * (Ts1 + Ts2)}$„Nyní, protože existuje DOACROSS paralelismus, lze zrychlení dosáhnout provedením iterací pipeline, což nám dává čas provedení ${displaystyle Ts1 + n * Ts2}$.
DOPIPE paralelismus
DOPIPE Parallelism implementuje pipeline paralelismus pro závislost na smyčce, kde je iterace smyčky distribuována na více synchronizovaných smyčkách.[1] Cílem DOPIPE je chovat se jako montážní linka, kde je spuštěna jedna fáze, jakmile je k dispozici dostatek dat z předchozí fáze.[6]
Zvažte následující, synchronní kód se závislostí S1 [i] -> T S1 [i + 1].
pro (int i = 1; i 
S1 musí být provedeno postupně, ale S2 nemá žádnou závislost na smyčce. S2 lze provést paralelně pomocí DOALL Parallelism po provedení všech výpočtů potřebných S1 v sérii. Zrychlení je však omezeno, pokud se tak stane. Lepším přístupem je paralelizace tak, že S2 odpovídající každé S1 se provede, když je řečená S1 hotová.
Implementace zřetězeného paralelismu vede k následující sadě smyček, kde se druhá smyčka může provést pro index, jakmile první smyčka dokončí svůj odpovídající index.
pro (int i = 1; i 
Řekněme, že je čas provedení S1 a S2 ${displaystyle Ts1}$ a ${displaystyle Ts2}$ pak je doba provedení pro sekvenční formu výše uvedeného kódu ${displaystyle n * (Ts1 + Ts2)}$„Nyní, protože existuje paralelismus DOPIPE, lze zrychlení dosáhnout provedením iterací pipeline, což nám dává čas provedení ${displaystyle n * Ts1 + (n / p) * Ts2}$, kde p je počet procesorů paralelně.
Viz také
Datový paralelismus
Paralelnost úkolů
Paralelismus s použitím různých typů paměťových modelů, jako je sdílené a distribuováno a Předávání zpráv
Reference
^ A b C d E Solihin, Yan (2016). Základy paralelní architektury. Boca Raton, FL: CRC Press. ISBN  978-1-4822-1118-4.
^ Goff, Gina (1991). "Praktické testování závislosti". Sborník příspěvků z konference ACM SIGPLAN 1991 o návrhu a implementaci programovacího jazyka - PLDI '91. str. 15–29. doi:10.1145/113445.113448. ISBN  0897914287.
^ Murphy, Niall. „Objevování a využívání paralelismu ve smyčkách DOACROSS“ (PDF). Univerzita v Cambridge. Citováno 10. září 2016.
^ Kavi, Krišna. "Paralelizace smyček DOALL a DOACROSS - průzkum". Citovat deník vyžaduje | deník = (Pomoc)
^ Unnikrishnan, Priya (2012), „Praktický přístup k paralelizaci DOACROSS“, Paralelní zpracování Euro-Par 2012, Přednášky v informatice, 7484, str. 219–231, doi:10.1007/978-3-642-32820-6_23, ISBN  978-3-642-32819-0
^ „DoPipe: Efektivní přístup k paralelizaci simulace“ (PDF). Intel. Citováno 13. září 2016.