PD Stefan Bosse - VPP - Modul C: Parallele und Verteilte Zelluläre Automaten

Verteilte und Parallele Programmierung

Mit Virtuellen Maschinen

PD Stefan Bosse

Universität Bremen - FB Mathematik und Informatik

1 / 14

PD Stefan Bosse - VPP - Modul C: Parallele und Verteilte Zelluläre Automaten

Parallele und Verteilte Zelluläre Automaten

Wie kann das ZA Modell für die Parallelisierung und Verteilung genutzt werden?

Wie können geteilte und verteilte Speichermodelle sinnvoll eingesetzt werden?

Wie kann CALUA parallelisiert werden?

2 / 14

PD Stefan Bosse - VPP - Modul C: Parallele und Verteilte Zelluläre Automaten

Das 1:1 Modell

  • Die einzelnen Zellen eines ZA sind zunächst völlig unabhängig voneinander → Kontrollpfadparallelität

  • Die Datenabängigkeit einer Zelle ist auf die Zellen seiner unmittelbaren Umgebung beschränkt → Kurzreichweitige Datenabhängigkeit

  • Synchronisation erfolgt primär (implizit) durch einen zentralen Takt, der aber nur die einzelnen Phasen des ZA (before, activity, after) einleitet.

  • Weitere implizite Synchronisation beim Zugriff auf Zustand (Variablen) von Nachbarzellen

3 / 14

PD Stefan Bosse - VPP - Modul C: Parallele und Verteilte Zelluläre Automaten

(a) Das parallele (oder verteilte) 1:1 ZA Modell wo jede Zelle von einem physischen Prozessor ausgeführt wird → Verteiltes Speichermodell (b) Das partitionierte 1:N ZA Modell wo ein Bereich des ZA von einem Prozessor ausgeführt wird → Geteiltes und verteiltes Speichermodell

4 / 14

PD Stefan Bosse - VPP - Modul C: Parallele und Verteilte Zelluläre Automaten

Das Partitionsmodell

  • Paritionierung der Zellen des ZA in parallele Felder:

    • Jedes Feld besteht aus einer Gruppe aus Zellen Fi={zZ} ⊂ Z für sich: Ein P mit SM, Zellen eng gekoppelt
    • Alle Felder: Verteilter Zellenrechner, Multi-P, Felder lose gekoppelt über Verteilten und geteilten Speicher (DSM)
  • Man unterscheidet:

    • Kernbereiche eines Feldes (Untergruppe von Zellen aus F) mit reinem SM Modell, und
    • Überlappende Randbereiche mit DM Modell
  • Es gibt weiterhin einen gemeinsamen Takt (Synch.)

5 / 14

PD Stefan Bosse - VPP - Modul C: Parallele und Verteilte Zelluläre Automaten