PD Stefan Bosse - VPP - Modul C: Parallele und Verteilte Zelluläre Automaten
Mit Virtuellen Maschinen
PD Stefan Bosse
Universität Bremen - FB Mathematik und Informatik
PD Stefan Bosse - VPP - Modul C: 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 - Modul C: Parallele und Verteilte Zelluläre Automaten
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 - 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
PD Stefan Bosse - VPP - Modul C: Parallele und Verteilte Zelluläre Automaten
Paritionierung der Zellen des ZA in parallele Felder:
Man unterscheidet:
Es gibt weiterhin einen gemeinsamen Takt (Synch.)
PD Stefan Bosse - VPP - Modul C: Parallele und Verteilte Zelluläre Automaten
Partitionierter ZA mit gemischten SM und DSM Modellen (Kern- und Randbereiche)
PD Stefan Bosse - VPP - Modul C: Parallele und Verteilte Zelluläre Automaten
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!
PD Stefan Bosse - VPP - Modul C: Parallele und Verteilte Zelluläre Automaten
PD Stefan Bosse - VPP - Modul C: Parallele und Verteilte Zelluläre Automaten
function C:initialize (..) for k,v in pairs(parameter.state) do if shared then self.__state[k]=v else self[k]=v; end endendfunction 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 ) endendfunction 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 endend
Lua Objektmonitor mit Objektgetter und Settergateways. Bei geteilten Zellen werden die Zellzustandsvariablen (state) in einem Hintergrundobjekt verwaltet.
PD Stefan Bosse - VPP - Modul C: Parallele und Verteilte Zelluläre Automaten
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
PD Stefan Bosse - VPP - Modul C: Parallele und Verteilte Zelluläre Automaten
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 - Modul C: Parallele und Verteilte Zelluläre Automaten
(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 - Modul C: Parallele und Verteilte Zelluläre Automaten
www.greenarraychips.com GA144 Array Rechner (ein Mikrochip!)
PD Stefan Bosse - VPP - Modul C: Parallele und Verteilte Zelluläre Automaten
Der GA144 Parallelrechner bietet:
144 F18A Forth Prozessoren (Forth: Interpretersprache, stackbasiert)
96GIPS!
14μW - 650mW Leistungsaufnahme
Kein zentraler Takt! Asynchrone Digitallogik