Paralel harici bellek - Parallel external memory

PEM Modeli

Bilgisayar biliminde, bir paralel harici bellek (PEM) modeli bir önbelleğe duyarlı, harici bellek soyut makine.^[1] Tek işlemciye paralel hesaplama benzetmesidir harici hafıza (EM) modeli. Benzer bir şekilde, önbelleğe duyarlı bir analojidir. paralel rasgele erişimli makine (PRAM). PEM modeli, ilgili özel önbellekleri ve paylaşılan bir ana bellek ile birlikte bir dizi işlemciden oluşur.

Modeli

Tanım

PEM modeli^[1] EM modeli ile PRAM modelinin bir kombinasyonudur. PEM modeli, aşağıdakilerden oluşan bir hesaplama modelidir: ${ displaystyle P}$ işlemciler ve iki seviyeli bellek hiyerarşisi. Bu bellek hiyerarşisi büyük bir harici hafıza (ana hafıza) boyutunda ${ displaystyle N}$ ve ${ displaystyle P}$ küçük dahili anılar (önbellekler). İşlemciler ana belleği paylaşır. Her önbellek tek bir işlemciye özeldir. Bir işlemci başka birinin önbelleğine erişemez. Önbelleklerin boyutu var ${ displaystyle M}$ boyut bloklarına bölünmüş olan ${ displaystyle B}$. İşlemciler yalnızca önbelleğinde bulunan veriler üzerinde işlem yapabilir. Veriler, boyut blokları halinde ana bellek ile önbellek arasında aktarılabilir ${ displaystyle B}$.

G / Ç karmaşıklığı

karmaşıklık ölçüsü PEM modelinin G / Ç karmaşıklığı^[1], ana bellek ile önbellek arasındaki paralel blok aktarımlarının sayısını belirleyen. Paralel blok aktarımı sırasında her işlemci bir bloğu aktarabilir. Öyleyse ${ displaystyle P}$ işlemciler aynı boyutta bir veri bloğu yükler ${ displaystyle B}$ ana hafızayı önbelleklerine dönüştürdüğünde, bir G / Ç karmaşıklığı olarak kabul edilir ${ displaystyle O (1)}$ değil ${ displaystyle O (P)}$. PEM modelindeki bir program, ana bellek ile önbellekler arasındaki veri aktarımını en aza indirmeli ve önbellekteki veriler üzerinde mümkün olduğunca çok çalışmalıdır.

Çakışmaları oku / yaz

PEM modelinde, doğrudan iletişim ağı P işlemciler arasında. İşlemcilerin ana bellek üzerinden dolaylı olarak iletişim kurması gerekir. Birden fazla işlemci ana bellekte aynı bloğa aynı anda erişmeye çalışırsa okuma / yazma çakışmaları^[1] meydana gelir. PRAM modelinde olduğu gibi, bu problemin üç farklı çeşidi dikkate alınır:

• Eşzamanlı Okuma Eşzamanlı Yazma (CRCW): Ana bellekteki aynı blok aynı anda birden çok işlemci tarafından okunabilir ve yazılabilir.
• Eşzamanlı Okuma Özel Yazma (CREW): Ana bellekteki aynı blok aynı anda birden fazla işlemci tarafından okunabilir. Bir seferde yalnızca bir işlemci bir bloğa yazabilir.
• Exclusive Read Exclusive Write (EREW): Ana bellekteki aynı blok aynı anda birden çok işlemci tarafından okunamaz veya yazılamaz. Aynı anda bir bloğa yalnızca bir işlemci erişebilir.

Aşağıdaki iki algoritma^[1] CREW ve EREW problemini çözerseniz ${ displaystyle P leq B}$ işlemciler aynı bloğa aynı anda yazar. İlk yaklaşım, yazma işlemlerini serileştirmektir. Birbiri ardına yalnızca bir işlemci bloğa yazar. Bu toplamda sonuçlanır ${ displaystyle P}$ paralel blok transferleri. İkinci bir yaklaşımın ihtiyacı ${ displaystyle O ( log (P))}$ paralel blok aktarımları ve her işlemci için ek bir blok. Ana fikir, yazma işlemlerini bir ikili ağaç modası ve verileri kademeli olarak tek bir blokta birleştirin. İlk turda ${ displaystyle P}$ işlemciler bloklarını birleştirerek ${ displaystyle P / 2}$ bloklar. Sonra ${ displaystyle P / 2}$ işlemciler ${ displaystyle P / 2}$ Bloklar ${ displaystyle P / 4}$. Bu prosedür, tüm veriler tek bir blokta birleştirilene kadar devam eder.

Diğer modellerle karşılaştırma

Örnekler

Çok yollu bölümleme

İzin Vermek ${ displaystyle M = {m_ {1}, ..., m_ {d-1} }}$ artan sırada sıralanmış d-1 pivotlarının bir vektörü olabilir. İzin Vermek ${ displaystyle A}$ sırasız bir N eleman kümesi olabilir. Bir d-yollu bölüm^[1] nın-nin ${ displaystyle A}$ bir set ${ displaystyle Pi = {A_ {1}, ..., A_ {d} }}$ , nerede ${ displaystyle cup _ {i = 1} ^ {d} A_ {i} = A}$ ve ${ displaystyle A_ {i} cap A_ {j} = emptyset}$ için ${ displaystyle 1 leq i$. ${ displaystyle A_ {i}}$ i-inci kova denir. İçindeki elemanların sayısı ${ displaystyle A_ {i}}$ daha büyüktür ${ displaystyle m_ {i-1}}$ ve daha küçük ${ displaystyle m_ {i} ^ {2}}$. Aşağıdaki algoritmada^[1] giriş N / P boyutlu bitişik segmentlere bölünmüştür ${ displaystyle S_ {1}, ..., S_ {P}}$ ana bellekte. İşlemci i öncelikle segmentte çalışır ${ displaystyle S_ {i}}$. Çok yollu bölümleme algoritması (PEM_DIST_SORT^[1]) bir PEM kullanır önek toplamı algoritma^[1] önek toplamını optimal ile hesaplamak için ${ displaystyle O ({ frac {N} {PB}} + log (P))}$ G / Ç karmaşıklığı. Bu algoritma, optimal bir PRAM önek toplam algoritmasını simüle eder.

// Veri segmentlerinde d-yollu bir bölümü paralel olarak hesaplayın ${ displaystyle S_ {i}}$her biri için işlemci i paralel olarak yap    Pivotların vektörünü okuyun ${ displaystyle M}$ önbelleğe. Bölüm ${ displaystyle S_ {i}}$ d kovalara ve vektör ${ displaystyle M_ {i} =  {j_ {1} ^ {i}, ..., j_ {d} ^ {i} }}$ her bir paketteki öğe sayısı olacaktır.sonu içinVektör kümesinde PEM önek toplamını çalıştırın ${ displaystyle  {M_ {1}, ..., M_ {P} }}$ eşzamanlı olarak.// Son bölümü hesaplamak için önek toplam vektörünü kullanınher biri için işlemci i paralel olarak yap    Öğeleri yazın ${ displaystyle S_ {i}}$ bellek konumlarına uygun şekilde dengelenmiştir. ${ displaystyle M_ {i-1}}$ ve ${ displaystyle M_ {i}}$.sonu içinİçinde depolanan önek toplamlarını kullanma ${ displaystyle M_ {P}}$ son işlemci P vektörü hesaplar ${ displaystyle B}$ kova boyutları ve döndürür.

Vektörü ${ displaystyle d = O ({ frac {M} {B}})}$ pivotlar M ve giriş kümesi A bitişik bellekte bulunur, daha sonra d-yollu bölümleme sorunu PEM modelinde çözülebilir. ${ displaystyle O ({ frac {N} {PB}} + lceil { frac {d} {B}} rceil> log (P) + d log (B))}$ G / Ç karmaşıklığı. Nihai paketlerin içeriği bitişik bellekte yer almalıdır.

Seçimi

seçim problemi sırasız bir listede k'inci en küçük öğeyi bulmakla ilgilidir ${ displaystyle A}$ boyut ${ displaystyle N}$Aşağıdaki kod^[1] kullanır PRAMSORT PRAM optimum sıralama algoritması olan ${ displaystyle O ( log N)}$, ve SEÇ, önbellek için en uygun tek işlemci seçim algoritmasıdır.

Eğer ${ displaystyle N  leq P}$ sonra     ${ displaystyle { texttt {PRAMSORT}} (A, P)}$    dönüş ${ displaystyle A [k]}$eğer biterse // Her birinin medyanını bulun ${ displaystyle S_ {i}}$her biri için işlemci ${ displaystyle i}$ paralel olarak yap     ${ displaystyle m_ {i} = { texttt {SELECT}} (S_ {i}, { frac {N} {2P}})}$sonu için // Medyanları sırala${ displaystyle { texttt {PRAMSORT}} ( lbrace m_ {1},  dots, m_ {2}  rbrace, P)}$// Medyanların medyanı etrafında bölümleme${ displaystyle t = { texttt {PEMPARTITION}} (A, m_ {P / 2}, P)}$Eğer ${ displaystyle k  leq t}$ sonra     dönüş ${ displaystyle { texttt {PEMSELECT}} (A [1: t], P, k)}$Başka     dönüş ${ displaystyle { texttt {PEMSELECT}} (A [t + 1: N], P, k-t)}$eğer biterse

Girişin bitişik bellekte saklandığı varsayımı altında, PEMSELECT G / Ç karmaşıklığına sahiptir:

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

Dağıtım sıralaması

Dağıtım sıralaması bir giriş listesini bölümler ${ displaystyle A}$ boyut ${ displaystyle N}$ içine ${ displaystyle d}$ benzer boyutta ayrık kovalar. Her kova daha sonra yinelemeli olarak sıralanır ve sonuçlar tam sıralı bir liste halinde birleştirilir.

Eğer ${ displaystyle P = 1}$ görev, önbellek için en uygun tek işlemcili sıralama algoritmasına delege edilmiştir.

Aksi takdirde aşağıdaki algoritma^[1] kullanıldı:

// Örneklem ${ displaystyle { tfrac {4N} { sqrt {d}}}}$ öğelerden ${ displaystyle A}$için her biri işlemci ${ displaystyle i}$ paralel olarak yap    Eğer ${ displaystyle M <| S_ {i} |}$ sonra        ${ displaystyle d = M / B}$        Yük ${ displaystyle S_ {i}}$ içinde ${ displaystyle M}$boyutlu sayfalar ve sayfaları ayrı ayrı sıralayın Başka        ${ displaystyle d = | S_ {i} |}$        Yükle ve sırala ${ displaystyle S_ {i}}$ tek sayfa olarak eğer biterse    Her birini seç ${ displaystyle { sqrt {d}} / 4}$her sıralı bellek sayfasından bitişik vektöre ait 'inci öğe ${ displaystyle R ^ {i}}$ örneklerinsonu için paralel olarak yap    Vektörleri birleştir ${ displaystyle R ^ {1}  noktalar R ^ {P}}$ tek bir bitişik vektöre ${ displaystyle { mathcal {R}}}$    Yapmak ${ displaystyle { sqrt {d}}}$ Kopyaları ${ displaystyle { mathcal {R}}}$: ${ displaystyle { mathcal {R}} _ {1}  dots { mathcal {R}} _ { sqrt {d}}}$bitirmek// Bul ${ displaystyle { sqrt {d}}}$ pivotlar ${ displaystyle { mathcal {M}} [j]}$için ${ displaystyle j = 1}$ -e ${ displaystyle { sqrt {d}}}$ paralel olarak yap    ${ displaystyle { mathcal {M}} [j] = { texttt {PEMSELECT}} ({ mathcal {R}} _ {i}, { tfrac {P} { sqrt {d}}}, {  tfrac {j  cdot 4N} {d}})}$sonu içinBitişik dizide pivotları paketleyin ${ displaystyle { mathcal {M}}}$// Bölme ${ displaystyle A}$pivotlar etrafında kovalar halinde ${ displaystyle { mathcal {B}}}$${ displaystyle { mathcal {B}} = { texttt {PEMMULTIPARTITION}} (A [1: N], { mathcal {M}}, { sqrt {d}}, P)}$// Paketleri yinelemeli olarak sıralayıniçin ${ displaystyle j = 1}$ -e ${ displaystyle { sqrt {d}} + 1}$ paralel olarak yap    özyinelemeli çağrı ${ displaystyle { texttt {PEMDISTSORT}}}$ kova üzerinde ${ displaystyle j}$boyut ${ displaystyle { mathcal {B}} [j]}$    kullanma ${ displaystyle O  sol ( sol  lceil { tfrac {{ mathcal {B}} [j]} {N / P}}  sağ  rceil  sağ)}$ kovadaki öğelerden sorumlu işlemciler ${ displaystyle j}$sonu için

G / Ç karmaşıklığı PEMDISTSORT dır-dir:

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

nerede

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

İşlemci sayısı seçilirse ${ Displaystyle f (N, P, d) = O sol ( sol lceil { tfrac {N} {PB}} sağ rceil sağ)}$ve ${ displaystyle M$ G / Ç karmaşıklığı şu durumda:

${ displaystyle O sol ({ frac {N} {PB}} log _ {M / B} { frac {N} {B}} sağ)}$

Diğer PEM algoritmaları

PEM Algoritması	G / Ç karmaşıklığı	Kısıtlamalar
Birleşme[1]	${ displaystyle O sol ({ frac {N} {PB}} log _ { frac {M} {B}} { frac {N} {B}} sağ) = { textrm {sıralama} } _ {P} (N)}$	${ displaystyle P leq { frac {N} {B ^ {2}}}, M = B ^ {O (1)}}$
Liste sıralaması[2]	${ displaystyle O sol ({ textrm {sıralama}} _ {P} (N) sağ)}$	${ displaystyle P leq { frac {N / B ^ {2}} { log B cdot log ^ {O (1)} N}}, M = B ^ {O (1)}}$
Euler turu[2]	${ displaystyle O sol ({ textrm {sıralama}} _ {P} (N) sağ)}$	${ displaystyle P leq { frac {N} {B ^ {2}}}, M = B ^ {O (1)}}$
İfade ağacı değerlendirme[2]	${ displaystyle O sol ({ textrm {sıralama}} _ {P} (N) sağ)}$	${ displaystyle P leq { frac {N} {B ^ {2} log B cdot log ^ {O (1)} N}}, M = B ^ {O (1)}}$
Bir MST[2]	${ displaystyle O sol ({ textrm {sıralama}} _ {P} (| V |) + { textrm {sıralama}} _ {P} (| E |) log { tfrac {| V |} {pB}} sağ)}$	${ displaystyle p leq { frac {| V | + | E |} {B ^ {2} log B cdot log ^ {O (1)} N}}, M = B ^ {O (1 )}}$

Nerede ${ displaystyle { textrm {sıralama}} _ {P} (N)}$ sıralamak için gereken zamandır ${ displaystyle N}$ ile öğeler ${ displaystyle P}$ PEM modelindeki işlemciler.

Ayrıca bakınız