imported>Gerolsteiner flasche: /* growthexperiments-addlink-summary-summary:2|0|0 */

2024-09-26T16:58:57Z

growthexperiments-addlink-summary-summary:2|0|0

Neue Seite

Als '''Parallel Random Access Machine''', kurz '''PRAM''', bezeichnet man in der [[Informatik]] einen [[Automat (Informatik)|Automaten]] zur Analyse [[Paralleler Algorithmus|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 (Computer)|Register]] gleichzeitig Berechnungen ausführen und das Ergebnis in [[Arbeitsspeicher|Speicherzellen]] ablegen können. Die PRAM dient u. a. in der [[Komplexitätstheorie]] zur Definition der Klasse [[NC (Komplexitätsklasse)|NC]] der effizient parallel [[entscheidbar]]en 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 [[Computerprogramm|Programme]] in einer höheren [[Programmiersprache]] angegeben werden können. Die parallele Verarbeitung von Befehlen kann nun durch die Einführung einer neuen [[Anweisung (Programmierung)|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 [[Feld (Datentyp)|Array]] betrachtet werden, dessen Felder mit 1 bis 100 indiziert sind. Die allgemeinere Schreibweise xi sieht von solchen [[Implementierung]]sdetails 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 <code>m</code>. Das [[Größtes und kleinstes Element|Maximum]] in einer unsortierten Liste einer beliebigen Länge n lässt sich also mit konstantem Aufwand, also in [[Landau-Notation|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 [[Variable (Programmierung)|Variablen]]. Derartige parallele Modelle bezeichnet man als ''Single Instruction Multiple Data''-Modell oder kurz [[Flynnsche Klassifikation#SIMD (Single Instruction, Multiple Data)|SIMD]]. Sind innerhalb eines Zeittaktes auch unterschiedliche Befehle erlaubt, so spricht man von einem ''Multiple Instruction Multiple Data''-Modell ([[Flynnsche Klassifikation#MIMD (Multiple Instruction, Multiple Data)|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 [[Prozessor]]en 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:<ref>{{Literatur |Autor=Jaja, J. |Titel=Introduction to Parallel Algorithms |Seiten=14-15 |Online=https://www.cs.utah.edu/~hari/teaching/bigdata/book92-JaJa-parallel.algorithms.intro.pdf}}</ref>
* 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ät (Informatik)|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.

{{Normdaten|TYP=s|GND=4361282-9}}

== Einzelnachweise ==
<references />

[[Kategorie:Theoretische Informatik]]
[[Kategorie:Parallelverarbeitung]]

Parallel Random Access Machine - Versionsgeschichte

imported>Gerolsteiner flasche: /* growthexperiments-addlink-summary-summary:2|0|0 */