Opis maszyny typu PRAM

Podstawowym modelem służącym do badań algorytmów równoległych jest maszyna typu PRAM¹ ([4]). Jej głównymi składnikami są globalna pamięć oraz zbiór procesorów. Do rozważań teoretycznych przyjmuje się, że zbiór procesorów oraz zasoby pamięci są potencjalnie nieskończone, jednak w skończonych obliczeniach wykorzystuje się jedynie skończony ich podzbiór. Oto podstawowe cechy maszyny tego typu:

1. Wszystkie procesory są taktowane jednym zegarem systemowym. PRAM może być maszyną typu SIMD² lub MIMD³ , przy czym standardowe algorytmy są projektowane na pierwszy z wymienionych typów. Oznacza to, że w danej chwili wszystkie procesory wykonują dokładnie taki sam program operując na różnych danych lub pozostają w stanie oczekiwania. W implementacjach sprzętowych to założenie zazwyczaj jest realizowane programowo, ponieważ nie można zapewnić synchronizacji lepszej niż na poziomie pojedynczego rozkazu procesora.
2. Każdy procesor jest identyfikowany przez swój numer, zwany także indeksem. Jest on unikatowy w skali danej maszyny. Jest on także dostępny dla kodu programu (najczęściej jako stała) i na jego podstawie zazwyczaj określa się zakres prac przewidzianych dla danego procesora.
3. Każdy procesor posiada własną pamięć podręczną o dostępie swobodnym.
4. Wszystkie procesory mogą komunikować się bezpośrednio z globalną pamięcią dzieloną dostępną dla wszystkich jednostek. W zależności od potrzeb zapewnia się przy tym możliwość jednoczesnego dostępu do tej samej komórki pamięci (przy zapisie wprowadza się strategie określające, które dane zostaną w takiej sytuacji zapisane) lub np. zabrania jednoczesnego odczytu i/lub zapisu przez kilka procesorów (maszyny typu EREW⁴ , CREW⁵ , CRCW⁶ ).

Schemat budowy takiej maszyny przedstawia rysunek 1.

Rysunek 1: Schemat budowy maszyny typu PRAM

 

Taki model ma następujące zalety:

1. Istnieje wiele technik i metod pozwalających rozwiązywać problemy pochodzące z różnych klas algorytmów.
2. Nie ma potrzeby zajmowania się problemami synchronizacji i komunikacji. Pozwala to na skoncentrowanie się na istotnych elementach algorytmu.
3. W prosty sposób można ocenić efektywność danego algorytmu.