Paralelní externí paměť - Parallel external memory

Model PEM

V počítačové vědě, a model paralelní externí paměti (PEM) je vědomi mezipaměti, externí paměť abstraktní stroj.^[1] Jedná se o analogii paralelního výpočtu s jednoprocesorem externí paměť (EM) model. Podobným způsobem je to analogie s vědomím mezipaměti paralelní stroj s náhodným přístupem (PRAM). Model PEM se skládá z řady procesorů, jejich příslušných soukromých mezipamětí a sdílené hlavní paměti.

Modelka

Definice

Model PEM^[1] je kombinací modelu EM a modelu PRAM. Model PEM je výpočetní model, který se skládá z ${ displaystyle P}$ procesory a dvouúrovňový hierarchie paměti. Tato hierarchie paměti se skládá z velké externí paměť (hlavní paměť) velikosti ${ displaystyle N}$ a ${ displaystyle P}$ malý interní paměti (cache). Procesory sdílejí hlavní paměť. Každá mezipaměť je vyhrazena pro jeden procesor. Procesor nemá přístup do mezipaměti jiného uživatele. Mezipaměti mají velikost ${ displaystyle M}$ který je rozdělen na bloky velikosti ${ displaystyle B}$. Procesory mohou provádět operace pouze s daty, která jsou v jejich mezipaměti. Data lze přenášet mezi hlavní pamětí a mezipamětí ve velikostních blocích ${ displaystyle B}$.

Složitost I / O

The míra složitosti modelu PEM je složitost I / O^[1], který určuje počet přenosů paralelních bloků mezi hlavní pamětí a mezipamětí. Během přenosu paralelního bloku může každý procesor přenést blok. Takže když ${ displaystyle P}$ procesory načítají paralelně datový blok velikosti ${ displaystyle B}$ tvoří hlavní paměť do jejich mezipaměti, považuje se to za I / O složitost ${ displaystyle O (1)}$ ne ${ displaystyle O (P)}$. Program v modelu PEM by měl minimalizovat přenos dat mezi hlavní pamětí a mezipamětí a pracovat co nejvíce s daty v mezipaměti.

Konflikty čtení / zápisu

V modelu PEM není síť přímé komunikace mezi P procesory. Procesory musí komunikovat nepřímo přes hlavní paměť. Pokud se více procesorů pokusí o přístup ke stejnému bloku v hlavní paměti současně ke konfliktům čtení / zápisu^[1] nastat. Stejně jako v modelu PRAM jsou zvažovány tři různé varianty tohoto problému:

• Souběžné čtení Souběžný zápis (CRCW): Stejný blok v hlavní paměti může číst a zapisovat více procesorů současně.
• Souběžné čtení Exkluzivní zápis (CREW): Stejný blok v hlavní paměti může číst více procesorů současně. Pouze jeden procesor může zapisovat do bloku najednou.
• Exkluzivní čtení Exkluzivní zápis (EREW): Stejný blok v hlavní paměti nelze číst ani zapisovat více procesory současně. Pouze jeden procesor může přistupovat k bloku najednou.

Následující dva algoritmy^[1] vyřešit problém POSÁDKY a POSÁDKY, pokud ${ displaystyle P leq B}$ procesory zapisují do stejného bloku současně. Prvním přístupem je serializace operací zápisu. Do bloku zapisuje pouze jeden procesor za druhým. Výsledkem je celkem ${ displaystyle P}$ paralelní blokové převody. Je zapotřebí druhý přístup ${ displaystyle O ( log (P))}$ přenosy paralelních bloků a další blok pro každý procesor. Hlavní myšlenkou je naplánovat operace zápisu v a binární stromová móda a postupně kombinovat data do jednoho bloku. V prvním kole ${ displaystyle P}$ procesory kombinují své bloky do ${ displaystyle P / 2}$ bloky. Pak ${ displaystyle P / 2}$ procesory kombinují ${ displaystyle P / 2}$ bloky do ${ displaystyle P / 4}$. Tento postup pokračuje, dokud se všechna data nespojí do jednoho bloku.

Srovnání s jinými modely

Příklady

Vícecestné dělení

Nechat ${ displaystyle M = {m_ {1}, ..., m_ {d-1} }}$ být vektorem čepů d-1 seřazených ve vzestupném pořadí. Nechat ${ displaystyle A}$ být neuspořádaná sada N prvků. D-way oddíl^[1] z ${ displaystyle A}$ je sada ${ displaystyle Pi = {A_ {1}, ..., A_ {d} }}$ , kde ${ displaystyle cup _ {i = 1} ^ {d} A_ {i} = A}$ a ${ displaystyle A_ {i} čepice A_ {j} = emptyset}$ pro ${ Displaystyle 1 leq já$. ${ displaystyle A_ {i}}$ se nazývá i-tý kbelík. Počet prvků v ${ displaystyle A_ {i}}$ je větší než ${ displaystyle m_ {i-1}}$ a menší než ${ displaystyle m_ {i} ^ {2}}$. V následujícím algoritmu^[1] vstup je rozdělen na souvislé segmenty velikosti N / P ${ displaystyle S_ {1}, ..., S_ {P}}$ v hlavní paměti. Procesor i pracuje primárně na segmentu ${ displaystyle S_ {i}}$. Algoritmus vícenásobného dělení (PEM_DIST_SORT^[1]) používá PEM součet prefixů algoritmus^[1] vypočítat součet předpon s optimálním ${ displaystyle O ({ frac {N} {PB}} + log (P))}$ Složitost I / O. Tento algoritmus simuluje optimální algoritmus součtu předpon PRAM.

// Výpočet paralelně oddílu d-way na datových segmentech ${ displaystyle S_ {i}}$pro každého procesor i paralelně dělat    Přečtěte si vektor čepů ${ displaystyle M}$ do mezipaměti. Rozdělit ${ displaystyle S_ {i}}$ do kbelíků a nechat vektor ${ displaystyle M_ {i} =  {j_ {1} ^ {i}, ..., j_ {d} ^ {i} }}$ být počet položek v každém kbelíku.konec proSpusťte součet předpon PEM na sadě vektorů ${ displaystyle  {M_ {1}, ..., M_ {P} }}$ současně .// Použijte vektor součtu předpon k výpočtu posledního oddílupro každého procesor i paralelně dělat    Napište prvky ${ displaystyle S_ {i}}$ do paměťových míst s odpovídajícím posunutím o ${ displaystyle M_ {i-1}}$ a ${ displaystyle M_ {i}}$.konec proPoužívání prefixových součtů uložených v ${ displaystyle M_ {P}}$ poslední procesor P vypočítá vektor ${ displaystyle B}$ velikostí kbelíku a vrátí jej.

Pokud vektor ${ displaystyle d = O ({ frac {M} {B}})}$ otočné čepy M a vstupní sada A jsou umístěny v souvislé paměti, pak lze problém dělení d-way v modelu PEM vyřešit pomocí ${ displaystyle O ({ frac {N} {PB}} + lceil { frac {d} {B}} rceil> log (P) + d log (B))}$ Složitost I / O. Obsah finálních segmentů musí být umístěn v souvislé paměti.

Výběr

The problém s výběrem je o hledání k-té nejmenší položky v neuspořádaném seznamu ${ displaystyle A}$ velikosti ${ displaystyle N}$Následující kód^[1] využívá PRAMSORT což je algoritmus pro optimální třídění PRAM, který běží ${ displaystyle O ( log N)}$, a VYBRAT, což je algoritmus výběru jednoho procesoru pro optimalizaci mezipaměti.

-li ${ displaystyle N  leq P}$ pak     ${ displaystyle { texttt {PRAMSORT}} (A, P)}$    vrátit se ${ displaystyle A [k]}$skončit, pokud // Najít medián každého z nich ${ displaystyle S_ {i}}$pro každého procesor ${ displaystyle i}$ paralelně dělat     ${ displaystyle m_ {i} = { texttt {SELECT}} (S_ {i}, { frac {N} {2P}})}$konec pro // Řadit mediány${ displaystyle { texttt {PRAMSORT}} ( lbrace m_ {1},  dots, m_ {2}  rbrace, P)}$// Rozdělení kolem mediánu mediánů${ displaystyle t = { texttt {PEMPARTITION}} (A, m_ {P / 2}, P)}$-li ${ displaystyle k  leq t}$ pak     vrátit se ${ displaystyle { texttt {PEMSELECT}} (A [1: t], P, k)}$jiný     vrátit se ${ displaystyle { texttt {PEMSELECT}} (A [t + 1: N], P, k-t)}$skončit, pokud

Za předpokladu, že vstup je uložen v souvislé paměti, PEMSELECT má I / O složitost:

${ displaystyle O ({ frac {N} {PB}} + log (PB) cdot log ({ frac {N} {P}}))}$

Třídění distribuce

Třídění distribuce rozděluje seznam vstupů ${ displaystyle A}$ velikosti ${ displaystyle N}$ do ${ displaystyle d}$ disjunktní lopaty podobné velikosti. Každý segment je poté rekurzivně tříděn a výsledky jsou sloučeny do plně seřazeného seznamu.

Li ${ displaystyle P = 1}$ úkol je delegován na algoritmus třídění jednoho procesoru s optimální úrovní mezipaměti.

Jinak následující algoritmus^[1] se používá:

// Vzorek ${ displaystyle { tfrac {4N} { sqrt {d}}}}$ prvky z ${ displaystyle A}$pro každý procesor ${ displaystyle i}$ paralelně dělat    -li ${ displaystyle M <| S_ {i} |}$ pak        ${ displaystyle d = M / B}$        Zatížení ${ displaystyle S_ {i}}$ v ${ displaystyle M}$-sized stránky a třídit stránky jednotlivě jiný        ${ displaystyle d = | S_ {i} |}$        Načíst a třídit ${ displaystyle S_ {i}}$ jako jedna stránka skončit, pokud    Vyberte každý ${ displaystyle { sqrt {d}} / 4}$První prvek z každé tříděné stránky paměti do souvislého vektoru ${ displaystyle R ^ {i}}$ vzorkůkonec pro paralelně dělat    Kombinujte vektory ${ displaystyle R ^ {1}  tečky R ^ {P}}$ do jednoho souvislého vektoru ${ displaystyle { mathcal {R}}}$    Udělat ${ displaystyle { sqrt {d}}}$ kopie ${ displaystyle { mathcal {R}}}$: ${ displaystyle { mathcal {R}} _ {1}  tečky { mathcal {R}} _ { sqrt {d}}}$konec udělej// Najít ${ displaystyle { sqrt {d}}}$ čepy ${ displaystyle { mathcal {M}} [j]}$pro ${ displaystyle j = 1}$ na ${ displaystyle { sqrt {d}}}$ paralelně dělat    ${ displaystyle { mathcal {M}} [j] = { texttt {PEMSELECT}} ({ mathcal {R}} _ {i}, { tfrac {P} { sqrt {d}}}, {  tfrac {j  cdot 4N} {d}})}$konec proBalení čepů do souvislého pole ${ displaystyle { mathcal {M}}}$// Oddíl ${ displaystyle A}$kolem čepů do kbelíků ${ displaystyle { mathcal {B}}}$${ displaystyle { mathcal {B}} = { texttt {PEMMULTIPARTITION}} (A [1: N], { mathcal {M}}, { sqrt {d}}, P)}$// Rekurzivně třídit segmentypro ${ displaystyle j = 1}$ na ${ displaystyle { sqrt {d}} + 1}$ paralelně dělat    rekurzivně volat ${ displaystyle { texttt {PEMDISTSORT}}}$ na kbelíku ${ displaystyle j}$velikosti ${ displaystyle { mathcal {B}} [j]}$    použitím ${ displaystyle O  left ( left  lceil { tfrac {{ mathcal {B}} [j]} {N / P}}  right  rceil  right)}$ procesory odpovědné za prvky v kbelíku ${ displaystyle j}$konec pro

Složitost I / O PEMDISTSORT je:

${ displaystyle O left ( left lceil { frac {N} {PB}} right rceil left ( log _ {d} P + log _ {M / B} { frac {N} { PB}} right) + f (N, P, d) cdot log _ {d} P right)}$

kde

${ displaystyle f (N, P, d) = O left ( log { frac {PB} { sqrt {d}}} log { frac {N} {P}} + left lceil { frac { sqrt {d}} {B}} log P + { sqrt {d}} log B right rceil right)}$

Pokud je zvolen počet procesorů, je to ${ displaystyle f (N, P, d) = O left ( left lceil { tfrac {N} {PB}} right rceil right)}$a ${ displaystyle M$ složitost I / O je pak:

${ displaystyle O left ({ frac {N} {PB}} log _ {M / B} { frac {N} {B}} right)}$

Další PEM algoritmy

Algoritmus PEM	Složitost I / O	Omezení
Sloučit třídění[1]	${ displaystyle O left ({ frac {N} {PB}} log _ { frac {M} {B}} { frac {N} {B}} right) = { textrm {sort} } _ {P} (N)}$	${ displaystyle P leq { frac {N} {B ^ {2}}}, M = B ^ {O (1)}}$
Seznam hodnocení[2]	${ displaystyle O left ({ textrm {sort}} _ {P} (N) right)}$	${ displaystyle P leq { frac {N / B ^ {2}} { log B cdot log ^ {O (1)} N}}, M = B ^ {O (1)}}$
Prohlídka Euler[2]	${ displaystyle O left ({ textrm {sort}} _ {P} (N) right)}$	${ displaystyle P leq { frac {N} {B ^ {2}}}, M = B ^ {O (1)}}$
Výraz strom hodnocení[2]	${ displaystyle O left ({ textrm {sort}} _ {P} (N) right)}$	${ displaystyle P leq { frac {N} {B ^ {2} log B cdot log ^ {O (1)} N}}, M = B ^ {O (1)}}$
Hledání a MST[2]	${ displaystyle O left ({ textrm {sort}} _ {P} (| V |) + { textrm {sort}} _ {P} (| E |) log { tfrac {| V |} {pB}} vpravo)}$	${ displaystyle p leq { frac {| V | + | E |} {B ^ {2} log B cdot log ^ {O (1)} N}}, M = B ^ {O (1 )}}$

Kde ${ displaystyle { textrm {sort}} _ {P} (N)}$ je čas potřebný k třídění ${ displaystyle N}$ položky s ${ displaystyle P}$ procesory v modelu PEM.

Viz také

• Paralelní stroj s náhodným přístupem (PRAM)
• Stroj s náhodným přístupem (RAM)
• Externí paměť (EM)

Reference