Parallel Random Access Machine

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.

Inhaltsverzeichnis

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 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 mi 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.


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Parallel Random Access Machine — In computer science, Parallel Random Access Machine (PRAM) is a shared memory abstract machine. As its name indicates, the PRAM was intended as the parallel computing analogy to the random access machine (RAM). In the same way, that the RAM is… …   Wikipedia

  • Parallel random access machine — PRAM, pour Parallel Random Access Machine, est un modèle abstrait de machine destiné à concevoir des algorithmes pour machines parallèles de modèle MIMD, ou pour de plus rares cas de modèle SIMD. PRAM modélise une machine parallèle à une mémoire… …   Wikipédia en Français

  • Random access machine — In computer science, random access machine (RAM) is an abstract machine in the general class of register machines. The RAM is very similar to the counter machine but with the added capability of indirect addressing of its registers. Like the… …   Wikipedia

  • Random access stored program machine — In theoretical computer science the Random Access Stored Program (RASP) machine model is an abstract machine used for the purposes of algorithm development and algorithm complexity theory.The RASP is a Random Access Machine (RAM) model that,… …   Wikipedia

  • Parallel programming model — A parallel programming model is a set of software technologies to express parallel algorithms and match applications with the underlying parallel systems. It encloses the areas of applications, programming languages, compilers, libraries,… …   Wikipedia

  • Dynamic random-access memory — DRAM redirects here. For other uses, see Dram (disambiguation). Computer memory types Volatile RAM DRAM (e.g., DDR SDRAM) SRAM In development T RAM Z RAM TTRAM Historical Delay line memory Selectron tube Williams tube …   Wikipedia

  • Dynamic random access memory — (DRAM) is a type of random access memory that stores each bit of data in a separate capacitor within an integrated circuit. Since real capacitors leak charge, the information eventually fades unless the capacitor charge is refreshed periodically …   Wikipedia

  • Turing machine equivalents — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… …   Wikipedia

  • Pointer machine — In theoretical computer science a pointer machine is an atomistic abstract computational machine model akin to the Random access machine.Depending on the type, a pointer machine may be called a linking automaton, a KU machine, an SMM, an… …   Wikipedia

  • Turing machine — For the test of artificial intelligence, see Turing test. For the instrumental rock band, see Turing Machine (band). Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”