Paralelní stroj s náhodným přístupem
Ve vědě o počítačích, je paralelní RAM stroj , nebo kočárek pro krátké , je stroj pro analýzu paralelních algoritmů . Jedná se o registrační stroj , který byl rozšířen o možnost paralelního zpracování příkazů. Stejně jako u všech modelů registračních strojů existují různé varianty PRAM. Myšlenka společná pro všechny modely je, že několik registrů může provádět výpočty současně a ukládat výsledek do paměťových buněk . PRAM slouží mimo jiné. v teorii složitosti definovat třídu NC efektivně paralelních rozhodovatelných problémů.
Příklad realizace
I když registrační stroje v užším smyslu podporují pouze velmi jednoduchou sadu instrukcí , lze definovat ekvivalentní registrační stroje, jejichž programy lze specifikovat v programovacím jazyce na vysoké úrovni . Paralelní zpracování příkazů lze nyní provést zavedením nového příkazu, který vypadá asi takto:
- pro <podmínku> pardo <pokyny>
pardo znamená dělat paralelně . Příklad:
- pro i = 1 až 100 pardo x i : = 0
Tato instrukce inicializuje 100 paměťových míst s hodnotou 0 současně. Například x lze považovat za pole s poli indexovanými od 1 do 100. Obecnější notace x i neobsahuje takové podrobnosti implementace . Uvedený příklad samozřejmě nemá zvlášť velký praktický význam. Zde je tedy užitečnější příklad, který demonstruje možnosti PRAM:
Je uveden seznam n různých hodnot, které jsou uloženy netříděné v paměťových buňkách x 1 až x n . Hledáme to x i, které obsahuje největší hodnotu. Překvapivě lze toto vyhledávání provádět paralelně na PRIORITY-CRCW-PRAM (viz níže), který nevyžaduje aktivaci procesorů, pro n jakékoli velikosti v konstantním čase :
for i=1 to n pardo
bi := 1
for i,j=1 to n pardo
if xj > xi
then
bi := 0
fi
for i=1 to n pardo
if bi = 1
then
m := i
fi
Po druhé smyčce for má b i pouze hodnotu 1, pokud x i je maximum. Všechny ostatní b j s j ≠ mám hodnotu 0. I s b i = 1 je tedy hledaný index a lze jej najít po provedení programu m. Maximální v netříděné seznamu libovolné délky n mohou tedy být vypočítána s konstantní intenzity, tj. V O (1) času.
Různé modely PRAM
SIMD a MIMD PRAM
Výše popsaná instrukce pardo umožňuje simultánní provádění určité instrukce na různých proměnných v časovém cyklu . Takové paralelní modely se nazývají více datové modely s jednou instrukcí nebo zkráceně SIMD . Pokud jsou v rámci časového cyklu povoleny různé příkazy, nazývá se to vícenásobný datový model s více instrukcemi ( MIMD ). Pro takový model je prohlášení pardo definováno příliš úzce.
Současný přístup pro čtení a zápis do identických paměťových buněk
Musí být definováno, zda by měl být povolen současný přístup pro čtení a zápis do identických paměťových buněk nebo ne. Výše uvedený algoritmus pro maximální hledání vyžaduje obojí: V rámci druhé instrukce pardo jsou ke stejným paměťovým buňkám x i přistupovány současně různými procesory , aby je bylo možné navzájem porovnávat, a do paměťové buňky b i je současně přistupováno pro zápis . Ne vždy chcete dovolit takové svobody. Rozlišuje se proto:
- CRCW PRAM: Souběžné čtení, Souběžný zápis - je možný současný přístup pro čtení i zápis
- POSÁDKA PRÁCE: Souběžné čtení, exkluzivní zápis - současný přístup ke čtení, ale je povolen pouze exkluzivní přístup pro zápis
- EREW PRAM: Exkluzivní čtení, exkluzivní zápis - povolen pouze exkluzivní přístup pro čtení a zápis
Například v případě EREW může mít pouze jeden procesor přístup ke čtení nebo zápisu do konkrétní paměťové buňky. Jinak bude program ukončen .
Přístup pro zápis do CRCW
V případě CRCW PRAM je stále nutné vyjasnit, co by se mělo stát v případě současného přístupu k zápisu, když chtějí různé procesory zapisovat do paměťové buňky různé hodnoty. K dispozici jsou 3 režimy:
- common: Je povolen pouze zápis identických hodnot.
- libovolný: Je vybrána a zapsána náhodná hodnota.
- priorita: Procesor s nejnižší adresou přijímá přístup pro zápis.
Se specifickými algoritmy vedou různé variace PRAM k různým složitostem ve spotřebě zdrojů. Například výše uvedený algoritmus pro maximální vyhledávání závisí na současném přístupu pro čtení a zápis, tj. Na CRCW PRAM, jak je popsáno. Řešení v konstantním čase by nebylo možné na PRAM, který to neumožňuje. Který model PRAM si vyberete pro konkrétní vyšetřování, proto závisí na cílech analýzy, které s ním sledujete.
