Parallel Random Access Machine

Als Parallel Random Access Machine, kurz PRAM, bezeichnet man ein Maschinenmodell zur Analyse paralleler Algorithmen. Es handelt sich um eine Registermaschine, die um die Möglichkeit zur parallelen Verarbeitung von Befehlen erweitert wurde. Wie auch bei den 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 x_i := 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 x_i 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 x₁ bis x_n abgelegt sind. Wir suchen dasjenige x_i, 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 b_i der Wert 1, wenn x_i das Maximum ist. In allen anderen b_j mit j≠i steht der Wert 0. Dasjenige i mit b_i = 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 ersten pardo-Anweisung wird von verschiedenen Prozessoren gleichzeitig auf identische Speicherzellen zugegriffen, um diese miteinander zu vergleichen. Innerhalb der zweiten pardo-Anweisung wird hingegen gleichzeitig schreibend auf die Speicherzelle m_i zugegriffen. Eine derartige Freiheit 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
• ERCW PRAM: Exclusive Read, Concurrent Write - exklusiver Lese-, aber gleichzeitiger 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 somit 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.