DOPIPE - DOPIPE

DOPIPE rovnoběžnost je způsob provedení paralelismus na úrovni smyčky zřetězením příkazů ve smyčce. Pipeline paralelismus může existovat na různých úrovních abstrakce, jako jsou smyčky, funkce a algoritmické fáze. Rozsah rovnoběžnost závisí na schopnosti programátorů co nejlépe využít tento koncept. Závisí to také na faktorech, jako je identifikace a oddělení samostatných úkolů a jejich paralelní provádění.[1]

Pozadí

Hlavní účel zaměstnávání paralelismus na úrovni smyčky je hledat a rozdělit sekvenční úkoly programu a převést je na paralelní úkoly bez jakýchkoli předchozích informací o algoritmus. Dobrými kandidáty jsou části dat, které se opakují a spotřebovávají značné množství času provedení paralelismus na úrovni smyčky. Některé běžné aplikace paralelismus na úrovni smyčky se nacházejí v matematické analýze, která používá vícerozměrné matice, které jsou iterovány ve vnořených smyčkách.[2]

Existují různé druhy paralelizačních technik, které se používají na základě režie ukládání dat, stupně paralelizace a datové závislosti. Některé ze známých technik jsou: UDĚLAT VŠE, DOACROSS a DOPIPE.

UDĚLAT VŠE: Tato technika se používá tam, kde můžeme paralelizovat každou iteraci smyčky bez jakékoli interakce mezi iteracemi. Proto se celková doba běhu sníží z N * T (pro sériový procesor, kde T je doba provádění pro každou iteraci) pouze na T (protože všechny N iterace jsou prováděny paralelně).

DOACROSS: Tato technika se používá všude tam, kde existuje možnost datových závislostí. Proto paralelizujeme úkoly takovým způsobem, že všechny úlohy nezávislé na datech jsou prováděny paralelně, ale ty závislé jsou prováděny postupně. K synchronizaci závislých úkolů napříč paralelními procesory se používá určitý stupeň synchronizace.

Popis

DOPIPE je a pipeline technika paralelizace, která se používá v programech, kde je každý prvek vytvořený během každé iterace spotřebován v pozdější iteraci. Následující příklad ukazuje, jak implementovat techniku ​​DOPIPE ke snížení celkové doby provádění rozbitím úkolů uvnitř smyčky a jejich provedením v pipeline způsob. Vloupání do úkolů probíhá tak, že vše závislosti v rámci smyčky jsou jednosměrné, tj. následující iterace nezávisí na předchozí iteraci.

Příklad

Níže uvedený program zobrazuje a pseudo kód[2] pro paralelizaci DOPIPE.

V tomto kódu vidíme, že uvnitř iterace smyčky jsou tři úkoly (F0, F1 a F2) j na 1 až N. Následuje seznam závislostí v kódu:

F1 [j] → T F1 [j + 1], implikuje toto prohlášení F1 v iteraci j + 1 musí být provedeno po příkazu F1 v iteraci j. Toto se také označuje jako skutečná závislost.

F1 [j] → T F2 [j], implikuje toto tvrzení F2 v iteraci j musí být provedeno po příkazu F1 v iteraci j.

pro (j = 1; j <= N; j ++) {F0: o [j] = x [j] - a [j]; F1: z [j] = z [j-1] * 5; F2: y [j] = z [j] * w [j];}

Pokud by tento kód byl spuštěn postupně, pak by se celková spotřebovaná doba rovnala N * (TF0 + T.F1 + T.F2), kde TF0, TF1 a TF2 označte čas provedení funkcí F0, F1 a F2 na iteraci. Nyní, pokud smyčku paralelizujeme pipetováním příkazů uvnitř smyčky následujícím způsobem:

pro (j = 1; j <= N; j ++) {F0: o [j] = x [j] - a [j]; // DOALL parallelism} for (j = 1; j <= N; j ++) {F1: z [j] = z [j-1] * 5; // DOPIPE paralelismus příspěvek (j); // Výsledek F1 se zveřejní a je k dispozici pro použití} for (j = 1; j <= N; j ++) {wait (j); // Čeká, až se F1 dokončí a vytvoří hodnotu z [j], kterou bude používat F2 F2: y [j] = z [j] * w [j];}

Protože F0 je nezávislá funkce, tj. Nemá žádnou závislost přenášenou smyčkou (žádná závislost na j + 1 nebo j-1 iterace). Ani nemá žádnou závislost mezi ostatními příkazy ve smyčce. Proto můžeme tuto funkci úplně oddělit a spustit ji paralelně pomocí DOALL rovnoběžnost. Na druhou stranu jsou příkazy F1 a F2 závislé (vysvětleno výše), proto je rozdělíme do dvou různých smyček a provedeme je v pipeline móda. Používáme příspěvek (j) a počkej (j) synchronizovat mezi smyčkami F1 a F2.

Počínaje první iterací j, příkaz F1 bude proveden v TF1 čas. Mezitím se F2 neprovádí, protože čeká na hodnotu z [j] být vyroben F1. Když F1 dokončí své provedení pro iteraci j, zveřejní hodnotu pomocí příspěvek (j). Po čekání na spuštění F1 pomocí počkej (j), F2 zahájí provádění, protože má hodnotu z [j] k dispozici pro použití. Vzhledem k tomu, že výkon F1 není omezen klávesou F2, spustí se tedy F1 j + 1 zároveň. Obrázek níže ukazuje časovou osu provádění všech příkazů.

Příklad DOPIPE

Z obrázku vidíme, že celkový čas k provedení F0 je TF0, protože všechny iterace F0 jsou prováděny paralelně. Zatímco u F1 a F2 je celková doba provádění rovna N * TF1 + T.F2 (s ohledem na zanedbatelnou dobu synchronizace).

To je podstatně méně než čas získaný během sekvenčního provádění.

Srovnání s jinými modely

UDĚLAT VŠE rovnoběžnost funguje hlavně na principu rozděl a panuj. Zde všechny úlohy běží v různých iteracích, které používají jedinečnou sadu dat. Takže problém s touto implementací spočívá v tom, že když je velké množství datových prací počítáno společně, velký mezipaměti je potřeba prostor pro práci pro různé vlákna. Protože neexistuje závislosti v vlákna, neexistuje žádná režie pro komunikaci mezi vlákny.

Zatímco v DOPIPE, existuje synchronizace režie mezi vlákny. Ale kvůli své zřetězené struktuře vyžaduje méně mezipaměti, protože vyprodukovaná data spotřebitel okamžitě spotřebuje.[2]

Viz také

Reference

  1. ^ Pankratius, Victor; Adl-Tabatabai, Ali-Reza; Tichy, Walter (2011). Základy vývoje vícejádrového softwaru. CRC tisk.
  2. ^ A b C Solihin, Yan (2016). Základy paralelní vícejádrové architektury. Chapman and Hall / CRC.