Als Parallel Random Access Machine, kurz PRAM, bezeichnet man in der Informatik einen Automaten zur Analyse paralleler Algorithmen. Es handelt sich um eine Registermaschine, die um die Möglichkeit zur parallelen Verarbeitung von Befehlen erweitert wurde. Wie bei allen Registermaschinen-Modellen gibt es verschiedene Variationen der PRAM. Die allen Modellen gemeinsame Vorstellung besteht darin, dass mehrere Register gleichzeitig Berechnungen ausführen und das Ergebnis in Speicherzellen ablegen können. Die PRAM dient u. a. in der Komplexitätstheorie zur Definition der Klasse NC der effizient parallel entscheidbaren Probleme.
Beispiel für eine Realisierung
Auch wenn Registermaschinen im engeren Sinne nur einen sehr einfachen Befehlssatz unterstützen, lassen sich äquivalente Registermaschinen definieren, deren Programme in einer höheren Programmiersprache angegeben werden können. Die parallele Verarbeitung von Befehlen kann nun durch die Einführung einer neuen Anweisung erfolgen, die etwa folgendermaßen aussieht:
- for <Bedingung> pardo <Anweisungen>
pardo steht für do in parallel. Ein Beispiel:
- for i = 1 to 100 pardo xi := 0
Durch diese Anweisung werden 100 Speicherplätze gleichzeitig mit dem Wert 0 initialisiert. x kann beispielsweise als Array betrachtet werden, dessen Felder mit 1 bis 100 indiziert sind. Die allgemeinere Schreibweise xi sieht von solchen Implementierungsdetails ab. Das angegebene Beispiel ist freilich nicht von allzu hoher praktischer Bedeutung. Daher hier ein sinnvolleres Beispiel, das die Leistungsfähigkeit einer PRAM gut demonstriert:
Gegeben sei eine Liste von n verschiedenen Werten, die unsortiert in den Speicherzellen x1 bis xn abgelegt sind. Wir suchen dasjenige xi, das den größten Wert enthält. Diese Suche ist auf einer PRIORITY-CRCW-PRAM (siehe unten), die keine Aktivierung der Prozessoren erfordert, parallel überraschenderweise für beliebig große n in konstanter Zeit durchführbar:
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
Nach der zweiten for-Schleife steht nur dann noch in bi der Wert 1, wenn xi das Maximum ist. In allen anderen bj mit j≠i steht der Wert 0. Dasjenige i mit bi = 1 ist also der gesuchte Index und findet sich nach Ausführung des Programms in m. Das Maximum in einer unsortierten Liste einer beliebigen Länge n lässt sich also mit konstantem Aufwand, also in O(1) Zeit berechnen.
Unterschiedliche PRAM-Modelle
SIMD und MIMD-PRAMs
Die oben beschriebene pardo-Anweisung ermöglicht innerhalb eines Zeittaktes die gleichzeitige Ausführung eines bestimmten Befehles auf unterschiedlichen Variablen. Derartige parallele Modelle bezeichnet man als Single Instruction Multiple Data-Modell oder kurz SIMD. Sind innerhalb eines Zeittaktes auch unterschiedliche Befehle erlaubt, so spricht man von einem Multiple Instruction Multiple Data-Modell (MIMD). Die pardo-Anweisung ist für ein solches Modell zu eng definiert.
Gleichzeitige Lese- und Schreibzugriffe auf identische Speicherzellen
Es muss definiert werden, ob gleichzeitige Lese- und Schreibzugriffe auf identische Speicherzellen erlaubt sein sollen oder nicht. Der obige Algorithmus zur Maximumsuche benötigt beides: Innerhalb der zweiten pardo-Anweisung wird sowohl von verschiedenen Prozessoren gleichzeitig auf identische Speicherzellen xi zugegriffen, um diese miteinander zu vergleichen, als auch gleichzeitig schreibend auf die Speicherzelle bi zugegriffen. Derartige Freiheiten möchte man nicht immer erlauben. Man unterscheidet daher:
- CRCW PRAM: Concurrent Read, Concurrent Write – gleichzeitiger Lese- und Schreibzugriff möglich
- CREW PRAM: Concurrent Read, Exclusive Write – gleichzeitiger Lesezugriff, aber nur exklusiver Schreibzugriff erlaubt
- EREW PRAM: Exclusive Read, Exclusive Write – nur exklusiver Lese- und Schreibzugriff erlaubt
Bei einer EREW darf also beispielsweise jeweils nur ein Prozessor lesend oder schreibend auf eine bestimmte Speicherzelle zugreifen. Ansonsten kommt es zu einem Programmabbruch.
Schreibzugriffe bei CRCWs
Bei einer CRCW PRAM muss noch geklärt werden, was im Falle eines gleichzeitigen Schreibzugriffes geschehen soll, wenn verschiedene Prozessoren verschiedene Werte in die Speicherzelle schreiben wollen. Man unterscheidet 3 Modi:
- common: Nur das Schreiben identischer Werte ist erlaubt.
- arbitrary: Ein zufälliger Wert wird ausgewählt und geschrieben.
- priority: Der Prozessor mit der niedrigsten Adresse erhält das Schreibrecht.
Die unterschiedlichen Variationen der PRAM führen bei konkreten Algorithmen zu unterschiedlichen Komplexitäten im Ressourcenverbrauch. So ist der oben angegebene Algorithmus zur Maximumsuche wie beschrieben auf gleichzeitigen Lese- und Schreibzugriff angewiesen, also auf eine CRCW PRAM. Auf einer PRAM, die dies nicht erlaubt, wäre eine Lösung in konstanter Zeit nicht möglich. Welches PRAM-Modell man für eine konkrete Untersuchung auswählt, hängt also von den Analysezielen ab, die man damit verfolgt.