PD Stefan Bosse - VPP - 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?

PD Stefan Bosse - VPP - Parallele und Verteilte Zelluläre Automaten :: Das 1:1 Modell

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

PD Stefan Bosse - VPP - Parallele und Verteilte Zelluläre Automaten :: Das 1:1 Modell

(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

PD Stefan Bosse - VPP - Parallele und Verteilte Zelluläre Automaten :: Das Partitionsmodell

Das Partitionsmodell

• Partitionierung der Zellen des ZA in parallele Felder:

  • Jedes Feld besteht aus einer Gruppe aus Zellen F_i={z∈Z} ⊂ 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.)

PD Stefan Bosse - VPP - Parallele und Verteilte Zelluläre Automaten :: Das Partitionsmodell

Partitionierter ZA mit gemischten SM und DSM Modellen (Kern- und Randbereiche)

PD Stefan Bosse - VPP - Parallele und Verteilte Zelluläre Automaten :: Parallele Programmierung des ZA

Parallele Programmierung des ZA

Da das Speichermodell der Kern- und Randzellen unterschiedlich ist müsste explizit bei der Programmierung zwischen Zellen im eigenen Feld und im Nachbarfeldern unterschieden werden!

• Die Kommunikation bei Zellen innerhalb eines Feldes ist ein direkter Speicherzugriff,
  • bei verteilten Feldern (physisch getrennte Rechner) ein Nachrichtenversand (DSM),
  • und bei SM auf einem Parallelrechner (Multi-core Rechner) wieder ein direkter Speicherzugriff, aber bei Verwendung einer VM auf ein spezielles geteiltes Speicherobjekt!

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

Monitore

• Um heterogene und nicht einheitliche Programmierung (Siehe Entwurfsprinzipien von Verteilten Systemen!) können Objektmonitore eingesetzt werden
  • Sogenannte getter/setter Funktionen überwachen den Zugriff auf Feldern von Objekten (Proxy)
  • Bei Nachbarzellen innerhalb eines Feldes wird direkt auf die Objektvariablen zugegriffen
  • Bei Nachbarzellen außerhalb des Feldes wird entweder Nachrichtenkommunikation verwendet (Achtung: ausführungsblockierend!) oder bei SM auf ein spezielles geteiltes Speicherobjekt zugegriffen

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

function C:initialize (..)
    for k,v in pairs(parameter.state) do
      if shared then
        self.__state[k]=v
      else 
        self[k]=v;
      end 
    end
end
function C:__newindex( index, value )
   if index ~= '__state' and self.__state ~= nil and self.__state[index] ~= nil then
     if shared then model.shared[index]:write(value,self.y,self.x) 
     else self.__state[index] = value end
   else
     rawset( self, index, value )
   end
end
function C:__index( index )
    if index ~= '__state' and self.__state ~= nil and self.__state[index] ~= nil then
      if shared and then return model.shared[index]:read(self.y,self.x)
      else return self.__state[index] end
    else
      local value = rawget( self, index )
      if value == nil then return rawget (getmetatable(self), index)
      else return value end
    end
end

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

• Bei einem Zugriff auf die Zustandsvariablen einer Zelle, also z.B. self.open, werden die Setter und Getter Funktionen aufgerufen

• Handelt es sich um eine geteilte Randzelle und bei dem Objektzugriff um eine Zustandsvariable (aus der state Definition der Zelle), wird ein von allen Randzellen geteilter Speicher verwendet, ansonsten die lokale private Speicher einer Zelle

  • Anstelle des geteilten Speicherzugriffs könnte auch nachrichtenbasierte Kommunikation verwendet werden (read/write Remote Procedure Call)

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

Objektmonitore implementieren lokalen, geteilten, und verteilten Speicherzugriff: Virtualisierung des Speicherzugriffs durch getter und setter Methoden

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

• Aber: Sowohl der Zugriff auf geteilten (und geschützen) als auch vor allem auf verteilten Speicher verursacht erhöhte Laufzeitkosten!

• Da die Zelloperationen i.A. geringe Rechenkomplexität aufweisen kann das parallele ZA Modell schnell ineffizient werden (Skalierunsgproblem)

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

(Links) Partitionierter ZA mit lokalen und geteilten Speicher in den Randbereichen (Rechts) Prozessablaufmodell: Fork & Join Phasen (jeweils einzeln für before, activity, after)

PD Stefan Bosse - VPP - Parallele und Verteilte Zelluläre Automaten :: Multi-Computer Parallelrechner: GreenArrays GA144

Multi-Computer Parallelrechner: GreenArrays GA144

www.greenarraychips.com GA144 Array Rechner (ein Mikrochip!)

PD Stefan Bosse - VPP - Parallele und Verteilte Zelluläre Automaten :: Multi-Computer Parallelrechner: GreenArrays GA144

Der GA144 Parallelrechner bietet:

• 144 F18A FORTH Prozessoren (FORTH: Interpretersprache, stackbasiert)

  • Anordnung der einzelnen Prozessoren in einem 2D Gitter mit Nachbarknotenkommunikation
  • Pro F18A Knoten: 9k Word RAM

• 96GIPS!

• 14μW - 650mW Leistungsaufnahme

• Kein zentraler Takt! Asynchrone Digitallogik

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

Zusammenfassung