PD Stefan Bosse - Modul H: Verteilte Programmierung von Sensornetzwerken
Mit Datenaggregation und Sensorfusion
PD Stefan Bosse
Universität Bremen - FB Mathematik und Informatik
PD Stefan Bosse - Modul H: Verteilte Programmierung von Sensornetzwerken
Neben P2P Kommunikation, RPC, und Gruppenkommunikation gibt es höhere Netzwerkorganisationen und Softwareframeworks
Übergang zu heterogener Cluster- und Cloud pogrammierung
Grundlagen von Map&Reduce Verfahren
Einführung in das MPI Softwareframework
Parallele und Verteilte Architekturen PD Stefan Bosse - Modul H: Verteilte Programmierung von Sensornetzwerken
Vergleich verschiedener paralleler und verteilter Berechnungssysteme [10]
Cluster Computing PD Stefan Bosse - Modul H: Verteilte Programmierung von Sensornetzwerken
Ein Computer-Cluster besteht aus miteinander verbundenen eigenständigen Computern, die kooperativ als eine einzige integrierte Computer-Ressource arbeiten.
In der Vergangenheit haben Computer-Cluster eindrucksvolle Ergebnisse bei der Bewältigung hoher Arbeitslasten mit großen Datenmengen gezeigt.
Cluster von Servern mit Disk Arrays, Hochgeschwindigkeitsverbindung, Ein- und Ausgabegeräte, und Ankopplung an das Internet [10]
Cluster Computing PD Stefan Bosse - Modul H: Verteilte Programmierung von Sensornetzwerken
Ein idealer Cluster mit mehrere Systembilder sollte zu einem Single-System-Image (SSI) zusammengeführt werden.
Cluster-Entwickler wünschen ein Cluster-Betriebssystem oder eine Middleware, um SSI auf verschiedenen Ebenen zu unterstützen, einschließlich der gemeinsamen Nutzung von CPUs, Arbeitsspeicher und E/A über alle Cluster-Knoten hinweg.
Ein SSI ist eine durch Software oder Hardware erzeugte Illusion, die eine Sammlung von Ressourcen als eine integrierte Ressource darstellt.
SSI lässt den Cluster wie eine einzige Maschine für den Benutzer erscheinen. Ein Cluster mit mehreren Systemabbildern ist nichts anderes als eine Sammlung unabhängiger Computer &arr; One Big Virtual Machine!
Cloud Computing PD Stefan Bosse - Modul H: Verteilte Programmierung von Sensornetzwerken
Nutzer können virtualisierte Ressourcen anfragen → Auslagerung von Berechnung!
Virtuelle Netzwerke PD Stefan Bosse - Modul H: Verteilte Programmierung von Sensornetzwerken
Die Struktur eines P2P-Systems durch Abbildung eines physischen IP-Netzwerks auf ein Overlay-Netzwerk mit virtuellen Verbindungen. [10]
Partitionierung und Kommunikation PD Stefan Bosse - Modul H: Verteilte Programmierung von Sensornetzwerken
Problemzerlegung durch Partitionierung → Abbildung auf Kommunikationsnetzwerke [Janetzko, MPI Practice 2014]
Gustafson Gesetz PD Stefan Bosse - Modul H: Verteilte Programmierung von Sensornetzwerken
Um bei Verwendung eines großen Clusters eine höhere Effizienz zu erzielen, muss die Größe des Problems so skalieren, dass sie der Cluster-Fähigkeit entspricht!
Gustafson Gesetz PD Stefan Bosse - Modul H: Verteilte Programmierung von Sensornetzwerken
Gustafson Gesetz PD Stefan Bosse - Modul H: Verteilte Programmierung von Sensornetzwerken
Diese skalierte Arbeitslast W* ist im Wesentlichen die sequentielle Ausführungszeit auf einem einzelnen Prozessor.
Die parallele Ausführungszeit einer skalierten Arbeitslast W* auf n Prozessoren wird wie folgt durch eine skalierte Arbeitslast-Beschleunigung definiert:
S⋆=W⋆/W=[ηW+(1−η)nW]/W=η+(1−η)n
Map & Reduce PD Stefan Bosse - Modul H: Verteilte Programmierung von Sensornetzwerken
Ein Web-Programmiermodell für die skalierbare Datenverarbeitung in großen Clustern über große Datenmengen.
Das Modell wird häufig in Web-Scale-Search- und Cloud-Computing-Anwendungen eingesetzt.
Aber auch funktionale und parallele Programmierung macht von MapReduce Methoden Gebrauch
Map & Reduce PD Stefan Bosse - Modul H: Verteilte Programmierung von Sensornetzwerken
Methode
Map & Reduce PD Stefan Bosse - Modul H: Verteilte Programmierung von Sensornetzwerken
Die Map-Funktion verarbeitet ein Paar (Schlüssel, Wert) und gibt eine Liste von Zwischenpaaren (Schlüssel, Wert) zurück:
map(k1,v1)→list(k2,v2)
Die Reduzierungsfunktion führt alle Zwischenwerte zusammen, die die gleichen Zwischenschlüssel haben:
reduce(k2,list(v2)) → list(v3)
Map & Reduce PD Stefan Bosse - Modul H: Verteilte Programmierung von Sensornetzwerken
Ausführungsphasen einer generischen MapReduce Applikation
Map & Reduce PD Stefan Bosse - Modul H: Verteilte Programmierung von Sensornetzwerken
Ein Master-Prozess erhält einen Jobdeskriptor, der den auszuführenden MapReduce-Job angibt. Der Jobdeskriptor enthält neben anderen Informationen den Ort der Eingabedaten, auf die unter Verwendung eines verteilten Dateisystems zugegriffen werden kann.
Gemäß dem Jobdeskriptor startet der Master eine Anzahl von Mapper- und Reducer-Prozessen auf verschiedenen Maschinen. Gleichzeitig startet es einen Prozess, der die Eingabedaten von seinem Speicherort liest, diese Daten in eine Gruppe von Aufteilungen unterteilt und diese Aufteilungen an verschiedene Zuordner verteilt.
Nach dem Empfang seiner Datenpartition führt jeder Zuordnungsvorgang die Zuordnungsfunktion aus (die als Teil des Jobdeskriptors bereitgestellt wird), um eine Liste von Zwischenschlüssel / Wert-Paaren zu erzeugen. Dann werden diese Paare auf der Basis ihrer Schlüssel gruppiert.
Map & Reduce PD Stefan Bosse - Modul H: Verteilte Programmierung von Sensornetzwerken
Alle Paare mit den gleichen Schlüsseln sind dem gleichen Reduziervorgang zugeordnet. Daher führt jeder Reduzierprozess die Reduktionsfunktion (definiert durch den Jobdeskriptor) aus, die alle Werte vereinigt, die mit dem gleichen Schlüssel assoziiert sind, um einen möglicherweise kleineren Satz von Werten zu erzeugen.
Dann werden die von jedem Reduktionsprozess erzeugten Ergebnisse gesammelt und an einen durch den Jobdeskriptor spezifizierten Ort geliefert, um die endgültigen Ausgabedaten zu bilden.
Map & Reduce PD Stefan Bosse - Modul H: Verteilte Programmierung von Sensornetzwerken
local options = {workers = 2}local data = {34,35,36,37,38,39,40,41}local function worker (id,set) local results = T{} for i = 1,#set do results:push(fib(set[i])) end return resultsend-- Parallel Processinglocal Parallel = require('parallel')local p = Parallel:new(data,options)function sum (x,y) return x+y endp:time(): map(worker): apply(function (r) print(r:print()) end): reduce(sum): apply(print): time()
MPI PD Stefan Bosse - Modul H: Verteilte Programmierung von Sensornetzwerken
Message Passing Interface: MPI
MPI PD Stefan Bosse - Modul H: Verteilte Programmierung von Sensornetzwerken
MPI PD Stefan Bosse - Modul H: Verteilte Programmierung von Sensornetzwerken
MPI PD Stefan Bosse - Modul H: Verteilte Programmierung von Sensornetzwerken
Kommunikationswelt mit einer Gruppe aus Prozessen die gemeinsam Nachrichten austauschen können
Nachrichten können nur innerhalb der Kommunikationswelt ausgetauscht werden
MPI_COMM_WORLD ist die Standardwelt
MPI PD Stefan Bosse - Modul H: Verteilte Programmierung von Sensornetzwerken
MPI PD Stefan Bosse - Modul H: Verteilte Programmierung von Sensornetzwerken
Kommunikation zwischen zwei Prozessen
Quellprozess sendet eine Nachricht (Typ, Daten) an einen Zielprozess unter Angabe der Rank ID
Kommunikation kann nur innerhalb eines Communicators stattfinden
MPI.send(dest:number,message:{type:string,content:string})
MPI PD Stefan Bosse - Modul H: Verteilte Programmierung von Sensornetzwerken
MPI.recv(type:string,callback:function (message))
MPI PD Stefan Bosse - Modul H: Verteilte Programmierung von Sensornetzwerken
MPI.broadcast(message:{type:string,content:string})