View
216
Download
0
Category
Preview:
Citation preview
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6. Organic Computing
Organic Computing: Forschungsinitiative für eingebettete Systeme
6.1 Grundlagen des Organic Computing
6.2 Organic Computing und Systems on Chip
6.3 Organic Computing und Middleware
6.4 Ein künstliche Hormonsystem zur Taskzuordnung in verteilten eingebetteten Systemen
1
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6. Organic Computing
Problem: Durch steigende Komplexität werden Entwicklung, Wartung und Betrieb von eingebetteten Systemen immer schwieriger
Idee: Systeme „lebensähnlicher“ zu gestalten => Organic Computing
Realisierung von Eigenschaften organischer Einheiten wie:
Selbstorganisation
Selbstkonfiguration Selbstoptimierung Selbstheilung Selbstschutz Selbsterklärung Selbstbewusstsein
Selbst-X
Selbstorganisation und Organic Computing
2
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.1 Grundlagen des Organic Computing
Ein Organic Computing System ist kein biologisches, sondern immer noch ein technisches System
Es verwendet aber in biologischen Systemen beobachtete Prinzipien wie dynamische Anpassung an die Umgebungsbedingungen durch die genannten Selbst-X Eigenschaften
Das Ziel von Organic Computing ist somit die technische Nutzung von Prinzipien aus der Biologie
Hierdurch soll die Entwicklung komplexer eingebettere Systeme verbessert und erleichtert werden
3
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.1 Grundlagen des Organic Computing
Einige wichtige Begriffe:
Selbstorganisation bezieht sich auf einen Prozess, bei dem sich dieinterne Ordnung eines Systems selbsttätig und ohne äußeren Eingriff erhöht.
Selbstorganisation benutzt üblicherweise vier grundlegende „Zutaten“:
Positive Rückkopplung
Negative Rückkopplung
Gleichgewicht von Nutzung und Erforschung
Vielfältige Interaktionen
4
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.1 Grundlagen des Organic Computing
In sich selbst organisierenden Systemen kann oft emergentes Verhaltenbeobachtet werden
Beispiele: das Auffinden kürzester Wege durch Ameisenkolonien„Stöckchen sammeln“ von Termiten
In der Biologie ist Selbstorgansiation meist verbunden mit:
Morphogenese, (Entwicklung und Wachstum lebender Organismen)
Homeostase (Selbsterhaltende Natur von Systemen von der Zelle bis zum Organismus)
Schwarmverhalten (Vögel, Fische, ...)
Selbstorganisation findet sich auch in der Physik:
z.B. Strukturbildung in der Astrophysik (Sterne, Galaxien, ...)
5
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.1 Grundlagen des Organic Computing
Verbreiteter technischer Ansatz: Observer/Controller Struktur
Rückführung (Verwandtschaft zur Regelungstechnik)
Kontrolle emergenten Verhaltens
ObserverController
System
6
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.1 Grundlagen des Organic Computing
Forschungsaktivitäten / Stand der Forschung G. Jetschke. Mathematik der Selbstorganisation, Harry Deutsch
Verlag, Frankfurt, 1989 R. Whitaker. Self-Organization, Autopoiesis, and Enterprises,
http://www.acm.org/sigs/sigois/auto/Main.html/ IBM. Autonomic Computing,
http://www.research.ibm.com/autonomic/ EU-Program FET – Complex Systems:
http://www.cordis.lu/ist/fet/co.htm BMBF Programm "Technische Anwendung der Selbstorganisation„
http://www.bmbf.de/foerderungen/5150.php SFB 637: Selbststeuerung logistischer Prozesse
http://www.sfb637.uni-bremen.de Graduiertenkolleg 1194 Selbstorganisierende Sensor-Aktor-
Netzwerke http://www.grk1194.uni-karlsruhe.de/home.php DFG Schwerpunktprogramm 1183 Organic Computing
http://www.organic-computing.de/SPP 7
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.1 Grundlagen des Organic Computing
DFG Schwerpunktprogramm 1183 “Organic Computing”
Quelle: DFG Forschungsschwerpunkt 1183
8
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.2 Organic Computing und Systems on Chip
Künftige Systems On Chip (SoC) sind gekennzeichnet durch:
zunehmende Komplexität auf dem Chip (Integrationsdichte)
zunehmende Komplexität der Vernetzung (verteilte SoC)
zunehmende Komplexität der Aufgaben (Software)
die daraus resultieren Probleme im Bereich Konfiguration, Wartung, Fehleranfälligkeit, ... machen künftige SoC zu einem idealen Kandiaten für Organic Computing Techniken
9
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.2 Organic Computing und Systems on Chip
6.2.1 Autonomic Systems on Chip (ASoC)
o Problem:hohe Integrationsdichtenverursachen zunehmend transiente Fehler während des Betriebs
o Idee: 2 Ebenen
o Funktionale Ebene:Eigentliche Chip-Funktionalität
o Autonomic Ebene:Überwachung der funktionalen Ebene
AE AE
AE AE
AE AE
Prozessorkern
RAM ROM
Ein-/Ausgabe
Prozessorkern
Netzwerk
. . . . . .
. . . . . .
Autonomic Ebene
Funktionale Ebene
AE (Autonomic Element) Aktuator
Evaluator Monitor
Schnittstelle
(Univ. München, Tübingen, FZI Karlsruhe)
10
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.2 Organic Computing und Systems on Chip
Entwurfsprozess:
o Abbildung der Anwendungs-anforderungen auf die Architektur-Charakteristiken
o Auswahl der funktionalen Elemente
o Auswahl dazu passender Autonomic Elemente
o Parametrierung der Elemente
o Ableitung eines Modells zur Systemevaluation
o Fortlaufende Verfeinerung
Architektur-Charakteristiken
Funktionale
Elemente (FE)
Autonomic Elemente
(AE)
Anwendungs- und
Anforderungs-Charakteristiken
Parameterauswahl FE / AE
Modell FE / AE
Evaluation
Parameter- Evaluation
11
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.2 Organic Computing und Systems on Chip
6.2.2 Connective Autonomic Real-time Systems on Chip (CARSoC)
o vernetzte Systems on Chip
Mehrfädiger Prozessor-kern (SMT)
Echtzeit-scheduling
lokale und globale Regel-kreise für Organic Management
dezentrale Regelkreise
(Univ. Augsburg, Karlsruhe, Frankfurt) 12
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.2 Organic Computing und Systems on Chip
CARSoC Hardware
13
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.3 Organic Computing und Middleware
Wie kann Middleware bei Organic Computing helfen?Sie kann verteilten Systemen Selbst-X Eigenschaften verleihen
Dienst A
Rechen-Ressource1
Dienst B
Dienst C
Rechen-Ressource2 . . .
Middleware
Dienst D
Selbst-Konfiguration
Selbst-Optimierung
Selbst-Heilung
Selbst-Schutz… …
Zuordnung Dienste an RessourcenZuordnung Aufträge an Dienste
Auftrag
Vergabe von Prioritäten, GP-Werten, Bandbreiten, Taktfrequenzen, ...
Optimierung von Dienst- und Auftragszuordnung
Optimierung Prioritäten, GP-Werten, Bandbreiten, Taktfrequenzen, ...
Dienstverlagerung bei Ressourecanausfall
Aufspüren fremder Dienste und Aufträge, z.B. durch Computerimmunologie
14
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.3 Organic Computing und Middleware
Organic Management
Auftrag
Dienst
Ressource
bestimmt, welcher Auftrag von welchem Dienst ausgeführt wird
bestimmt, welcher Dienst auf welcher Ressource abläuft
15
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.3 Organic Computing und Middleware
6.3.1 OSA+ als „organische Middleware“, neue Konzepte, Organic Manager
Die Anwendung bestimmt, welche Ressourcen oder Ressourcenklassen für einen Dienst in Frage kommen
Der Organic Manager wählt hieraus durch Auswertung einer Kosten/Nutzenfunktion die aktuelle Ressource aus
Ressource 1
Ressource 2
Ressource 3
Ressource 3
. . .
Middleware, verteilter Organic Manager (Ortsauswahl von Diensten auf Grund von Kosten/Nutzen und Parameter aus dem Monitoring wie
Knotenauslastung, Energievorrat, ...)
Dienst A Knoten 1: Kosten/Nutzen Knoten 2: Kosten/Nutzen Knoten 3: Kosten/Nutzen
Dienst B Knoten 3: Kosten/Nutzen Knoten 4: Kosten/Nutzen
... Knoten n: Kosten/Nutzen
16
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.3 Organic Computing und Middleware
Die Anwendung bestimmt eine Menge von Diensten, die für einen Auftrag in Frage kommen
Der Organic Manager wählt hieraus durch Auswertung einer Kosten/Nutzenfunktion den aktuellen Dienst aus
Auftraggeber
Dienst A Dienst C
Dienst B
Auftrag
Dienst A: Kosten/Nutzen Dienst B : Kosten/Nutzen Dienst C: Kosten/Nutzen
Middleware, verteilter Organic Manager (Dienstauswahl für Jobs auf Grund von Kosten/Nutzen und Parameter aus dem Monitoring wie
Knotenauslastung, Energievorrat, ...)
17
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.3 Organic Computing und Middleware
Die Anwendung kann darüber hinaus Abhängigkeiten definieren:
Dienstabhängigkeit: Auftrag X und Y müssen vom selben Dienst ausgeführt werden
Ressourcenabhängigkeit: Auftrag X und Y müssen auf der selben Ressource ausgeführt werden
Zeitliche Abhängigkeit: Auftrag X muss vor Auftrag Y ausgeführt werden
18
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.3 Organic Computing und Middleware
Ausführungspfad:Ein Ausführungspfad besteht aus einer Menge von Aufträgen, welche genau auf einer Ressource in einer vorgegebenen Reihenfolge ausgeführt werden müssen.
Mission:Eine Mission besteht aus einer Anzahlvon Ausführungspfaden.
Beispiel:
Mission
Ausführungs-pfad
Ausführungs- pfad
AuftragfahreZu(Ziel)
AuftragfahreZu(Lager)
Auftrag lade(auf)
Auftraglade(ab)
19
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.3 Organic Computing und Middleware
Die Middleware erhält von der Anwendung die Ausführungspfade einer Mission
Bsp: Beladung von Paletten durch Roboter mit gleichzeitiger Prozessvisualisierung
Ausführungspfad 1: Fahre zum Lager, Greife Produkt 1, Fahre zur Ziel, Lade Produkt 1 ab
Ausführungspfad 2: Fahre zum Lager, Greife Produkt 2, Fahre zur Ziel, Lade Produkt 2 ab
Ausführungspfad 3: Visualisiere Position der Roboter
Ausführungspfad 4: Visualisiere Füllgrad Lager
....
Die Ausführungspfade und elementaren Aufträge werden vom Organic Management nach Auswertung der Kosten/Nutzenfunktionen den Diensten und Ressourcen zugeordnet
Bsp: Ausführungspfad 1 Roboter A, Fahre zum Lager Dienst Energieeffizientes Fahren, ...
Ausführungspfad 2 Roboter B, Fahre zum Lager Dienst Schnelles Fahren, ...
Ausführungspfad 3 PDA, Visualisiere Position Dienst Prozessvisualisierung
Ausführungspfad 4 PDA, Visualisiere Füllgrad Dienst Prozessvisualisierung
20
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.3 Organic Computing und Middleware
Die Anwendung gibt somit den Spielraum für den Organic Manager vor
=> der Entwickler gibt Randbedingungen vor, das Organic Management erledigt die Details (Selbst-X)
Weiterhin kann sie die Parameter der Kosten/Nutzenfunktion beeinflussen oder hier eigene Module (Verhandlungsstrategien) definieren
Vorgaben der Anwendung zur Ortsauswahl von Diensten
Vorgaben der Anwendung zur Dienstauswahl von Aufträgen
mögliche Ressourcen
mögliche Dienste
21
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.3 Organic Computing und Middleware
Zuordnung der Ausführungspfade an Ressourcen über einen Entscheidungsbaum
AP1 AP1 AP1
AP2AP2AP2
R1 R2 R3
R1 R2 R1
kn11 kn12 kn13
kn21 kn22 kn23 knij: Kosten/Nutzen-Parameter
Selbst-Konfiguration
Dynamischer Vorgang, Neuzuordnung auf Grund vom Monitoring gemeldeter Ereignisse möglich (z.B. Energieknappheit, Ressourcenausfall, ...) Selbst-Optimierung, Selbst-Heilung
22
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.3 Organic Computing und Middleware
Echtzeitaspekte:
Baumaufbau kann jederzeit unterbrochen werden
Muss eine Zuordnung getroffen werden, bevor der Baumaufbau abgeschlossen ist
=> Auswahl der momentan besten Lösung
=> Suboptimales Verhalten, aber Einhaltung der Zeitbedingungen
23
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.3 Organic Computing und Middleware
Erweiterungsmöglichkeit :
Vorhersage des Zustandes von Ressourcen nach virtueller Ausführung eines Ausführungspfades
Anfangszustand
R 1 R 2 R 3
Vorhersage Virtueller Zustand
R 1 R 2 R 3
24
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.3 Organic Computing und Middleware
Möglichkeiten der Zustandsvorhersage: Vorgabe relativer Werte durch die Anwendung
die Änderung von Zustandswerten wird vorgegeben
Vorgabe absoluter Werte durch die Anwendung neue Zustandswerte werden vorgegeben
Die Zustandswerte werden vom Organic Management selbst berechnet z.B. durch Linearisierung
rold, rnew: Alter und neuer Zustandsverktor einer Ressource
)*( JobJoboldnew dcMrr +−=
25
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.3 Organic Computing und Middleware
Es werden die bekannten Prinzipien von Auktionen benutzt:
Ausschreibung
Gebote
Zuschlag and den Meistbietenden
Ausführungspfade werden vom Koordinator (Empfänger der Mission) ausgeschrieben
Die Gebote werden von den Ressourcen in Abhängigkeit ihrer Eignung für die ausgeschriebenen Ausführungspfade und ihres aktuellen Zustandes abgegeben
Der Koordinator gibt den Zuschlag an den (oder die) Meistbietenden
Protokolle: z.B. ContractNet
Zuordnung der Ausführungspfade an Ressourcen über Auktionsmechansmen
26
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.3 Organic Computing und Middleware
Res.1
Res. 2
Res. 3
Res. n
Koord.
Phase 1: Ausschreibung einer Ausführungspfades (Aufgabenbeschreibung und Parameter)
A
A
A
A
27
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.3 Organic Computing und Middleware
Res. 1
Res. 2
Res. 3
Res. n
Koord.
Phase 2: Eingang der Gebote
B1
B3
B2Bn
28
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.3 Organic Computing und Middleware
Res. 1
Res. 2
Res. 3
Res. n
Koord.
Phase 3: Zuschlag an eine (oder mehrere) Ressourcen (Kontrakt)
K
29
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.3 Organic Computing und Middleware
Echtzeitaspekte:
Vorgabe eines Zeitlimits für die Auktion
Angebote nach Verstreichen des Zeitlimits werden ignoriert
=> obere Zeitschranke für die Zuteilung kann angegeben werden
=> möglicherweise suboptimale Lösung(wie bei Baum-Variante)
30
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
Body / Emotions
Sinus Node AtrioventricularNode
MyocardialCell
ParasympatheticNervous System
SympatheticNervous System
Low
Powe
r –Fa
il Saf
e –Re
al Ti
me
Environment / TaskMod. 1 Mod. 2
Learning/Adaptation↓
Algo-rithm↓
←
ControlLoop
OrganicManager
ControlLoop
Environment / Task
Brain
Lev
elOr
gan
Leve
lCe
ll Lev
el PC
Processing Cells
PC PC
PCPCPC
PC
6.3 Organic Computing und Middleware
6.3.2 DodOrg - Digital On Demand Computing Organismvon der Biologie zu einem Organic Computing System
31
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.3 Organic Computing und Middleware
Middleware
Mon
itorin
g
Pow
er M
anag
emen
t
Tasks
PZ PZ PZ PZ PZ PZ PZ
PZ PZ PZ PZ PZ PZ PZ
PZ PZ PZ PZ PZ PZ PZ
PZ PZ PZ PZ PZ PZ PZ
PZ PZ PZ PZ PZ PZ PZ
PZ PZ PZ PZ PZ PZ PZ
PZ PZ PZ PZ PZ PZ PZ
Virtuelle Organe
Anwendung DodOrg-Komponenten
•Anwendung
•Middleware
•Monitoring
•Power Management
•Prozessorzellen
32
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.3 Organic Computing und Middleware
• Die Middleware von DodOrg nutzt ein künstliches Hormonsystem zur Zuordnung von Task an Prozessorzellen
• Ausbildung „virtueller Organe“
• Hormonbasierte Regelschleifen wirken als Mechanismus zur Selbst-Konfiguration, Selbst-Optimierung und Selbst-Heilung
33
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
6.4.1 Natürliches HormonsystemAuch „endokrine System“ genannt:
System zur Steuerung und Regelung vielfältiger Körperfunktionen,
z.B. Verdauung, Wachstum, Fortpflanzung
Grundkonzept: chemische Botenstoffe (Hormone) werden von endokrinem Gewebe (z.B. Drüsen) produziert und wirken in der Nachbarschaft oder werden vom Blutkreislauf im ganzen Körper verteilt
Die Wirkung erfolgt entweder über entsprechende Rezeptoren an der Zellmembran oder über das Eindringen des Hormons in die Zelle
Die Reaktion einer Zelle auf ein Hormon hängt allein von dieser Zelle ab
34
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
Zwei Wirkmechanismen:
a. Direkte Wirkung von Hormonen auf eine Zelle ohne weitere Rück- oder Wechselwirkung (Steuerung)
b. Verknüpfung und Wechselwirkung mehrere Hormongruppen untereinander, z.B. um eine negative Rückkopplung zu erreichen (Regelung)
Endokrines Gewebe
Zelle Zelle Zelle Zelle Zelle
Endokrines Gewebe+
+
+ +
+-
- - -
-
direkte WirkungWechselwirkung
indirekte Wechselwirkung
35
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
Eigenschaften:
• Flexible Struktur
• Dezentralisiert
• Zellen reagieren nach lokalen Regeln
• Globales Verhalten ergibt sich als Summe des lokalen Verhaltens
• Geschlossene Rückführungsschleifen
• Selbstorganisierend (keine zentrale Steuerinstanz)
• Robust und fehlertolerant
=> Vorbild für ein technisches System
36
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
6.4.2 Künstliches HormonsystemNachbildung der Hormone durch kurze Botschaften (künstliche Hormone)
Künstliche Hormone werden lokal in der Nachbarschaft (lokaler Multicast) oder im gesamten System (Broadcast) verteilt
Lokale Reaktion der Komponenten (künstliche Zellen) auf die künstlichen Hormone
Die Reaktion der künstlichen Zelle auf ein künstliches Hormon hängt allein von der künstlichen Zelle ab
Gegenspieler bei den künstlichen Hormonen erlauben geschlossene Rückführungen
37
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
Anwendung: Taskzuordnung in einem verteilten System
Künstliche Zellen: Rechenknoten (z.B. in einem Sensor-/Aktor-Netzwerk)
Künstliche Hormone:
Eignungswerte E: Geben an, wie gut ein Knoten für eine Aufgabe geeignet ist
Suppressoren S: Hemmen die Ausführung einer Aufgabe auf einem Knoten. Supressoren werden vom Eignungswert subtrahiert.
Acceleratoren A: Begünstigen die Ausführung einer Aufgabe auf einem Knoten. Acceleratoren werden zum Eignungswert addiert 38
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
Für i, γ empfangene
Suppressoren Siγ
Für i,γ empfangene
Acceleratoren Aiγ Lokaler
Eignungswert Eiγ
Σ -
+ +
Von i, γ gesendeter
modifizierten Eignungswert
Emiγ
Für i, γ empfangene
Eignungswerte Emiγ
a > b ?
Übernehme Task Ti auf Kγ
Von i, γ gesendete
Suppressoren Siγ
Von i, γ gesendete
Acceleratoren Aiγ
Task Ti auf Kγ
a
b
Notation: Hiγ Hormon für Task Ti auf Knoten Kγ
Hiγ: Hormon von Task Ti auf Knoten Kγ, lateinische Buchstaben stehen für Task-Indizes, griechische Buchstaben für Knoten-Indizes
Prinzip der geschlossenen Rückführung, Gegenspieler
39
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
6.4.3 Künstlichen Hormone
Eignungswerte:
Lokaler Eignungswert Eiγ ursprüngliche Eignung von Kγ für Task Ti=> Taskverteilung nach den Fähigkeiten der
Knoten
Modifizierter Eignungswert wird durch Addition bzw. Subtraktion der für Task Ti auf Kγ empfangenen Acceleratoren und Suppressoren vom lokalen Eignungswert berechnet. Wird an Task Ti auf allen Knoten gesendet.
iΩiEm γ
40
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
Suppressoren:
Übernahme-Suppressor wird an Task Ti auf allen Knoten ausgesandt, wenn Kγ Task Ti übernommen hat=> bestimmt somit, wie oft Task Ti im System
übernommen wird
Last-Suppressor wird nur lokal an den Kγ gesendet, welcher Task Ti übernommen hat. Wirkt dort auf alle Tasks => bestimmt somit, wieviele Tasks ein Knoten
übernehmen kann.
Monitor-Suppressor wird vom lokalen Monitoring lokal an einen Knoten gesendet und wirkt dort auf alle Tasks=> kennzeichnet den allgemeine Zustand eines
Knoten bei der Taskvergabe.
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
iΩiSü γ
γγMiSl
γγ
MMSm
41
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
Acceleratoren:
Organ-Accelerator wird an alle zu Task Ti verwandten Tasks auf benachbarten Knoten ausgesandt, wenn Kγ die Task Ti übernommen hat=> Ansiedlung verwandter Tasks in der Nähe,
Organbildung
Angebots-Accelerator begünstigt das Verbleiben einer Task auf dem bisherigen Knoten, wenn die Task im Zuge der Selbstoptimierung neu angeboten wird. Wird nur lokal für Task Ti gesendet=> kennzeichnet die Kosten einer Taskmigration.
Monitor-Acclerator wird vom lokalen Monitoring lokal an einen Knoten gesendet und wirkt dort auf alle Tasks=> Gegenspieler zum Monitor-Suppressor
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
γγ
MMAm
γγiiAa
γ
γΦV
iiAo
42
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
Eigenschaften dieses Verfahrens
selbst-organisierendEs existiert keinerlei äußere Organisationsinstanz, welche in die Aufgabenverteilung eingreift. Diese erfolgt einzig aus der Interaktion der einzelnen Knoten.
selbst-konfigurierendDas Verfahren bestimmt selbsttätig eine Anfangsverteilung, welche die Fähigkeiten (z.B. Rechenkapaziät, Speicher, ...) sowie den Zustand (z.B. Betriebstemperatur, Energievorrat, ...) der heterogenen Knoten berücksichtigt.
selbst-optimierendDie Verteilung passt sich im Betriebs selbstständig an sich ändernde Bedingungen und Zustände der Knoten (z.B. schwindende Energie, steigende Temperatur) an.
selbst-heilendDurch das Fehlern von zentralen Instanzen sowie die Fähigkeit zur Selbst-Optimierung gleicht das Verfahren automatisch die Auswirkungen von ausgefallenen Aufgaben bzw. Knoten durch Umverteilung an.
43
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
Live-Demo
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
44
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
Sende Hormone
(S) Entscheide
(E) tSE
tES
3 Fälle:
Alle Eignungswerte konstant => eingeschwungener, stabiler Zustand
Der Eignungswert eines Knotens sinkt => Übernahme der Aufgabe, wenn der gesunkene Eignungswert dafür ausreicht, alle anderen Knoten kennen den höheren oder gesunkenen Wert
Der Eignungswert eines Knotens steigt => Übernahme der Aufgabe, wenn der gestiegene Eignungswert dafür ausreicht ist kritisch, da eventuell noch nicht alle Knoten diesen gestiegenen Wert kennen
6.4.4 Dynamik des HormonsystemsHormonzyklus:
45
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
=> Übernahme der Aufgabe nur, wenn der gestiegene Eignungswert sicher an alle Knoten kommuniziert ist bzw. ein Suppressor für diese Aufgabe von einem anderen Knoten empfangen wurde
tK tK
tES
tSE Kγ
Kδ
. . .
. . .
. . .
. . .
tK : Kommunikationszeit Kδ übernimmt Task Ti eventuell auf Basis von
iΩineu Em γ iΩ
iSü δ
iΩialt Em γ
S E
S E
Bedingung hierfür: tSE ≥ tES + 2 tKKriterium für sichere Entscheidung im Hormonzyklus
46
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
Jeder Knoten prüft die Übernahme einer Aufgabe pro Zyklus
Anderenfalls wären die Organ-Accleratoren wirkungslos
=> Präzisierter Hormonzyklus
Sende Hormone für
alle für Kγ relevanten
Tasks Tj ∈ Mγ
Warte (tSE)
tES (= 0)
Entscheide über Task Ti
i:= i+1
6.4.4.1 Zeitverhalten der Selbstkonfiguration
47
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
Bei m Aufgaben haben alle Knoten nach m Zyklen alle Aufgaben überprüft
Durch den dynamischen Einfluss von Acceleratoren und Suppressoren ist es möglich, dass jedoch noch nicht alle Aufgaben übernommen wurden, Beispiele:
Kγ prüft die Übernahme von Task Ti, Sieger ist Kε Kδ prüft die Übernahme von Task Ti, Sieger ist Kε Kε prüft die Übernahme von Task Ti, Sieger ist Kδ
Kδ erhöht seinen Eignungswert für Ti auf Grund eines empfangenen Accelerators
t
Kγ prüft die Übernahme von Task Ti, Sieger ist Kε Kδ prüft die Übernahme von Task Ti, Sieger ist Kε Kε prüft die Übernahme von Task Ti, Sieger ist Kδ
Kε erniedrigt seinen Eignungswert für Ti auf Grund eines empfangenen Supressors
t
48
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
Die Gesamtzahl der Zyklen ist jedoch trotzdem begrenzt, da Acceleratoren und Suppressoren nur bei Übernahme einer Aufgabe ausgestossen werden
=> in jedem Durchlauf von m Zyklen wird mindestens 1 Aufgabe übernommen
=> Zeitverhalten im schlimmsten Fall: m2 Zyklen bis zur Übernahme aller Aufgaben
49
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
1. Verfeinerung des Hormonzyklus:
Berücksichtigung von Acceleratoren, welche den Eignungswert für eine Task erhöhen, in der Prüfreihenfolge des Hormonzyklus (analog Beispiel 1, Folie 15)
Erhöht sich ein gesendeter Wert einer Task über alle bisher empfangenen Werte, so wird die normale Prüfreihenfolge verlassen und diese Task als nächste geprüft
Sende Hormone für
alle für Kγ relevanten
Tasks Tj ∈ Mγ
Warte (tSE)
tES = 0
Entscheide über Task Ti
i:= i+1
Erhöhter Eignungswert für Task Tk gesendet,
Tk Siegerkandidat? Entscheide
über Task Tk
nein
ja
Verbesserung des Zeitverhaltens
50
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten SystemenZeitverhalten des verfeinerten Zyklus, schlimmster Fall:
Eignungswert von Task Ti erhöht sich in Zyklus m durch Accelerator
Dieser Accelerator wurde durch die Übernahme einer von m-1 anderen Tasks verursacht
=> Task Ti wird im nächsten Zyklus (m+1) erneut geprüft
Eignungswert von Task Ti erhöht sich in Zyklus m+1 durch Accelerator
Dieser Accelerator wurde durch die Übernahme einer von m-2 anderenTasks verursacht
=> Task Ti wird im nächsten Zyklus (m+2) erneut geprüft
Eignungswert von Task Ti erhöht sich in Zyklus m+2 durch Accelerator
Dieser Accelerator wurde durch die Übernahme einer von m-3 anderenTasks verursacht
… 51
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
Zyklus 1: T1 Tm-2 Tm-1 Tm... ...... ...
Zyklus m: T1 Tm-2 Tm-1 Tm ⇐ Tm genommen, Accelerator gesendetZyklus m+1: T1 Tm-2 Tm-1 ⇐ Tm-1 genommen, Accelerator gesendetZyklus m+2: T1 Tm-2 ⇐ Tm-2 genommen, Accelerator gesendet
... ...
... ...Zyklus 2m-1: T1 ⇐ T1 genommen, Accelerator gesendet
⇒ Worst-Case Zeitverhalten = 2m-1 Zyklen
52
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen2. Verfeinerung des Hormonzyklus:
Berücksichtigung von Suppressoren, welche den Eignungswert für eine Task erniedrigen, in der Prüfreihenfolge des Hormonzyklus (analog Beispiel 2, Folie 48)
Erniedrigt sich ein empfangener Wert einer Task unter alle bisher empfangenen sowie den eigenen Wert, so wird die normale Prüfreihenfolge verlassen und diese Task als nächste geprüft
Sende Hormone für
alle für Kγ relevanten
Tasks Tj ∈ Mγ
Warte (tSE)
tES = 0
Entscheide über Task Ti
i:= i+1
Erniedrigter Eignungswert für
Task Tk empfangen, Tk
Siegerkandidat? Entscheide über Task Tk
nein
ja
53
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
Aus analoger Überlegung ergibt sich das gleiche Zeitverhalten wie für Verfeinerung 1:
⇒ Mit Verfeinerung 1 und 2:
Generelles Zeitverhalten des Hormonzyklus
2m-1 Zyklen bis zur Übernahme aller Tasks
Anmerkung: für die hier betrachtete Anwendung ist Verfeinerung 2 unnötig, da Suppressoren hier niemals auf andere Tasks wirken sondernnur für Tasks ausgeschüttet werden, die bereits übernommen sind.
54
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
Weitere Präzisierungen für Verfeinerung 1:
Bisherige Annahme: alle Tasks sind mit allen verwandt, d.h. eine Task kann von m-1 anderen Tasks Acceleratoren empfangen
In der Regel ist eine Task Ti jedoch nur mit vi anderen Tasks verwandt,vi ≤ m-1
⇒ Sie kann nur von vi anderen Tasks Acceleratoren empfangen
⇒ Die Taskübernahme ist nach
m + vmax mit
Zyklen beendet
)(: ii
vmaxvMTmax ∈
=
55
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
Weitere Präzisierungen für Verfeinerung 1:
Bisherige Annahme: alle Knoten bewerben sich um alle Tasks
Bewirbt sich ein Knoten Kγ jedoch nur um mγ Tasks, mγ ≤ m
⇒ Die Taskübernahme ist nach
mmax + vmax mit
Zyklen beendet
)( γγ
mmaxmΩPEmax ∈
=
56
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
Beispiel:
10 Tasks T1 ... T10 ⇒ m = 10Verwandt: T1 ... T4,
T5 ... T10 ⇒ vmax = max(v1, ..., v10) = max(4,4,4,4,6,6,6,6,6,6) = 6
Es ergeben sich also:
mit 2m - 1 = 20-1 = 19 Zyklen als Obergrenzemit m + vmax = 10 + 6 = 16 Zyklen als Obergrenze
Bewerben sich weiterhin nur K1, K2 um T1 ... T5 und K3, K4 um T6 ... T10⇒ mmax = max(m1, ..., m4) = max(5,5,5,5,) = 5
so ergeben sich:
mit mmax + vmax = 5 + 6 = 11 Zyklen als Obergrenze57
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
Anzahl Tasks
Anz
ahl Z
ykle
nSimulationsergebnisse
58
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
Eine Selbstoptimierung findet nur statt, wenn ein Knoten eines Task zur Ver-schiebung anbietet => der Zeitpunkt der Optimierung wird vom Knoten gewählt
Weiterhin betreibt der alte Knoten die Task bis sie auf dem potenziellen neuen Knoten ausgeführt wird => maximale Ausfallzeit = Zeit für Zustandstransfer
Schlimmster Fall für die Dauer der Selbstoptimierung: alle Tasks werden gleichzeitig angeboten => gleiches Zeitverhalten wie bei der Selbstkonfiguration
mmax + vmax Zyklen
(wird hingegen z.B. nur eine Task angeboten, so wird sie gemäß Verfeinerung 1 bereits im nächsten Zyklus übernommen)
6.4.4.2 Zeitverhalten der Selbstoptimierung
59
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
Annahme: es bleiben in der Ausfallsituation noch genügend Knoten übrig, sodass alle Aufgaben übernommen werden können
⇒ im wesentlichen gleiches Zeitverhalten wie bei der Selbstkonfiguration oder Selbstoptimierung, hinzu kommt lediglich die Zeit um den Ausfall zu erkennen
Dies geschieht durch Überschreitung der Verfallszeit eines künstlichen Hormons (a Zyklen)
⇒ Selbstheilung beendet spätestens nachmmax + vmax + a Zyklen
Fällt nur ein Knoten aus, so müssen nur die dort ausgeführten eγ Task neu vergeben werden. Es ergeben sich somit hierfür
eγ + + a Zyklen)(vmax iET λi∈
6.4.4.3 Zeitverhalten der Selbstheilung
60
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
Ein Knoten Kγ sendet pro Zyklus:
Broadcast an alle anderen Knoten: 1 modifizierter Eignungswert pro beworbener Task Tj
1 Übernahme-Supressor pro übernommener Task Ti
Multicast an Nachbarn: 1 Organ-Accelerator pro verwandter Task einer über-nommenen Task Ti
Alle anderen Hormone werden nur lokal versandt bzw. genutzt
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
jΩjEm γ
iΩiSü γ
γ
γΦV
iiAo
6.4.5 Datenaufkommen der Hormonausschüttung
61
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
Datenstruktur eines künstlichen Hormons:
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
Hormontyp, Knoten-Id, Task-Id, Wert
Eignungswert, Suppressor, Accelerator
Absenderinformation
Eignungswerte, Suppressoren und Acceleratoren benötigen neben dem eigentlichen Wert noch eine Absenderinformation, um alte Hormonwerte durch neue, aktuellere eines Absenders ersetzen zu können.
62
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
Broadcast: Dbγ = De · kγ + Ds · eγ
mit Dbγ : Broadcast-Datenmenge von KγDe: Datenmenge zur Übertragung eines EignungswertesDs: Datenmenge zur Übertragung eines Suppressorskγ: Anzahl der Tasks, um die sich Kγ beworbenen hat und
welche noch nicht vollständig im gesamten System übernommen wurden
eγ: Anzahl aller auf dem Prozessorelement Kγ ausgeführten Tasks
Multicast:
mit Dmγ: Multicast-DatenmengeDa: Datenmenge zur Übertragung eines Acceleratorsvi: Anzahl aller zu einer Task Ti verwandten Tasks.
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
∑∈
⋅=γ
γ
ETi
i
vDaDm
63
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
=> Datenaufkommen eines beliebigen Knotens zu Beginn und im eingeschwungenen Zustand:
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
eγ = 0 zu Anfang
kγ = 0 am Ende
γγ kDeDbAnfang ⋅=
0DmAnfang =γ
γγ eDsDbEnde ⋅=
∑∈
⋅=γ
γET
iEndei
vDaDm
64
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
Das gesamte Hormon-Datenaufkommen an einem beliebigen Knoten Kγ ergibt sich aus der Summe der Broadcasts aller Prozessorelemente sowie der Summe der Multicasts seiner Nachbarn:
mit Dγ: Gesamte Datenmenge an Kγ
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
∑ ∑∈ ∈
+=ΩK ΦK
DmDbDδ γδ
δδγ
65
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
=> Gesamtes Datenaufkommen an einem beliebigen Knotens zu Beginn und im eingeschwungenen Zustand
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
∑ ∑∈ ∈
+=ΩK ΦK
AnfangAnfangAnfang DmDbDδ γδ
δδγ
∑∈
⋅=ΩK
kDeδ
δ
∑ ∑∈ ∈
+=ΩK ΦK
EndeEndeEnde DmDbDδ γδ
δ δγ
∑ ∑ ∑∈ ∈ ∈
⋅+⋅=ΩK ΦK ET
ii
vDaeDsδ γδ δ
δ
66
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
Bildung eines oberen Grenzwertes durch Ersetzen der Summen der individuellen Datenaufkommen durch Produkte der maximalen Datenaufkommen mit der Anzahl der verursachenden Elemente:
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
)()()( δδδδ
δδ
ϕω DmmaxmaxDbmaxD AnfangΩKΩKAnfangΩKmaxAnfang ∈∈∈⋅+⋅=
maxkDe ⋅⋅= ω
)()()( δδδδ
δδ
ϕω DmmaxmaxDbmaxD EndeΩKΩKEndeΩKmaxEnde ∈∈∈⋅+⋅=
maxmaxmaxmax veDaeDs ⋅⋅⋅+⋅⋅= ϕω
)(: δδ
kmaxkΩKmax ∈
=
)(: δδ
emaxeΩKmax ∈
=
)(: ii
vmaxvMTmax ∈
=
)(: δδ
ϕϕΩKmax max
∈=
mit: Maximum aller kδMaximum aller eδgrößte Anzahl miteinander verwandten Tasks größte
Anzahl benachbarter Knoten67
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
Ein Beispiel:
Eignungswerte, 2 Bit Hormontyp (Eignungswert/Suppressor/Accelerator)Suppressoren 8 Bit Knoten-Id (max. 256 Knoten)
7 Bit Task-Id (max. 128 Tasks)7 Bit Wert (128 Hormonabstufungen)
∑ 24 Bit
⇒ De = Ds = 24 Bit
Acceleratoren 2 Bit Hormontyp8 Bit Knoten-Id7 Bit Task-Id7 Bit Verwandte Task-Id7 Bit Wert
∑ 17 + vi · 14 Bit
⇒ Da = 17 + vmax · 14 Bit (schlimmster Fall: vi = vmax)
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
vi-mal wiederholt
68
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
Werte für Knoten, Tasks, …
ω = 64 (Anzahl PEs)
ϕmax = 9 (Anzahl zu einem Knoten benachbarte Knoten)
kmax = 32 (max. Anzahl von einem Knoten beworbener Tasks)
emax = 2 (max. Anzahl von einem Knoten übernommene Tasks)
vmax = 8 (max. Anzahl zu einer Task verwandte Tasks)
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
69
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
Mit diesen Werten ergibt sich:
Bei einer angenommenen Zykluszeit von 100msec (tSE + tES) ergibt sich daher ein Hormon-Datendurchsatz von:
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
Bytes 6144Bit 49152Bit 322464 ==⋅⋅=maxAnfang D
Bytes 25,674Bit 5394Bit )14817(2922464 ==⋅+⋅⋅+⋅⋅=maxEnde D
kBytes/sec 60Bytes/sec 614410 =⋅=maxAnfang DS
kBytes/sec 58,6Bytes/sec 25,67410 =⋅=maxEnde DS
70
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
Eigenschaften des künstlichen Hormonsystems:
+ algorithmisch einfaches Verfahren+ benötigt nur wenig Rechenleistung+ vollständig dezentrale Lösung+ rein lokale Entscheidungsverfahren+ selbstkonfigurierend, selbstoptimierend, selbstheilend+ definiertes Zeitverhalten
- Datenaufkommen wächst mit der Anzahl Knoten- Broadcast wird benötigt (Multicast zu Nachbarn eher unkritisch)- Zykluszeit hängt von der maximalen Kommunikationszeit im Netz ab
Mögliche Abhilfe bei größeren Netzen: Clusterbildung, Hierarchien
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
71
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
Drei Teilbereiche der Güte:
• Belastung der einzelnen Prozessorelemente• Berücksichtigung der Eignung eines Prozessorelements für eine Task• Kommunikationsdistanzen zwischen verwandten Tasks
⇒ Gütemaß für eine Task Ti auf einem Knoten Kγ
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
CDEVSH
CDEVSH
wwwCDwEVwSHwQU iii
i++
⋅+⋅+⋅=
γγγγ
6.4.6 Güte der Taskzuordnung
72
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
QUiγ Güte (Quality) von Ti auf Kγ, Wertebereich [0 ... 1]
SHiγ Anteil (Share) von Kγ, der Ti zur Verfügung steht,
Wertebereich [0 ... 1]
EViγ Eignung (EagerValue) von Kγ, für Ti im Verhältnis zur
bestmöglichen Eignung eines Knoten für Ti, Wertebereich
[0 ... 1]
CDiγ Kommunikationsdistanzmaß (Communication Distance)
von Ti auf Kγ zu den verwandten Tasks,
Wertebereich [0 ... 1]
wSH Gewicht (Weight) von SHiγ an der Güte
wEV Gewicht (Weight) von EViγ an der Güte
wCD Gewicht (Weight) von CDiγ an der Güte
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
73
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
Gütemaß für einen Knoten Kγ
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
γ
γ
γγ
e
QUQU ET
ii
∑∈=
QUγ Güte von Kγ, QUiγ Güte von Ti auf KγEγ Menge aller auf Kγ ausgeführten Taskseγ Anzahl aller auf Kγ ausgeführten Tasks
74
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
Gütemaß für das gesamte System
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
QU Güte der gesamten Taskzuordnung QUγ Güte von Kγ, QUiγ Güte von Ti auf KγΩ Menge aller Knoten im Systemm Anzahl aller Tasks im System
m
QUe
m
QUQU KK ET
ii
∑∑ ∑Ω∈Ω∈ ∈
⋅== γγ γ
γγγ
75
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
Berechnung des Anteils SHiγ
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
≥=
∑∑ ∈∈
sonst 1
1 wenn 1γ
γ
γγ
γ ETi
ETi
i i
i
LDLDSH
≤
=sonst 1
wenn γγγ
γ
γγ
γEiSl
ESl
LDMi
i
Mi
i
LDiγ : Auslastung von Knoten Kγ durch Task Ti, Eγ : Anzahl auf Kγ ausgeführter Tasks
: Last-Suppressor für Ti auf Kγ, Eiγ lokaler Eignungswert von Kγ für Tiγ
γMiSl
76
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
Berechnung des Anteils EViγ
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
Ω∈
=
δ
δ
γγ
Ki
ii
EmaxEEV
)(
Quotient des lokalen Eignungswertes Eiγ einer Task Ti auf Knoten Kγ zu dem bestmöglichen Eignungswert dieser Task auf einem Knoten
77
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
Berechnung des Anteils CDiγ
Berechnung über die Kommunikationsdistanz:
KDiγj = 1 + Anzahl Knoten zwischen Ti auf Kγ und Tj auf dem zugehörigen Knoten
Gewichtete Kommunikationsdistanz:
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
≥⋅⋅
=sonst 1
1 wenn , ijjiijjiji
VGKDVGKDGKD
γγγ
VGij Verwandtschaftsgrad von Ti und Tj, Wertebereich [0 .. 1]
(je enger verwandt zwei Task sind, desto öfter kommunizieren sie miteinander)
78
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
Berechnung des Anteils CDiγ
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
∑∈
=
ij VTji
ii
GKDvCD
γγ
vi Anzahl der zu Task Ti verwandten TasksVi Menge zu Task Ti verwandten Tasks GKDiγj Gewichtete Kommunikationsdistanz zwischen Ti auf Kγ und Tj
79
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
Bestimmung einer Obergrenze für das Gütemaß:
Wie weit ist die Taskzuteilung mittels künstlicher Hormone von einer optimalen
Zuteilungsstrategie entfernt?
Einfachste Obergrenze: QU ≤ 1
Müssen mehr Tasks zugeteilt werden als Prozessorkapazität verfügbar ist, so
kann auch eine optimale Taskzuteilungsstrategie den Wert QU = 1 nicht mehr
erreichen
Dies geschieht genau dann, wenn die Summe der Belastung durch alle Tasks
größer wird als die Anzahl der Knoten:
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
ωγγ
γ >∑∑∈Ω∈ ET
iK i
LD
80
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
Beispiel:
14 Tasks => m = 14
Jede Task benötige 0,5 Knoten => LDiγ = 0,5
5 Knoten sind verfügbar => ω = 5
=>
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
ωγγ
γ =>=∑∑∈Ω∈
57ET
iK i
LD
81
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
Möglichst gleiche Verteilung der Last => minimale Prozessorbelastung
Bei Gleichverteilung ergibt sich eine durchschnittliche Prozessorlast von
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
ωγγ
γ∑∑∈Ω∈= ET
iK
ai
LDL
57
==∑∑∈Ω∈
ωγγ
γ
ETi
Ka
i
LDL
Beispiel:
82
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
Somit ergibt sich der Anteil eines Knotens, welcher einer Task zur Verfügung steht, zu:
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
≥
=sonst 1
1 wenn 1a
aaL
LSH
Beispiel:
75
=aSH
83
Goethe-Universität Frankfurt am Main – Lehrstuhl für Eingebettete Systeme - Prof. Dr. U. Brinkschulte
Setzen wir weiterhin die anderen Güteanteile EV und CD auf ihren Maximalwert von 1, so ergibt sich die Obergrenze der Gesamtgüte zu:
6.4 Ein künstliches Hormonssystem zur Taskzuordnung in verteilten eingebetteten Systemen
CDEVSH
CDEVSH
CDEVSH
CDEVSH
wwwwwSHw
mwww
CDwEVwSHwmQU
a
a
max
++++⋅
=
++⋅+⋅+⋅
=
)(
Beispiel:
905,02119
111
11751
==++
++⋅=
++++⋅
=CDEVSH
CDEVSH
wwwwwSHwQU a
max
84
Recommended