RAM paralel

PRAM, Mașină paralelă cu acces aleator este un model teoretic utilizat în analiza eficienței algoritmilor paraleli. PRAM reprezintă o analogie de calcul paralel a Mașinii cu acces aleator (en. random access machine, RAM). În același mod în care RAM este utilizat de dezvoltatorii algoritmilor secvențiali pentru îmbunătățirea performanțelor, PRAM este utilizat pentru modelarea performanțelor algoritmilor. Modelul PRAM consideră că timpul de acces la memorie și costul de sincronizare sunt nule. Este utilizat pentru analiza timpului de execuție, accelerare, eficiență și scalabilitate. Acesta neglijează problemele de sincronizare și comunicare, dar oferă rezolvarea dependenței de memorie, prin utilizarea unui număr mare de procesoare. Costul algoritmilor este estimat utilizând doi parametrii: timpul și timpul multiplicat cu numărul de procesoare.

Acces concurent la memoria partajată

Memoria partajată poate fi centralizată sau distribuită. Procesoarele operează sincron operații de citire din memorie, calcule, scrieri în memorie. Un model ideal, nu încearcă modelarea unei mașini reale ci doar permite urmărirea aspectelor de concurență.

Modelul PRAM are următoarele opțiuni de acces concurent la memoria partajată:

ER (Exclusive Read) – câte o citire pe ciclu
EW (Exclusive Write) – câte o scriere pe ciclu
CR (Concurent Read) – mai multe procesoare pot citi simultan o locație de memorie
CW (Concurent Write) – mai multe procesoare pot înscrie simultan o locație de memorie

Utilizând combinații ale acestor opțiuni de acces, s-au format următoarele modele:

Exclusive Read Exclusive Write (EREW) — variantă restrictivă, fiecare celulă de memorie poate fi citită sau scrisă de către un singur procesor la un moment dat, nu simultan.
Concurrent Read Exclusive Write (CREW) — variantă bazată pe excludere mutuală: mai multe procesoare pot citi o celulă de memorie, dar numai una singură poate fi scrisă în același timp
Exclusive Read Concurrent Write (ERCW) — este o variantă rezultată pur combinațional, nu este utilizată
Concurrent Read Concurrent Write (CRCW) — mai multe procesoae pot citi sau scrie. Această variantă este numită și mașină concurentă cu acces aleator, CRCW PRAM.

Majusculele E și C semnfică 'exclusiv' și 'concurent'.

În funcție de scrierile concurente putem avea:

PRAM comun (en. Common PRAM) – toate procesoarele scriu aceeași valoare, se permit înscrieri concurente doar pentru valori identice

PRAM arbitrar (en. Arbitrary PRAM) – este înscrisă o singură valoare aleasă arbitrar, restul se ignoră

PRAM prioritar (en. Priority PRAM) – în funcție de o listă de priorități se alege valoarea care se înscrie

PRAM funcțional (en. Function PRAM) – se înscrie o valoare care rezultă din prelucrarea tuturor valorilor ce se încearcă a fi înscrise (exemplu: operații de reducere de matrice: suma, maxim, „Și logic”).

În vederea dezvoltării unui agloritm PRAM, sunt necesare următoarele:

Să nu existe limitări pentru numărul de procesoare ale mașinii.
Orice locație de memorie să accesibilă pentru orice procesor.
Să nu existe în sistem, limitări de cantitate ale memoriei partajate.
Să lipsească concurența între resurse.

Aceste tipuri de algoritmi sunt utili pentru înțelegerea noțiunii de concurență: împărțirea problemei în sub-probleme similare, și rezolvarea acestora în paralel.

Implementare

Algoritmii de eficiență PRAM, nu pot fi implementați folosind o combinare a Microprocesorului și a Memoriei dinamice cu acces aleator (en. Dynamic random-access memory, DRAM), deoarece DRAM nu permite accesul concurent, dar dacă se va implementa la nivelul componentelor sau prin citiri/scrieri către memoria internă Memorie statică cu acces aleator (en. Static random-access memory, SRAM) cu blocuri logice programabile FPGA, se poate utiliza algoritmul CRCW (citire și scriere concurentă).

Relevanța implementării unui algoritm PRAM depinde de modelul de cost oferă o îmbunatațire a calculatorului; structura unui astfel de calculator poate fi diferită de modelul abstractizat. Modelul PRAM poate realiza mai multe Fire de execuție și poate oferi viteze mari pentru acceași problemă, în comparație cu cel mai rapid program serial.