Datový paralelismus - Data parallelism

Sekvenční vs. datově paralelní provádění úloh

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ů.

Datový paralelismus v násobení matic
// 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:

  1. 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.
  2. 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:

  1. 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.
  2. 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ů.
  3. 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.
  4. 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é

Poznámky

  1. ^ Některá vstupní data (např. Při d.length vyhodnocení na 1 a round zaokrouhlení na nulu [toto je jen příklad, neexistují žádné požadavky na to, jaký typ zaokrouhlování se používá]) povedou k lower_limit tomu upper_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