Paralelizace cyklů.

 Paralelizace cyklů

Lze provést dekompozici dat, můžeme cykly paralelizovat a tím urychlit výpočet => datový paralelismus SPMD

Příklady: nalezení minima/maxima v poli, součet prvků v poli

Rozdělení proměnných v paralelním výpočtu

Lokální proměnné – inicializovány uvnitř smyčky

Sdílené proměnné

Nezávislé – pokud jsou využívány jen pro čtení, nebo pokud v případě pole jde pouze o jeden prvek, se kterým je pracováno v jedné iteraci

Závislé – dále se dělí na:

Redukční – nejprve se čte a pak zapisuje (vše v jedné iteraci) – např. suma - stačí mi lokální kopie proměnné a dám to dohromady nakonec - viz concurrency runtime

Uzamykané – může být čtena i zapisována v několika iteracích (v rámci jedné iterace), nezáleží na pořadí iterací – např. max - musim pouzit zamky, jinak to nejde

Uspořádané – závisí na pořadí iterací - nepomuze mi nic (jen nejake chytre prevedeni na jiny problem, nelze paralelizovat)

Paralelizaci součtu pole lze provést snadno, protože se v cyklu vyskytuje nejvýše redukční proměnná, kterou stačí jen ošetřit mutexem.

Paralelizace cyklu se závislou uspořádanou proměnnou

S = urychlení = čas_neparalelizovaný/čas_paralelní

E = účinnost = urychlení/počet_cpu

Paralelizace sčítání prefixů (výsledek pole součtů) již nelze provést jednoduchým rozdělením iterací vláknům, protože se v cyklu nachází uspořádaná proměnná.

Uspořádaná proměnná nám brání zapisovat do pole v jiném než určeném pořadí. Proto zavedeme ještě jednu kopii pole. S i-1 pak přistupujeme do pole, do kterého se v cyklu již nezapisuje (zrušeno uspořádání). Poté můžeme přeuspořádat pořadí počítání prefixů do stromu s vrcholem uprostřed sčítané posloupnosti. Jestliže lze paralelizovat výpočet posledního prvku, lze paralelizovat i výpočet ostatních prvků. Pomocí úprav a optimalizací se můžeme dostat až na složitost O(n/m) u paralelní verze.

Nápověda pro překladač s autovektorizací

V nejhorším dojde k většímu využití pipelines procesoru
