Datový paralelismus - Data parallelism
Datový paralelismus je paralelizace mezi více procesory v paralelních výpočetních prostředích. Zaměřuje se na distribuci dat mezi různé uzly, které na datech pracují paralelně. Lze jej použít na běžné datové struktury, jako jsou pole a matice, paralelním zpracováním každého prvku. Kontrastuje s paralelismem úkolů jako s jinou formou paralelismu.
Datovou paralelní úlohu na poli n prvků lze rozdělit rovnoměrně mezi všechny procesory. Předpokládejme, že chceme sečíst všechny prvky daného pole a čas pro operaci jediného přidání je časová jednotka Ta. V případě postupného provádění bude čas potřebný procesem n × Ta časových jednotek, protože shrnuje všechny prvky pole. Na druhou stranu, pokud provedeme tuto úlohu jako datovou paralelní úlohu na 4 procesorech, čas by se snížil na ( n / 4) × Ta + sloučení režijních časových jednotek. Paralelní provedení má za následek zrychlení 4 oproti sekvenčnímu provedení. Jedna důležitá věc, kterou je třeba si uvědomit, je, že lokalita datových odkazů hraje důležitou roli při hodnocení výkonu modelu datového paralelního programování. Lokalita dat závisí na přístupech do paměti prováděných programem a na velikosti mezipaměti.
Dějiny
Využívání konceptu datového paralelismu začalo v 60. letech vývojem Solomonova stroje. Solomonův stroj, nazývaný také vektorový procesor , byl vyvinut k urychlení výkonu matematických operací prací na velkém datovém poli (pracující na více datech v po sobě jdoucích časových krocích). Souběžnost datových operací byla také využívána provozováním více dat současně pomocí jediné instrukce. Těmto procesorům se říkalo „pole procesorů“. V 80. letech byl tento termín zaveden k popisu tohoto programovacího stylu, který byl široce používán k programování Connection Machines v datových paralelních jazycích, jako je C * . Dnes je datový paralelismus nejlépe ilustrován v grafických procesorových jednotkách (GPU), které používají obě techniky provozu na více datech v prostoru a čase pomocí jediné instrukce.
Popis
V multiprocesorovém systému provádějícím jednu sadu instrukcí ( SIMD ) je datový paralelismus dosažen, když každý procesor provádí stejnou úlohu na různých distribuovaných datech. V některých situacích řídí jedno vlákno provádění operace se všemi daty. V ostatních ovládají operaci různá vlákna, ale provádějí stejný kód.
Zvažte například násobení matic a sčítání sekvenčním způsobem, jak je popsáno v příkladu.
Příklad
Níže je sekvenční pseudokód pro násobení a přidáním dvou matic, kdy je výsledek uložené v matici C . Pseudo-kód pro násobení vypočítává skalární součin dvou matic , B a ukládá výsledek do výstupního matice C .
Pokud by byly následující programy prováděny postupně, doba potřebná k výpočtu výsledku by byla (za předpokladu, že délky řádků a délky sloupců obou matic jsou n) a pro násobení a sčítání.
// Matrix multiplication
for (i = 0; i < row_length_A; i++)
{
for (k = 0; k < column_length_B; k++)
{
sum = 0;
for (j = 0; j < column_length_A; j++)
{
sum += A[i][j] * B[j][k];
}
C[i][k] = sum;
}
}
// Array addition
for (i = 0; i < n; i++) {
c[i] = a[i] + b[i];
}
V předchozím kódu můžeme využít datový paralelismus k jeho rychlejšímu provedení, protože aritmetika je nezávislá na smyčce. Paralelizace maticového multiplikačního kódu je dosažena pomocí OpenMP . Direktiva OpenMP, "omp paralelní pro" dává kompilátoru pokyn k provedení kódu ve smyčce for paralelně. Pro násobení můžeme rozdělit matici A a B na bloky podél řádků a sloupců. To nám umožňuje vypočítat každý prvek v matici C jednotlivě, čímž je úkol paralelní. Například: A [mxn] tečka B [nxk] může být dokončena namísto při paralelním spuštění pomocí m * k procesorů.
// Matrix multiplication in parallel
#pragma omp parallel for schedule(dynamic,1) collapse(2)
for (i = 0; i < row_length_A; i++){
for (k = 0; k < column_length_B; k++){
sum = 0;
for (j = 0; j < column_length_A; j++){
sum += A[i][j] * B[j][k];
}
C[i][k] = sum;
}
}
Z příkladu je možné pozorovat, že bude zapotřebí mnoho procesorů, protože velikost matic se neustále zvyšuje. Udržování nízké doby provádění je prioritou, ale jak se zvyšuje velikost matice, čelíme dalším omezením, jako je složitost takového systému a související náklady. Proto, omezující počet procesorů v systému, můžeme stále použít stejný princip a rozdělit data do větších bloků pro výpočet součinu dvou matic.
Pro přidání polí v datové paralelní implementaci předpokládejme skromnější systém se dvěma centrálními procesorovými jednotkami (CPU) A a B, CPU A může přidat všechny prvky z horní poloviny polí, zatímco CPU B může přidat všechny prvky z spodní polovina polí. Vzhledem k tomu, že dva procesory pracují paralelně, bude úkolem přidání pole trvat polovinu času provádění stejné operace v seriálu pomocí jediného CPU samotného.
Program vyjádřený v pseudokódu níže - který aplikuje nějakou libovolnou operaci foo
na každý prvek v poli - d
ilustruje datový paralelismus:
if CPU = "a" then lower_limit := 1 upper_limit := round(d.length / 2) else if CPU = "b" then lower_limit := round(d.length / 2) + 1 upper_limit := d.length for i from lower_limit to upper_limit by 1 do foo(d[i])
V systému SPMD prováděném na 2 procesorovém systému budou oba procesory provádět kód.
Datový paralelismus zdůrazňuje distribuovanou (paralelní) povahu dat, na rozdíl od zpracování (paralelismus úlohy). Většina skutečných programů spadá někam na kontinuum mezi paralelismem úkolů a datovým paralelismem.
Kroky k paralelizaci
Proces paralelizace sekvenčního programu lze rozdělit do čtyř samostatných kroků.
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. |
Datový paralelismus vs. paralelismus úkolů
Datový paralelismus | Paralelnost úkolů |
---|---|
Stejné operace se provádějí na různých podmnožinách stejných dat. | Na stejných nebo různých datech se provádějí různé operace. |
Synchronní výpočet | Asynchronní výpočet |
Zrychlení je více, protože na všech sadách dat funguje pouze jedno podproces spuštění. | Zrychlení je menší, protože každý procesor bude spouštět jiné vlákno nebo proces na stejné nebo jiné sadě dat. |
Velikost paralelizace je úměrná velikosti vstupních dat. | Rozsah paralelizace je úměrný počtu nezávislých úkolů, které mají být provedeny. |
Navrženo pro optimální vyvážení zátěže v systému s více procesory. | Vyrovnávání zatížení závisí na dostupnosti hardwaru a plánovacích algoritmech, jako je statické a dynamické plánování. |
Datový paralelismus vs. paralelismus modelu
Datový paralelismus | Modelový paralelismus |
---|---|
Stejný model se používá pro každé vlákno, ale data poskytnutá každému z nich jsou rozdělena a sdílena. | Pro každé vlákno se používají stejná data a model je rozdělen mezi vlákna. |
Je to rychlé pro malé sítě, ale velmi pomalé pro velké sítě, protože je třeba přenášet velké množství dat mezi procesory najednou. | U malých sítí je pomalý a u velkých sítí rychlý. |
Datový paralelismus se ideálně používá při maticových a maticových výpočtech a konvolučních neuronových sítích | Modelový paralelismus nachází své uplatnění v hlubokém učení |
Smíšená data a paralelismus úkolů
Data a paralelismus úloh lze implementovat současně jejich kombinací pro stejnou aplikaci. Toto se nazývá Smíšená data a paralelismus úkolů. Smíšený paralelismus vyžaduje sofistikované plánovací algoritmy a softwarovou podporu. Je to nejlepší druh paralelismu, když je komunikace pomalá a velký počet procesorů.
Smíšená data a paralelismus úkolů mají mnoho aplikací. Používá se zejména v následujících aplikacích:
- Smíšená data a paralelismus úkolů nacházejí uplatnění v globálním modelování klimatu. Velké datové paralelní výpočty se provádějí vytvářením mřížek dat představujících zemskou atmosféru a oceány a pro simulaci funkce a modelu fyzikálních procesů se používá paralelismus úloh.
- V simulaci obvodů založených na časování . Data jsou rozdělena mezi různé dílčí okruhy a paralelismu je dosaženo orchestrací z úkolů.
Prostředí paralelního programování dat
Dnes je k dispozici řada datových paralelních programovacích prostředí, z nichž nejpoužívanější jsou:
- Rozhraní pro předávání zpráv : Jedná se o programovací rozhraní pro předávání zpráv mezi platformami pro paralelní počítače. Definuje sémantiku funkcí knihovny, která uživatelům umožňuje psát přenosné programy pro předávání zpráv v jazycích C, C ++ a Fortran.
- Open Multi Processing (Open MP): Jedná se o rozhraní API (Application Programming Interface), které podporuje modely programování sdílené paměti na více platformách víceprocesorových systémů.
- CUDA a OpenACC : CUDA a OpenACC (v uvedeném pořadí) jsou platformy API pro paralelní výpočty navržené tak, aby softwarovému inženýrovi umožnily využívat výpočetní jednotky GPU pro zpracování pro všeobecné účely.
- Threading Building Blocks a RaftLib : Obě programovací prostředí s otevřeným zdrojovým kódem, která umožňují smíšený datový / úkolový paralelismus v prostředích C / C ++ napříč heterogenními prostředky.
Aplikace
Datový paralelismus nachází své uplatnění v různých oblastech od fyziky, chemie, biologie, materiálových věd až po zpracování signálů. Vědy naznačují paralelismus dat pro simulaci modelů, jako je molekulární dynamika, sekvenční analýza dat genomu a další fyzikální jevy. Hnací síly ve zpracování signálu pro paralelnost dat jsou kódování videa, zpracování obrazu a grafiky, bezdrátová komunikace, abychom jmenovali alespoň některé.
Viz také
- Aktivní zpráva
- Paralela na úrovni instrukcí
- Škálovatelný paralelismus
- Rovnoběžnost na úrovni závitu
- Model paralelního programování
Poznámky
-
^ Některá vstupní data (např. Při
d.length
vyhodnocení na 1 around
zaokrouhlení na nulu [toto je jen příklad, neexistují žádné požadavky na to, jaký typ zaokrouhlování se používá]) povedou klower_limit
tomuupper_limit
, že budou větší než , předpokládá se, že smyčka okamžitě skončí ( tj. dojde k nulovým iteracím), když k tomu dojde.
Reference
- Hillis, W. Daniel a Steele, Guy L. , Data Parallel Algorithms Communications of the ACM December 1986
- Blelloch, Guy E, Vector Models for Data-Parallel Computing MIT Press 1990. ISBN 0-262-02313-X