Automatická paralelizace - Automatic parallelization
Automatická paralelizace , také automatická paralelizace nebo autoparalelizace označuje převod sekvenčního kódu na vícevláknový a/nebo vektorizovaný kód za účelem použití více procesorů současně v počítači s více procesory ( SMP ) se sdílenou pamětí . Plně automatická paralelizace sekvenčních programů je výzvou, protože vyžaduje komplexní analýzu programu a nejlepší přístup může záviset na hodnotách parametrů, které nejsou v době kompilace známy.
Řídicí struktury programování, na které se autoparalelizace nejvíce zaměřuje, jsou smyčky , protože obecně většina času provádění programu probíhá uvnitř nějaké formy smyčky. Existují dva hlavní přístupy k paralelizaci smyček: víceřetězcové propojování a cyklické vícevláknové zpracování. Zvažte například smyčku, která na každou iteraci použije sto operací a běží na tisíc iterací. Lze to chápat jako mřížku 100 sloupců po 1000 řádcích, celkem 100 000 operací. Cyklické vícevláknové přiřazení každého řádku k jinému vláknu. Pipelined multi-threading přiřadí každý sloupec k jinému vláknu.
Technika automatické paralelizace
Analyzovat
Toto je první fáze, kdy skener přečte vstupní zdrojové soubory, aby identifikoval všechna statická a externí použití. Každý řádek v souboru bude zkontrolován podle předem definovaných vzorů, aby se oddělil do tokenů . Tyto tokeny budou uloženy v souboru, který bude později použit v gramatickém stroji. Gramatický modul zkontroluje vzory tokenů, které odpovídají předdefinovaným pravidlům, aby v kódu identifikoval proměnné, smyčky, řídicí příkazy, funkce atd.
Analyzovat
Analyzátor se používá k identifikaci částí kódu, které mohou být provedeny současně. Analyzátor používá informace o statických datech poskytnuté analyzátorem skeneru. Analyzátor nejprve najde všechny zcela nezávislé funkce a označí je jako jednotlivé úkoly. Analyzátor poté zjistí, které úkoly mají závislosti.
Plán
Plánovač vypíše všechny úkoly a jejich závislosti na sebe navzájem, pokud jde o provádění a začít krát. Plánovač vytvoří optimální plán z hlediska počtu procesorů, které mají být použity, nebo celkové doby provedení aplikace.
Generování kódu
Plánovač bude generovat seznam všech úkolů a podrobnosti jader, na kterých budou provádějí spolu s časem, že budou vykonávat pro. Generátor kódu vloží do kódu speciální konstrukce, které budou načteny během provádění plánovačem. Tyto konstrukty budou instruovat plánovač, na kterém jádru se konkrétní úkol provede spolu s časy začátku a konce.
Cyklické vícevláknové
Cyklický kompilační kompilátor s více vlákny se pokusí rozdělit smyčku tak, aby každou iteraci bylo možné provádět souběžně na samostatném procesoru .
Paralelizační analýza kompilátoru
Překladač obvykle provádí dva průchody analýzy před vlastním paralelizace cílem stanovit následující:
- Je bezpečné paralelizovat smyčku? Odpověď na tuto otázku vyžaduje přesnou analýzu závislosti a analýzu aliasů
- Vyplatí se to paralelizovat? Tato odpověď vyžaduje spolehlivý odhad (modelování) pracovního vytížení programu a kapacity paralelního systému.
První průchod kompilátoru provede analýzu smyčky na datové závislosti, aby určil, zda každou iteraci smyčky lze provést nezávisle na ostatních. Někdy je možné se vypořádat se závislostí na datech, ale může to způsobit dodatečnou režii ve formě předávání zpráv , synchronizace sdílené paměti nebo jiného způsobu komunikace procesoru.
Druhý průchod se pokouší ospravedlnit snahu o paralelizaci porovnáním teoretické doby provedení kódu po paralelizaci s časem sekvenčního spuštění kódu. Poněkud neintuitivně, kód ne vždy těží z paralelního spouštění. Extra režie, která může být spojena s použitím více procesorů, může snížit potenciální zrychlení paralelizovaného kódu.
Příklad
Smyčka se nazývá DOALL, pokud lze všechny její iterace v jakémkoli daném vyvolání provádět souběžně. Níže uvedený kód Fortran je DOALL a může být automaticky paralelizován kompilátorem, protože každá iterace je nezávislá na ostatních a konečný výsledek pole zbude správný bez ohledu na pořadí provádění ostatních iterací.
do i = 1, n
z(i) = x(i) + y(i)
enddo
Existuje mnoho příjemně paralelních problémů, které mají takové DOALL smyčky. Například při vykreslování filmu sledovaného paprskem může být každý snímek filmu vykreslen nezávisle a každý pixel jednoho snímku může být vykreslen nezávisle.
Na druhé straně, následující kód nemůže být auto-paralelizovat, protože hodnota z(i)závisí na výsledku předchozího iterace z(i - 1).
do i = 2, n
z(i) = z(i - 1)*2
enddo
To neznamená, že kód nelze paralelizovat. Ve skutečnosti je ekvivalentní
do i = 2, n
z(i) = z(1)*2**(i - 1)
enddo
Současné paralelizující kompilátory však obvykle nejsou schopny tyto paralelismy vynášet automaticky a je otázkou, zda by tomuto kódu paralelizace vůbec prospěla.
Pipelined multi-threading
Plynovodový vícevláknový paralelní kompilátor se pokusí rozdělit sekvenci operací uvnitř smyčky na řadu bloků kódu, takže každý blok kódu lze spustit na samostatných procesorech souběžně.
Existuje mnoho příjemně paralelních problémů, které mají takové relativně nezávislé bloky kódu, zejména systémy využívající potrubí a filtry . Například při produkci televizního vysílání v přímém přenosu je třeba několikrát za sekundu provést následující úkoly:
- Přečtěte si snímek surových pixelových dat ze snímače obrazu,
- Proveďte kompenzaci pohybu MPEG na nezpracovaných datech,
- Entropie komprimuje pohybové vektory a další data,
- Rozdělte komprimovaná data na pakety,
- Přidejte příslušnou opravu chyb a proveďte FFT pro převod datových paketů na signály COFDM a
- Odešlete signály COFDM z televizní antény.
Plynovodový vícevláknový paralelní kompilátor by mohl přiřadit každou z těchto 6 operací jinému procesoru, možná uspořádanému v systolickém poli , vložením příslušného kódu pro předání výstupu jednoho procesoru dalšímu procesoru.
Nedávný výzkum se zaměřuje na využití síly GPU a vícejádrových systémů pro výpočet takových nezávislých bloků kódu (nebo jednoduše nezávislých iterací smyčky) za běhu. Paměť přístupná (ať už přímá nebo nepřímá) lze jednoduše označit pro různé iterace smyčky a lze ji porovnat pro detekci závislostí. Pomocí těchto informací jsou iterace seskupeny do úrovní tak, že iterace patřící do stejné úrovně jsou na sobě nezávislé a lze je provádět souběžně.
Potíže
Automatická paralelizace kompilátory nebo nástroji je velmi obtížná z následujících důvodů:
- analýza závislostí je obtížná pro kód, který používá nepřímé adresování, ukazatele, rekurze nebo nepřímá volání funkcí, protože je obtížné detekovat takové závislosti v době kompilace;
- smyčky mají neznámý počet iterací;
- přístupy ke globálním zdrojům je obtížné koordinovat, pokud jde o přidělování paměti, I/O a sdílené proměnné;
- nepravidelné algoritmy, které používají na vstupu závislou směrovost, zasahují do analýzy a optimalizace v době kompilace.
Řešení
Vzhledem k inherentním potížím s plně automatickou paralelizací existuje několik jednodušších přístupů k získání paralelního programu ve vyšší kvalitě. Jedním z nich je umožnit programátorům přidávat do svých programů „rady“, které by vedly k paralelizaci kompilátoru, například HPF pro distribuované paměťové systémy a OpenMP nebo OpenHMPP pro systémy sdílené paměti . Dalším přístupem je vybudování interaktivního systému mezi programátory a paralelními nástroji/kompilátory. Pozoruhodnými příklady jsou Pareon společnosti Vector Fabrics , SUIF Explorer (překladač pro střední formát Stanfordské univerzity), překladač Polaris a ParaWise (formálně CAPTools). Konečně je dalším přístupem spekulativní multithreading podporovaný hardwarem .
Paralelizující kompilátory a nástroje
Většina výzkumných překladače pro automatické paralelizace zvážit Fortran programy, protože Fortran dělá silnější záruky o aliasing než jazyky, jako je C . Typickými příklady jsou:
- Překladač paradigmat
- Překladač Polaris
- Rice Fortran D kompilátor
- Kompilátor SUIF
- Kompilátor Vienna Fortran
