Broadcast (paralelní vzor) - Broadcast (parallel pattern)

tento článek je sirotek, jako žádné další články odkaz na to. Prosím zavést odkazy na tuto stránku z související články; zkuste Najít odkaz nástroj pro návrhy. (Července 2019)

Přenos je primitivní kolektivní komunikace v paralelní programování k distribuci programovacích pokynů nebo dat do uzlů v klastru je to reverzní operace redukce.^[1] Vysílací operace je široce používána v paralelních algoritmech, jako je násobení matice-vektor,^[1] Gaussova eliminace a nejkratší cesty.^[2]

The Rozhraní pro předávání zpráv implementuje vysílání v MPI_Bcast.^[3]

Definice

Zpráva ${ displaystyle M [1..m]}$délky n by měl být distribuován z jednoho uzlu do všech ostatních ${ displaystyle p-1}$ uzly.

${ displaystyle T _ { text {byte}}}$je čas potřebný k odeslání jednoho bajtu.

${ displaystyle T _ { text {start}}}$je čas potřebný pro cestu zprávy do jiného uzlu, bez ohledu na jeho délku.

Proto je čas odeslat balíček z jednoho uzlu do druhého ${ displaystyle t = velikost * T _ { text {byte}} + T _ { text {start}}}$.^[1]

${ displaystyle p}$ je počet uzlů a počet procesorů.

Vysílání binomického stromu ^[4]

Vysílání binomického stromu

S Binomial Tree Broadcast se odesílá celá zpráva najednou. Každý uzel, který již zprávu přijal, ji odešle dále. To roste exponenciálně, protože v každém kroku se počet odesílajících uzlů zdvojnásobí. Algoritmus je ideální pro krátké zprávy, ale u delších zpráv klesá, protože v době, kdy dojde k prvnímu přenosu a je zaneprázdněn pouze jeden uzel.

Odeslání zprávy do všech uzlů trvá ${ displaystyle log_ {2} (p) t}$ čas, jehož výsledkem je doba běhu ${ displaystyle log_ {2} (p) (mT _ { text {byte}} + T _ { text {start}})}$

Zpráva Mid := uzel číslop := číslo z uzly-li id > 0      blocking_receive Mpro (i := strop(log_2(p)) - 1; i >= 0; i--)    -li (id % 2^(i+1) == 0 && id + 2^i <= p)        poslat M na uzel id + 2^i

Lineární potrubní vysílání^[4]

Pipeline Broadcast

Zpráva je rozdělena na ${ displaystyle k}$ balíčky a posílat po částech z uzlu ${ displaystyle n}$ do uzlu ${ displaystyle n + 1}$. Čas potřebný k distribuci první části zprávy je ${ displaystyle pt = { frac {m} {k}} T _ { text {byte}} + T _ { text {start}}}$ čímž ${ displaystyle t}$ je čas potřebný k odeslání balíčku z jednoho procesoru do druhého.

Odeslání celé zprávy trvá ${ displaystyle (p + k) ({ frac {mT _ { text {byte}}} {k}} + T _ { text {start}}) = (p + k) t = pt + kt}$.

Optimální je vybrat si ${ displaystyle k = { sqrt { frac {m (p-2) T _ { text {byte}}} {T _ { text {start}}}}}}$ což má za následek dobu běhu přibližně

$${ displaystyle mT _ { text {byte}} + pT _ { text {start}} + { sqrt {mpT _ { text {start}} T _ { text {byte}}}}}$$

Doba běhu závisí nejen na délce zprávy, ale také na počtu procesorů, které hrají role. Tento přístup svítí, když je délka zprávy mnohem větší než množství procesorů.

Zpráva M := [m_1, m_2, ..., m_n]id = uzel číslopro (i := 1; i <= n; i++) v paralelní    -li (id != 0)        blocking_receive m_i            -li (id != n)        poslat m_i na uzel id + 1

Pipelined Binary Tree Broadcast^[2][4]

Pipeline Pipeline Binary Tree Broadcast

Tento algoritmus kombinuje Binomial Tree Broadcast a Linear Pipeline Broadcast, díky čemuž algoritmus funguje dobře pro krátké i dlouhé zprávy. Cílem je, aby co nejvíce uzlů pracovalo a přitom byla zachována schopnost rychlého odesílání krátkých zpráv. Dobrým přístupem je použití Fibonacciho stromy pro rozdělení stromu, které jsou dobrou volbou, protože zprávu nelze odeslat oběma dětem současně. Výsledkem je a binární strom struktura.

V následujícím budeme předpokládat, že komunikace je plny Duplex. The Fibonacciho strom struktura má hloubku asi ${ displaystyle d přibližně protokol _ { Phi} (p)}$čímž ${ displaystyle Phi = { frac {1 + { sqrt {5}}} {2}}}$the Zlatý řez.

Výsledná doba běhu je ${ displaystyle ({ frac {m} {k}} T _ { text {byte}} + T _ { text {start}}) (d + 2k-2)}$. Optimální je ${ displaystyle k = { sqrt { frac {n (d-2) T _ { text {byte}}} {3T _ { text {start}}}}}}$.

To má za následek běh ${ displaystyle 2mT _ { text {byte}} + T _ { text {start}} log _ { Phi} (p) + { sqrt {2mlog _ { Phi} (p) T _ { text {start}} T_ { text {byte}}}}}$.

Zpráva M := [m_1, m_2, ..., m_k]pro i = 1 na k     -li (hasParent())        blocking_receive m_i            -li (hasChild(left_child))        poslat m_i na left_child            -li (hasChild(right_child))        poslat m_i na right_child

Vysílání Two Tree (23-Broadcast) ^[5][6][7]

Vizualizace vysílání ve dvou stromech

Definice

Tento algoritmus si klade za cíl zlepšit některé nevýhody modelů stromové struktury s plynovody. Normálně v modelech stromové struktury s kanály (viz metody výše) dostávají listy pouze svá data a nemohou přispívat k odesílání a šíření dat.

Algoritmus současně používá dva binární stromy komunikovat přes. Tyto stromy se budou nazývat stromy A a B. Strukturálně v binární stromy existuje relativně více ponechaných uzlů než vnitřních uzlů. Základní myšlenkou tohoto algoritmu je vytvořit listový uzel stromu A jako vnitřní uzel stromu B. Má také stejnou technickou funkci na opačné straně od stromu B ke stromu A. To znamená, že dva pakety jsou odesílány a přijímány vnitřními uzly a listy v různých krocích.

Konstrukce stromu

Příklady stromových struktur v závislosti na počtu procesorů

Počet kroků potřebných ke konstrukci konstrukce dvou paralelních prací binární stromy závisí na počtu procesorů. Stejně jako u jiných struktur může být jedním procesorem kořenový uzel, který odesílá zprávy do dvou stromů. Není nutné nastavovat kořenový uzel, protože není těžké rozpoznat směr odesílání zpráv dovnitř binární strom je obvykle shora dolů. Počet procesorů pro sestavení dvou není nijak omezen binární stromy. Nechť je výška kombinovaného stromu h = ⌈Log (p + 2)⌉. Stromy A a B mohou mít výšku ${ displaystyle h-1}$. Zvláště, pokud odpovídá počet procesorů ${ displaystyle p = 2 ^ {h} -1}$, můžeme z obou stran vytvořit stromy a kořenový uzel.

Abychom tento model vytvořili efektivně a snadno s plně sestaveným stromem, můžeme použít dva způsoby zvané „Posun“ a „Zrcadlení“, abychom získali druhý strom. Předpokládejme, že strom A je již modelován a strom B má být konstruován na základě stromu A. Předpokládáme, že máme ${ displaystyle p}$ procesory objednané od 0 do ${ displaystyle p-1}$.

Řazení

Konstrukce stromu pomocí funkce „Shifting“

Metoda „Posun“ nejprve zkopíruje strom A a přesune každý uzel o jednu pozici doleva, aby získal strom B. Uzel, který bude umístěn na -1, se stane podřízeným procesorem ${ displaystyle p-2}$.

Zrcadlení

Konstrukce stromu pomocí zrcadlení

„Zrcadlení“ je ideální pro sudý počet procesorů. S touto metodou může být strom B snadněji sestrojen stromem A, protože neexistují žádné strukturální transformace za účelem vytvoření nového stromu. Symetrický proces navíc usnadňuje tento přístup. Tato metoda zvládne i lichý počet procesorů, v tomto případě můžeme nastavit procesor ${ displaystyle p-1}$ jako kořenový uzel pro oba stromy. U zbývajících procesorů lze použít funkci „Mirroring“.

Zbarvení

Musíme najít plán, abychom se ujistili, že žádný procesor nemusí v kroku posílat ani přijímat dvě zprávy ze dvou stromů. Okraj, je komunikační spojení pro připojení dvou uzlů, a může být označen jako 0 nebo 1, aby se zajistilo, že každý procesor může střídat mezi 0 a 1 označenými okraji. Okraje A a B lze obarvit dvěma barvami (0 a 1) tak, že

• v procesorech není připojen žádný procesor k jeho nadřazeným uzlům A a B pomocí hran stejné barvy -
• v podřízených uzlech není připojen žádný procesor A nebo B pomocí hran stejné barvy.^[7]

V každém sudém kroku jsou hrany s 0 aktivovány a hrany s 1 jsou aktivovány v každém lichém kroku.

Časová složitost

V tomto případě je počet paketů k rozdělen na polovinu pro každý strom. Oba stromy spolupracují na celkovém počtu paketů ${ displaystyle k = k / 2 + k / 2}$ (horní strom + spodní strom)

V každém binárním stromu trvá odeslání zprávy do jiných uzlů ${ displaystyle 2 * i}$ kroky, dokud procesor nemá v kroku alespoň paket ${ displaystyle i}$. Proto můžeme vypočítat všechny kroky jako ${ displaystyle d: = log_ {2} (p + 1) => log_ {2} (p + 1) přibližně log_ {2} (p)}$.

Výsledná doba běhu je ${ displaystyle T (m, p, k) přibližně ({ frac {m} {k}} T _ { text {byte}} + T _ { text {start}}) (2d + k-1)}$. (Optimální ${ displaystyle k = { sqrt { frac {m (2d-1) T _ { text {byte}}} {T _ { text {start}}}}}}$)

To má za následek dobu běhu ${ displaystyle T (m, p) přibližně mT _ { text {byte}} + T _ { text {start}} * 2log_ {2} (p) + { sqrt {m * 2log_ {2} (p) T _ { text {start}} T _ { text {byte}}}}}$.

ESBT-Broadcasting (Edge-disjoint Spanning Binomial Trees)^[8][9]

V této části bude představen další vysílací algoritmus se základním modelem telefonní komunikace. A Hypercube vytváří síťový systém s ${ displaystyle p = 2 ^ {d} (d = 0,1,2,3, ...)}$. Každý uzel je reprezentován binárním ${ displaystyle {0,1}}$ v závislosti na počtu rozměrů. Zásadně je založen na ESBT (Edge-disjoint Spanning Binomial Trees) hyperkrychlové grafy, potrubí${ displaystyle m}$ zprávy jsou rozděleny na ${ displaystyle k}$ pakety) a binomické stromy. Procesor ${ displaystyle 0 ^ {d}}$ cyklicky šíří pakety do kořenů ESBT. Kořeny ESBT vysílají data s binomickým stromem. Opustit vše ${ displaystyle k}$ z ${ displaystyle p_ {0}}$, ${ displaystyle k}$ jsou vyžadovány kroky, protože všechny pakety jsou distribuovány pomocí ${ displaystyle p_ {0}}$. Trvá dalších d kroků, dokud poslední listový uzel neobdrží paket. Celkem ${ displaystyle d + k}$ jsou nutné kroky k vysílání ${ displaystyle m}$ zpráva prostřednictvím ESBT.

Výsledná doba běhu je ${ displaystyle T (m, p, k) = ({ frac {m} {k}} T _ { text {byte}} + T _ { text {start}}) (k + d)}$. ${ displaystyle (k = { sqrt { frac {mdT _ { text {byte}}} {T _ { text {start}}}}})}$.

To má za následek dobu běhu ${ displaystyle T (m, p): = mT _ { text {byte}} + dT _ { text {start}} + { sqrt {mdT _ { text {start}} T _ { text {byte}}} }}$.

Viz také

• Zmenšit (paralelní vzor)
• Operátor redukce

Reference