Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 1 - Prof. Dr. Uwe Brinkschulte
Natürliches HormonsystemAuch „endokrines 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
verteiltDie Wirkung erfolgt entweder über entsprechende Rezeptoren an der Zellmembran oder über das Eindringen des Hormons in die ZelleDie Reaktion einer Zelle auf ein Hormon hängt allein von dieser Zelle ab
3.7 Künstliche Hormonsysteme
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 2 - Prof. Dr. Uwe Brinkschulte
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
3.7 Künstliche Hormonsysteme
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 3 - Prof. Dr. Uwe Brinkschulte
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
3.7 Künstliche Hormonsysteme
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 4 - Prof. Dr. Uwe Brinkschulte
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
3.7 Künstliche Hormonsysteme
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 5 - Prof. Dr. Uwe Brinkschulte
Middleware
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
Anwendung• Zuordnung von Tasks an Prozessorzellen in verteilten eingebetteten Systemen• Ausbildung virtueller Organe• Hormonbasierte Regelschleifen als Mechanismus zur Selbst- Konfiguration, Selbst- Optimierung und Selbst- Heilung
3.7.1 Ein künstliche Hormon-system zur Taskzuordnung
Ref: U. Brinkschulte, M. Pacher, A. von Renteln, An Artificial Hormone System for Self-Organizing Real- Time Task Allocation in Organic Middleware, In: Organic Computing, Springer, 2008
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 6 - Prof. Dr. Uwe Brinkschulte
Künstliche Zellen: Rechenknoten (im verteilten System)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
3.7.1 Ein künstliche Hormon-system zur Taskzuordnung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 7 - Prof. Dr. Uwe Brinkschulte
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
3.7.1 Ein künstliche Hormon-system zur Taskzuordnung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 8 - Prof. Dr. Uwe Brinkschulte
Präzisierung der 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
3.7.1 Ein künstliche Hormon-system zur Taskzuordnung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 9 - Prof. Dr. Uwe 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.
iΩiSü
MiSl
MMSm
3.7.1 Ein künstliche Hormon-system zur Taskzuordnung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 10 - Prof. Dr. Uwe 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
MMAm
iiAa
ΦV
iiAo
3.7.1 Ein künstliche Hormon-system zur Taskzuordnung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 11 - Prof. Dr. Uwe Brinkschulte
Demo - Hormonsimulator
3.7.1 Ein künstliche Hormon-system zur Taskzuordnung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 12 - Prof. Dr. Uwe Brinkschulte
Autonomes Fahrzeug (AGV Autonomous Guided Vehicle)
Sensorik: LaserscannerTransponderempfängerBumper
Aktorik: Differentialantrieb
Ziel: Navigation in einer unbekannten Umgebung, Finden von Transpondern (nur Anwendungsbeispiel für das Hormonsystem, kein eigenständiges wissenschaftliches Ziel)
Orientierung
Notaus bei Kollision
3.7.2 Ein Anwendungsbeispiel
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 13 - Prof. Dr. Uwe Brinkschulte
Navigation mit Laserscanner und Transponder
Laser Corridor Task
Line Segment Task
Pilot Task
Transponder Localization Task
Drive Track Task
Drive Control Task
Laser ScannerTransponder Empfänger
3.7.2 Ein Anwendungsbeispiel
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 14 - Prof. Dr. Uwe Brinkschulte
State Transfer Task
State Transfer Task
Line Segment Task
Line Segment Task
Line Segment Task
Tasksstruktur:
Drive Control Task
Drive Track TaskTransponder Localization Task
Pilot Task
Laser Corridor Task
Line Segment Task
(n Instanzen)
State Transfer Task
(m Instanzen)
Organ-Beziehungen
3.7.2 Ein Anwendungsbeispiel
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 15 - Prof. Dr. Uwe Brinkschulte
Prozessor-Strukturen:
Prozessor(Festkomma)
Prozessor(Festkomma)
Prozessor(Festkomma)
Prozessor(Gleitkomma)
Prozessor(Gleitkomma)
Prozessor(Festkomma)
Prozessor(Gleitkomma)
Prozessor(Festkomma)
Prozessor(Festkomma)
Selbstkonfiguration: eigenständige Anpassung an die jeweilige Prozessorstruktur
Selbstoptimierung: Berücksichtigung von Eigenschaften, Temperaturen, …
Selbstheilung: eigenständige Kompensation von Ausfällen
Selbstorganisation: keine äußere Kontrollinstanz
3.7.2 Ein Anwendungsbeispiel
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 16 - Prof. Dr. Uwe Brinkschulte
Demo: AGV mit hormonbasierter Taskzuordnung
3.7.2 Ein Anwendungsbeispiel
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 17 - Prof. Dr. Uwe Brinkschulte
Weiteres Demo: hormonbasierte Lichtsteuerung im Auto
3.7.2 Ein Anwendungsbeispiel
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 18 - Prof. Dr. Uwe Brinkschulte
Sende Hormone
(S) Entscheide
(E) tSE
tES
Drei 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
3.7.3 Dynamik des Hormonzyklus
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 19 - Prof. Dr. Uwe Brinkschulte
=> Ü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 für sichere Entscheidung: tSE ≥ tES + 2 tK
3.7.3 Dynamik des Hormonzyklus
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 20 - Prof. Dr. Uwe Brinkschulte
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
3.7.4 Zeitverhalten der Selbstkonfiguration
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 21 - Prof. Dr. Uwe Brinkschulte
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
3.7.4 Zeitverhalten der Selbstkonfiguration
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 22 - Prof. Dr. Uwe Brinkschulte
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
3.7.4 Zeitverhalten der Selbstkonfiguration
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 23 - Prof. Dr. Uwe Brinkschulte
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 21)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
3.7.5 Verbesserung des Zeitverhaltens
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 24 - Prof. Dr. Uwe Brinkschulte
Zeitverhalten 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 anderen Tasks 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 anderen Tasks verursacht
…
3.7.5 Verbesserung des Zeitverhaltens
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 25 - Prof. Dr. Uwe Brinkschulte
Zyklus 1: T1 Tm-2 Tm-1 Tm
... ... ... ...Zyklus m: T1 Tm-2 Tm-1 Tm Tm genommen, Accelerator gesendet Zyklus m+1: T1 Tm-2 Tm-1 Tm-1 genommen, Accelerator gesendet Zyklus m+2: T1 Tm-2 Tm-2 genommen, Accelerator gesendet ... ... ... ...Zyklus 2m-1: T1 T1 genommen, Accelerator gesendet
Worst-Case Zeitverhalten = 2m-1 Zyklen
3.7.5 Verbesserung des Zeitverhaltens
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 26 - Prof. Dr. Uwe Brinkschulte
2. 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 21)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
3.7.5 Verbesserung des Zeitverhaltens
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 27 - Prof. Dr. Uwe Brinkschulte
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.
3.7.5 Verbesserung des Zeitverhaltens
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 28 - Prof. Dr. Uwe Brinkschulte
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 nachm + vmax mit
Zyklen beendet
)(: ii
vmaxvMTmax
3.7.5 Verbesserung des Zeitverhaltens
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 29 - Prof. Dr. Uwe Brinkschulte
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 nachmmax + vmax mit
Zyklen beendet
)(
mmaxmΩPEmax
3.7.5 Verbesserung des Zeitverhaltens
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 30 - Prof. Dr. Uwe Brinkschulte
Beispiel:
10 Tasks T1 ... T10 m = 10 Verwandt: 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 Obergrenze mit 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 Obergrenze
3.7.5 Verbesserung des Zeitverhaltens
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 31 - Prof. Dr. Uwe Brinkschulte
Anzahl Tasks
Anz
ahl Z
ykle
n
3.7.5 Verbesserung des Zeitverhaltens
Messergebnisse
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 32 - Prof. Dr. Uwe Brinkschulte
Eine Selbstoptimierung findet nur statt, wenn ein Knoten eines Task zur Verschiebung anbietet => der Zeitpunkt der Optimierung wird vom Knoten gewählt
Weiterhin betreibt der alte Knoten die Task bis sie auf dem potenziellen neuen Knoten zur Ausführung kommt => 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)
3.7.6 Zeitverhalten der Selbstoptimierung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 33 - Prof. Dr. Uwe Brinkschulte
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 nach
mmax + vmax + a Zyklen
Fällt nur ein Knoten aus, so müssen nur die dort ausgeführten e Tasks neu vergeben werden. Es ergeben sich somit hierfür
e + + a Zyklen )(vmax iET λi
3.7.7 Zeitverhalten der Selbstheilung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 34 - Prof. Dr. Uwe 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
jΩjEm
iΩiSü
ΦV
iiAo
3.7.8 Datenaufkommen derHormonausschüttung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 35 - Prof. Dr. Uwe Brinkschulte
Datenstruktur eines künstlichen Hormons:
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.
3.7.8 Datenaufkommen derHormonausschüttung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 36 - Prof. Dr. Uwe 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 Knoten K ausgeführten Tasks
Multicast:
mit Dm: Multicast-DatenmengeDa: Datenmenge zur Übertragung eines Acceleratorsvi: Anzahl aller zu einer Task Ti verwandten Tasks.
Datenaufkommen eines Knotens
ET
i
i
vDaDm
3.7.8 Datenaufkommen derHormonausschüttung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 37 - Prof. Dr. Uwe Brinkschulte
Broadcast: Db = De · k + Ds · e + Ds ·(m - e) = De · k + Ds · m (0-Hormone)
mit m : Anzahl der Tasks, um die sich K beworben hat
Multicast:
Zu berücksichtigen sind aber auch Hormone, die zu 0 geworden sind. Diese müssen zumindest 1 mal gesendet werden, danach werden sie durch die Alterung automatisch entfernt
=> ein Knoten sollte zu Beginn auch Hormone mit dem Wert 0 einmal senden, um den
0-Pegel zu garantieren
Unter Berücksichtigung dieser 0-Hormone ergibt sich zu Beginn ein Datenaufkommen von:
3.7.8 Datenaufkommen derHormonausschüttung
MT
i
EMT
i
ET
i
iii
vDavDavDaDm
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 38 - Prof. Dr. Uwe Brinkschulte
=> Datenaufkommen eines beliebigen Knotens zu Beginn und im eingeschwungenen Zustand:
k = m zu Anfang, 0-Hormone
k = 0 am Ende, keine 0-Hormone
3.7.8 Datenaufkommen derHormonausschüttung
mDsDeDbAnfang )(
MT
iAnfangi
vDaDm
eDsDbEnde
ET
iEndei
vDaDm
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 39 - Prof. Dr. Uwe Brinkschulte
Das gesamte Hormon-Datenaufkommen an einem beliebigen Knoten K ergibt sich aus der Summe der Broadcasts aller Knoten sowie der Summe der Multicasts seiner Nachbarn:
mit D: Gesamte Datenmenge an K
Gesamtes Hormon-Datenaufkommen
ΩK ΦK
DmDbD
3.7.8 Datenaufkommen derHormonausschüttung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 40 - Prof. Dr. Uwe Brinkschulte
=> Gesamtes Datenaufkommen an einem beliebigen Knotens zu Beginn und im eingeschwungenen Zustand
ΩK ΦK
EndeEndeEnde DmDbD
3.7.8 Datenaufkommen derHormonausschüttung
ΩK ΦK
AnfangAnfangAnfang DmDbD
ΦK MT
iΩK i
vDamDsDe )(
ΩK ΦK ET
ii
vDaeDs
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 41 - Prof. Dr. Uwe Brinkschulte
Bildung eines oberen Grenzwertes durch Ersetzen der Summen der individuellen Datenaufkommen durch Produkte der maximalen Datenaufkommen mit der Anzahl der verursachenden Elemente:
)()()(
DmmaxmaxDbmaxD AnfangΩKΩKAnfangΩKmaxAnfang
)()()(
DmmaxmaxDbmaxD EndeΩKΩKEndeΩKmaxEnde
maxmaxmaxmax veDaeDs
)(:
emaxeΩKmax
)(: ii
vmaxvMTmax
)(:
ΩKmax max
mit: Maximum aller m
Maximum aller e
größte Anzahl miteinander verwandten Tasks
größte Anzahl benachbarter Knoten
3.7.8 Datenaufkommen derHormonausschüttung
maxmaxmaxmax vmDamDsDe )(
)(:
mmaxmΩPEmax
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 42 - Prof. Dr. Uwe 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)
vi-mal wiederholt
3.7.8 Datenaufkommen derHormonausschüttung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 43 - Prof. Dr. Uwe Brinkschulte
Beispiel-Werte für Knoten, Tasks, …
= 64 (Anzahl Knoten)
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)
3.7.8 Datenaufkommen derHormonausschüttung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 44 - Prof. Dr. Uwe Brinkschulte
Mit diesen Werten ergibt sich:
Bei einer angenommenen Zykluszeit von 100msec (tSE + tES) ergibt sich daher ein Hormon-Datendurchsatz von:
Bytes 25,674Bit 5394Bit )14817(2922464 maxEnde D
kBytes/sec 58,6Bytes/sec 25,67410 maxEnde DS
3.7.8 Datenaufkommen derHormonausschüttung
Bytes 16932Bit 135456Bit )14817(32932)2424(64 maxAnfang D
kBytes/sec 32,169Bytes/sec 1693210 maxAnfang DS
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 45 - Prof. Dr. Uwe Brinkschulte
0
500
1000
1500
2000
2500
3000
0 5 10 15 20 25
Overall Hormone DataOverall Message Data
Messergebnisse aus dem AGV-Beispiel
3.7.8 Datenaufkommen derHormonausschüttung
Man sieht: wie theoretisch erwartet nimmt das Hormon-Datenaufkommen nach der Startphase ab. Dann überwiegt sehr schnell das Anwendungs-Datenaufkommen
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 46 - Prof. Dr. Uwe Brinkschulte
Schrittweises Vorgehen, zunächst starke Vereinfachungen, die dann Schritt für Schritt aufgehoben werden1. Nur Suppressoren und Eignungswerte, keine AcceleratorenAlle Suppressoren für Task T sollen zunächst den gleichen Wert sup, alle Eignungswerte den gleichen Wert ev besitzenDas künstliche Hormonsystem ordnet die Task zu, solange die Summe der Suppressoren schwächer als der Eignungswert ist, d.h. solange gilt: n * sup < ev mit n: Anzahl Zuordnungen von Task T
Die Anzahl Zuordungen einer Task T berechnet sich somit zu:
3.7.9 Stabilität des Hormonsystems
supevn
Ref: U. Brinkschulte, A. von Renteln, Analyzing the Behavior of an Artificial Hormone System for Task Allocation, ATC 2009, Brisbane, Australia
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 47 - Prof. Dr. Uwe Brinkschulte
Wir lassen nun verschiedene Eignungswerte im Bereich evmin …
evmax zu, die Suppressoren mögen weiterhin alle den gleichen Wert sup besitzen.
Solange der größte Eignungswert evmax nicht kompensiert ist, wird das Hormonsystem die Task T zuordnen!
Beispiel :1. Zuordnung 2. Zuordnung 3. Zuordnung
ev1 = 5, sup = 2 3 1 -1
ev2 = 3, sup = 2 1 -1 -3
ev3 = 2, sup = 2 0 -2 -4
3.7.9 Stabilität des Hormonsystems
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 48 - Prof. Dr. Uwe Brinkschulte
Das Hormonsystem ordnet also die Task zu, solange die Summe der Suppressoren schwächer als der größte Eignungswert evmax ist, d.h solange gilt:
n * sup < evmax
Die Anzahl Zuordungen einer Task T berechnet sich somit zu:
3.7.9 Stabilität des Hormonsystems
supevn max
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 49 - Prof. Dr. Uwe Brinkschulte
Wir lassen nun verschiedene Eignungswerte im Bereich evmin … evmax und verschiedene Suppressoren im Bereich supmin … supmax zu.Wir können nun eine Ober- und eine Untergrenze der Task-Zuordnungen ermitteln.
Obergrenze: Die Task wird auf dem Knoten mit dem schwächsten Suppressor zugeordnet. Die Zuordnung erfolgt, solange gilt:
nmax * supmin < evmax
Untergrenze: Die Task wird auf dem Knoten mit dem stärksten Suppressor zugeordnet. Die Zuordnung erfolgt, solange gilt:
nmin * supmax < evmin
3.7.9 Stabilität des Hormonsystems
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 50 - Prof. Dr. Uwe Brinkschulte
Damit lässt sich für die Anzahl Zuordnungen einer Task T folgende Ungleichung aufstellen:
Die bisherigen Betrachtungen beziehen sich auf global wirkende Suppressoren (Übernahme-Suppressor). Wir wollen nun noch den Einfluss lokaler Suppressoren (Last-Suppressor, Monitor-Suppressor) betrachten.
Die lokalen Suppressoren für Task T mögen sich im Bereich lsupmin … lsupmax bewegen
3.7.9 Stabilität des Hormonsystems
min
max
max supevn
supev min
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 51 - Prof. Dr. Uwe Brinkschulte
Die lokalen Suppressoren addieren sich zu den globalen Suppressoren. Damit lässt sich auch hier eine Ober- und Untergrenze für die Taskzuordnung angeben:
Obergrenze: Der schwächste lokale Suppressor wirkt. Die Zuordnung erfolgt, solange gilt:
nmax * supmin + lsupmin < evmax
Untergrenze: Der stärkste lokale Suppressor wirkt. Die Zuordnung erfolgt, solange gilt:
nmin * supmax + lsupmax < evmin
3.7.9 Stabilität des Hormonsystems
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 52 - Prof. Dr. Uwe Brinkschulte
Damit lässt sich die Anzahl Zuordnungen einer Task T bestimmen zu:
=> Stabilitätsbedingung für das Hormonsystem ohne Acceleratoren
Für alle Tasks T muss gelten: supmin > 0, supmax > 0
3.7.9 Stabilität des Hormonsystems
min
minmax
max
max
suplsupevn
suplsupev min (wenn der Wert der linken
oder rechten Seite < 0 wird, kann er zu 0 gesetzt werden)
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 53 - Prof. Dr. Uwe Brinkschulte
2. Suppressoren, Eignungswerte und AcceleratorenWir wollen nun auch den Einfluss der Acceleratoren betrachten.Zur Vereinfachung sollen zunächst wieder alle Suppressoren für Task T den gleicher Wert sup, alle Eignungswerte den gleichen Wert ev und alle an T geschickten Acceleratoren den gleichen Wert acc besitzen
Task T wird damit zugeordnet, solange gilt:
3.7.9 Stabilität des Hormonsystems
accaevsupn ** mit a: Anzahl Tasks, die Acceleratoren an T sendet
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 54 - Prof. Dr. Uwe Brinkschulte
Eine zugeordnete Task sendet Acceleratoren an alle verwandten Tasks. Dies gilt in beide Richtungen, d.h. wenn Ti und Tj verwandt sind, dann sendet Ti bei Zuordnung Acceleratoren an Tj und umgekehrt. Innerhalb einer Gruppe von v verwandten Tasks T1 .. Tv schicken die zugeordneten Tasks sich also gegenseitig Acceleratoren
Wir nehmen zur Vereinfachung zunächst an, dass alle Tasks in der Gruppe den gleichen Suppressor sup, Eignungswert ev und Accelerator acc besitzen.
ni sei die Anzahl Zuordnungen von Task Ti
3.7.9 Stabilität des Hormonsystems
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 55 - Prof. Dr. Uwe Brinkschulte
Für eine Gruppe von v verwandten Tasks erhalten wir somit folgendes System von Ungleichungen zur Taskzuordnung:
3.7.9 Stabilität des Hormonsystems
j
vj
naccevsupn
..2
1 **
j
jvj
naccevsupn
2
,..1
2 **
j
vj
v naccevsupn
1..1
**
.
.
.
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 56 - Prof. Dr. Uwe Brinkschulte
Dies lässt sich wie folgt umformen:
3.7.9 Stabilität des Hormonsystems
1
..1
1 *** naccnaccevsupn j
vj
.
.
.
2
..1
2 *** naccnaccevsupn j
vj
vj
vj
v naccnaccevsupn ***..1
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 57 - Prof. Dr. Uwe Brinkschulte
Um dieses Ungleichungssystem zu lösen, lösen wir zunächst das zugehörige Gleichungssystem:
3.7.9 Stabilität des Hormonsystems
1
..1
1 *** naccnaccevsupn j
vj
.
.
.
2
..1
2 *** naccnaccevsupn j
vj
vj
vj
v naccnaccevsupn ***..1
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 58 - Prof. Dr. Uwe Brinkschulte
Nach Umformung:
3.7.9 Stabilität des Hormonsystems
j
vj
naccevaccsupn
..1
1 *)(*
.
.
.
j
vj
naccevaccsupn
..1
2 *)(*
j
vj
v naccevaccsupn
..1
*)(*
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 59 - Prof. Dr. Uwe Brinkschulte
Subtraktion zweier beliebiger Gleichungen ergibt:
=> nk = nl
=> alle v Gleichungen haben die selbe Lösung
3.7.9 Stabilität des Hormonsystems
j
vj
j
vj
lk naccevnaccevaccsupnaccsupn
..1..1
**)()(*
0)()(* accsupnaccsupn lk
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 60 - Prof. Dr. Uwe Brinkschulte
Für eine beliebige Task Ti aus v verwandten Tasks ergibt sich somit:
3.7.9 Stabilität des Hormonsystems
ij
vj
i nvaccevnaccevaccsupn ***)(*..1
ii nvaccevsupn *)1(**
accvsupevni
*)1(
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 61 - Prof. Dr. Uwe Brinkschulte
Was bedeutet dies für die Lösung des ursprünglichen Ungleichungssystems?
Dazu interpretieren wir die Lösung grafisch:
kann als Schnittpunkt zweier Geraden aufgefasst werden.Im Schnittpunkt heben sich die Wirkungen gerade auf!
3.7.9 Stabilität des Hormonsystems
ii nvaccevsupn *)1(**
Gerade 1,Einfluss der
Suppressoren
Gerade 2,Einfluss der
Eignungswerte und Acceleratoren
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 62 - Prof. Dr. Uwe Brinkschulte
3 mögliche Fälle: 1. sup > (v – 1) * accSchnittpunkt im PositivenLinks vom Schnittpunkt sind die Eignungswerte und Acceleratoren stärker, d.h. es werden weiter Tasks zugeordnet. Sobald wir uns rechts vom Schnittpunkt befinden, überwiegen die Suppressoren, d.h. die Zuordnung endet
=> Task Ti wird mal zugeordnet
3.7.9 Stabilität des Hormonsystems
accvsup
evni*)1(
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 63 - Prof. Dr. Uwe Brinkschulte
2. sup = (v – 1) * accKein SchnittpunktFür jeden Wert von ni
überwiegen die Eignungs-werte und Acceleratoren.
=> Task Ti wird endlos zugeordnet
3.7.9 Stabilität des Hormonsystems
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 64 - Prof. Dr. Uwe Brinkschulte
3. sup < (v – 1) * accSchnittpunkt im NegativenFür jeden positiven Wert von ni
überwiegen die Eignungs-werte und Acceleratoren.
=> Task Ti wird endlos zugeordnet
3.7.9 Stabilität des Hormonsystems
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 65 - Prof. Dr. Uwe Brinkschulte
=> Das Hormonsystem ist stabil, wenn für jede Gruppe von v verwandten Tasks mit gleichen Werten für Suppressoren, Eignungswerten und Acceleratoren gilt:
sup > (v – 1) * acc
Dann wird jede Task Ti aus der Gruppe
mal zugeordnet
3.7.9 Stabilität des Hormonsystems
accvsup
evni*)1(
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 66 - Prof. Dr. Uwe Brinkschulte
Wir lassen nun für eine Gruppe von v verwandten Tasks verschiedene Eignungswerte im Bereich evmin … evmax , verschiedene Suppressoren im Bereich supmin … supmax und verschieden Acceleratoren im Bereichaccmin … accmax zu.Wir können nun wieder eine Ober- und eine Untergrenze der Task-Zuordnungen ermitteln.
Obergrenze:
Untergrenze:
3.7.9 Stabilität des Hormonsystems
maxmaxmaxminmax accaevsupn **
minminmaxmaxmin accaevsupn **
mit amax, amin: Maximale/minimale Anzahl Tasks, die Acceleratoren sendet
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 67 - Prof. Dr. Uwe Brinkschulte
Für die Obergrenze und Untergrenze lassen sich damit für eine Gruppe von v verwandten Tasks wieder ein System von Ungleichungen angeben:
3.7.9 Stabilität des Hormonsystems
maxmax j
vj
maxmaxmin naccevsupn
..2
1 **
.
.
.
maxmax j
jvj
maxmaxmin naccevsupn
2
,..1
2 **
maxmax j
vj
maxmaxminv naccevsupn
1..1
**
minmin j
vj
minmaxmax naccevsupn
..2
1 **
minmin j
jvj
minmaxmax naccevsupn
2
,..1
2 **
minmin j
vj
minmaxmaxv naccevsupn
1..1
**
Obergrenze
Untergrenze
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 68 - Prof. Dr. Uwe Brinkschulte
Dies lässt sich wie zuvor betrachtet lösen und führt zu folgender Stabilitätsbedingung:=> Das Hormonsystem ist stabil, wenn für jede Gruppe von v verwandten Tasks gilt: supmin > (v – 1) * accmax
Dann wird jede Task Ti aus der Gruppe
mal zugeordnet
3.7.9 Stabilität des Hormonsystems
maxmin
maxi
minmax
max
accvsupevn
accvsupev
*)1(*)1(
(Anmerkung: aus supmin > (v – 1) * accmax folgt sofort auch supmax > (v – 1) * accmin)
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 69 - Prof. Dr. Uwe Brinkschulte
Einfluss lokaler Acceleratoren und Suppressoren (z.B. Monitor-Accelerator/Suppressor): Die lokalen Acceleratoren und Suppressoren addieren bzw. subtrahieren sich von Eignungswert=> Es wird jede Task Ti aus der Gruppe
mal zugeordnet Da der Nenner gleich geblieben ist, ändert sich auch nicht das Stabilitätskriterium:
supmin > (v – 1) * accmax
3.7.9 Stabilität des Hormonsystems
maxmin
minmaxmaxi
minmax
maxminmax
accvsuplsuplaccevn
accvsuplsuplaccev
*)1(*)1(
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 70 - Prof. Dr. Uwe Brinkschulte
Begrenzte Reichweite von globalen AcceleratorenDie Reichweite der globalen Acceleratoren (z.B. Organ-Accelerator) ist begrenzt.Sie wirken nur in der Nachbarschaft des Senders. Im schlimmsten Fall wird eine Task außerhalb der Reichweite des Accelerators zugeordnet. Um dies zu berücksichtigen, kann in der Untergrenze accmin zu 0 gesetzt werden. Dies ändert aber ebenfalls nichts am Stabilitätskriterium.
Weitere Betrachtungen führen Abschätzungen der maximalen und minimalen Task-Anzahl auf einem Knoten, etc., siehe:
3.7.9 Stabilität des Hormonsystems
Ref: U. Brinkschulte, A. von Renteln, Analyzing the Behavior of an Artificial Hormone System for Task Allocation, ATC 2009, Brisbane, Australia
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 71 - Prof. Dr. Uwe 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
CDEVSH
CDEVSH
wwwCDwEVwSHwQU iii
i
3.7.10 Güte der Taskzuordnung
Ref: U. Brinkschulte, A. von Renteln, M. Pacher, Measuring the Quality of an Artificial Hormone System Based Task Mapping, Autonomics 2008, Turin, Italy
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 72 - Prof. Dr. Uwe 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
3.7.10 Güte der Taskzuordnung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 73 - Prof. Dr. Uwe Brinkschulte
Gütemaß für einen Knoten K
e
QUQU ET
i
i
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
3.7.10 Güte der Taskzuordnung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 74 - Prof. Dr. Uwe Brinkschulte
Gütemaß für das gesamte System
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
i
i
3.7.10 Güte der Taskzuordnung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 75 - Prof. Dr. Uwe Brinkschulte
Berechnung des Anteils SHi
sonst 1
1 wenn 1
ET
i
ET
ii 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
3.7.10 Güte der Taskzuordnung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 76 - Prof. Dr. Uwe Brinkschulte
Berechnung des Anteils EVi
Ki
ii
EmaxEEV
)(
Quotient des lokalen Eignungswertes Ei einer Task Ti auf Knoten K zu dem bestmöglichen Eignungswert dieser Task auf einem Knoten
3.7.10 Güte der Taskzuordnung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 77 - Prof. Dr. Uwe Brinkschulte
Berechnung des Anteils CDi
Berechnung über die Kommunikationsdistanz:
KDij = 1 + Anzahl Knoten zwischen Ti auf K und Tj auf dem zugehörigen Knoten
Gewichtete Kommunikationsdistanz:
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)
3.7.10 Güte der Taskzuordnung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 78 - Prof. Dr. Uwe Brinkschulte
Berechnung des Anteils CDi
ij VT
ji
ii
GKDvCD
vi Anzahl der zu Task Ti verwandten TasksVi Menge zu Task Ti verwandten Tasks GKDij Gewichtete Kommunikationsdistanz zwischen Ti auf K und Tj
3.7.10 Güte der Taskzuordnung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 79 - Prof. Dr. Uwe Brinkschulte
Evaluation: AHS gegen Load Balancing• 50 Tasks • 4x4 Prozessor Grid• Cluster von 4 verwandten Tasks
3.7.10 Güte der Taskzuordnung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 80 - Prof. Dr. Uwe Brinkschulte
Evaluation - Qualitätsentwicklung bei unterschiedlicher Taskanzahl
• 4x4 Prozessor Grid• Rot: 16 Tasks• Grün: 32 Tasks• Blau: 64 Tasks
3.7.10 Güte der Taskzuordnung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 81 - Prof. Dr. Uwe Brinkschulte
Evaluation – Unterschiedliche Anzahl verwandter Tasks
• 4x4 Prozessor Grid• Rot: 2 verwandte Tasks• Grün: 4 verwandte Tasks• Blau: 8 verwandte Tasks
3.7.10 Güte der Taskzuordnung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 82 - Prof. Dr. Uwe 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:
ET
i
K i
LD
3.7.10 Güte der Taskzuordnung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 83 - Prof. Dr. Uwe Brinkschulte
Beispiel:
14 Tasks => m = 14
Jede Task benötige 0,5 Knoten => LDi = 0,5
5 Knoten sind verfügbar => = 5
=>
57ET
i
K i
LD
3.7.10 Güte der Taskzuordnung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 84 - Prof. Dr. Uwe Brinkschulte
Möglichst gleiche Verteilung der Last => minimale Prozessorbelastung
Bei Gleichverteilung ergibt sich eine durchschnittliche Prozessorlast von
ET
i
Ka
i
LDL
57
ET
i
Ka
i
LDL
Beispiel:
3.7.10 Güte der Taskzuordnung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 85 - Prof. Dr. Uwe Brinkschulte
Somit ergibt sich der Anteil eines Knotens, welcher einer Task zur Verfügung steht, zu:
sonst 1
1 wenn 1a
aaL
LSH
Beispiel:
75
aSH
3.7.10 Güte der Taskzuordnung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 86 - Prof. Dr. Uwe 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:
CDEVSH
CDEVSH
CDEVSH
CDEVSH
wwwwwSHw
mwww
CDwEVwSHwmQU
a
a
max
)(
Beispiel:
905,02119
111
11751
CDEVSH
CDEVSH
wwwwwSHwQU a
max
3.7.10 Güte der Taskzuordnung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 87 - Prof. Dr. Uwe Brinkschulte
Demo Hormonsimulator
3.7.10 Güte der Taskzuordnung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 88 - Prof. Dr. Uwe Brinkschulte
3.7.11 Implementierung desHormonsystems
AHS (Artificial Hormone System) – Hormon-basierte Middleware nach den beschriebenen Prinzipien
Ref: A. von Renteln, U. Brinkschulte, Implementing and Evaluationg the AHS Organic Middleware - a First Approach, ISORC 2010, Carmona, Spain
Rechenknoten
AHSVerteilte Anwendung
Rechenknoten
AHSVerteilte Anwendung
Rechenknoten
AHSVerteilte Anwendung
Rechenknoten
AHSVerteilte Anwendung
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 89 - Prof. Dr. Uwe Brinkschulte
3.7.11 Implementierung desHormonsystems
AHS Aufbau (Modulstruktur)
AHS Interface
AHS Task Management
AHS Message Communication
AHS Hormone Communication
AHS Error Management
AHS List Management
AHS Log Management
AHS Basic OS Support
AHS Basic Communication Support
Distributed Application
Operating System Communication System
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 90 - Prof. Dr. Uwe Brinkschulte
3.7.11 Implementierung desHormonsystems
AHS InterfaceSchnittstelle zur AnwendungAHS Task ManagementEnthält allen hormon-spezifischen Code für Tasks, wie den Hormonzyklus, die Definition von Tasks, ...AHS Hormone CommunicationImplementiert die hormonspezifische Kommunikation mit Broadcast und Multicast zu Nachbarn. Es ist vollständig unabhängig von einem spezifischen KommunikationssystemAHS Message CommunicationImplementiert die botschaftsorientierte Singlecast Kommunikation. Es ist ebenfalls vollständig unabhängig von einem spezifischen Kommunikationssystem
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 91 - Prof. Dr. Uwe Brinkschulte
3.7.11 Implementierung desHormonsystems
AHS Log Management, AHS Error ManagementSind für Protokollierung und Fehlerbehandlung zuständigAHS List ManagementImplementiert grundlegende ListenfunktionalitätAHS Basic OS SupportRealisiert die Verbindung zum Betriebssystem. Hier werden Betriebssystems-spezifische Funktionen zur Threadverwaltung, Synchronisation, etc. realisiert. Dies ist das einzige Modul, welches bei Portierung auf ein anderes Betriebssystem geändert werden mussAHS Basic Communication SupportRealisiert die Verbindung zum Kommunikationssystem. Hier sind alle Kommunikationssystem-spezifischen Funktionen realisiert. Dies ist das einzige Modul, welches bei Portierung auf ein anderes Kommunikationssystem geändert werden muss
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 92 - Prof. Dr. Uwe Brinkschulte
3.7.11 Implementierung desHormonsystems
Komplett in ANSI C auf eine sehr portable Weise implementiert.
Nur zwei Module sind bei Portierung auf ein neues Betriebs- bzw. Kommunikationssystem anzupassen.
Kompakte Implementierung, 22 kBytes Code Größe bei Verwendung eines Visual C++ Compilers
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 93 - Prof. Dr. Uwe Brinkschulte
3.7.11 Implementierung desHormonsystems
Wesentliche AHS FunktionenSetup-Funktionen
AHSInit
Initialisiert das AHS, definiert eine eindeutige Id für den Rechenknoten. Über eine logische Netzwerk Id können weiterhin mehrere Instanzen des Hormonsystems gleichzeitig und unabhängig auf dem physikalischen Netzwerk arbeiten
AHSAddNeighbor
Definiert Nachbarschaftsbeziehungen zwischen Rechenknoten
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 94 - Prof. Dr. Uwe Brinkschulte
3.7.11 Implementierung desHormonsystems
Task-Definitions-Funktionen
AHSAddTask
Definiert eine neue Task, die auf dem Rechenknoten ausführbar ist. Hier werden auch die initialen Hormonwerte sowie weitere Taskparameter wie Priorität, etc. spezifiziert.
AHSAddRelatedTask
Definiert den Verwandtschaftsgrad zwischen auf dem Rechenknoten ausführbaren Tasks
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 95 - Prof. Dr. Uwe Brinkschulte
3.7.11 Implementierung desHormonsystems
Betriebs-Funktionen
AHSWakeup
Startet das Hormonsystem (den Hormonzyklus) auf allen Rechenknoten im Netzwerk. Jeder Knoten kann diese Funktion ausführen, es wird ein Weckhormon ausgeschüttet.
AHSSendToSleep
Stoppt das Hormonsystem auf allen Rechenknoten durch Auschüttung eines Schlafhormons.
Hier wird Wissen Wirklichkeit Organic Computing – Teil 3e, Folie 96 - Prof. Dr. Uwe Brinkschulte
3.7.11 Implementierung desHormonsystems
Botschafts-FunktionenDie Hormone sind für die Taskverteilung zuständig. Die Anwendung selbst kann auch über Hormone (Nutzerhormone) oder über Botschaften kommunizierenAHSSpreadMyUserHormone
Schüttet ein benutzerdefiniertes Hormon im System ausAHSGetMyUserHormoneLevel
Liefert die gegenwärtige Stärke eines benutzerdefinierten HormonsAHSSendMessage
Sendet eine Botschaft an eine TaskAHSReceiveMessage
Empfängt eine Botschaft von einer spezifischen oder beliebigen Task