6. Organic Computing - es.cs.uni-frankfurt.de · Einige wichtige Begriffe: ... Rückführung (Verwandtschaft zur Regelungstechnik) ... Aktuator Evaluator Monitor Schnittstelle

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


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



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



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



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



Verbreiteter technischer Ansatz: Observer/Controller Struktur

Rückführung (Verwandtschaft zur Regelungstechnik)

Kontrolle emergenten Verhaltens

ObserverController

System

6



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

http://www.acm.org/sigs/sigois/auto/Main.html/

http://www.research.ibm.com/autonomic/

http://www.cordis.lu/ist/fet/co.htm

http://www.bmbf.de/foerderungen/5150.php

http://www.sfb637.uni-bremen.de/

http://www.grk1194.uni-karlsruhe.de/home.php

http://www.organic-computing.de/SPP



DFG Schwerpunktprogramm 1183 “Organic Computing”

Quelle: DFG Forschungsschwerpunkt 1183

8



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



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



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



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



CARSoC Hardware

13



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



Organic Management

Auftrag

Dienst

Ressource

bestimmt, welcher Auftrag von welchem Dienst ausgeführt wird

bestimmt, welcher Dienst auf welcher Ressource abläuft

15



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



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



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



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



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



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



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



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



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



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



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



Res.1

Res. 2

Res. 3

Res. n

Koord.

Phase 1: Ausschreibung einer Ausführungspfades (Aufgabenbeschreibung und Parameter)

A

A

A

A

27



Res. 1

Res. 2

Res. 3

Res. n

Koord.

Phase 2: Eingang der Gebote

B1

B3

B2Bn

28



Res. 1

Res. 2

Res. 3

Res. n

Koord.

Phase 3: Zuschlag an eine (oder mehrere) Ressourcen (Kontrakt)

K

29



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


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.2 DodOrg - Digital On Demand Computing Organismvon der Biologie zu einem Organic Computing System

31



Middleware

Mon

itorin

g

Pow

er M

anag

emen

t

Tasks

PZ PZ PZ PZ PZ PZ PZ







Virtuelle Organe

Anwendung DodOrg-Komponenten

•Anwendung

•Middleware

•Monitoring

•Power Management

•Prozessorzellen

32



• 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


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



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



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



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



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



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



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


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

41


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

42



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


Live-Demo


44



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



=> Ü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



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



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



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



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


Tasks Tj ∈ Mγ

Warte (tSE)

tES = 0


i:= i+1

Erhöhter Eignungswert für Task Tk gesendet,

Tk Siegerkandidat? Entscheide

über Task Tk

nein

ja

Verbesserung des Zeitverhaltens

50


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



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


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


Tasks Tj ∈ Mγ

Warte (tSE)

tES = 0


i:= i+1

Erniedrigter Eignungswert für

Task Tk empfangen, Tk

Siegerkandidat? Entscheide über Task Tk

nein

ja

53



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



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



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



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



Anzahl Tasks

Anz

ahl Z

ykle

nSimulationsergebnisse

58



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



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


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

6.4.5 Datenaufkommen der Hormonausschüttung

61


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.

62


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.


∑∈

⋅=γ

γ

ETi

i

vDaDm

63


=> Datenaufkommen eines beliebigen Knotens zu Beginn und im eingeschwungenen Zustand:


eγ = 0 zu Anfang

kγ = 0 am Ende

γγ kDeDbAnfang ⋅=

0DmAnfang =γ

γγ eDsDbEnde ⋅=

∑∈

⋅=γ

γET

iEndei

vDaDm

64


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γ


∑ ∑∈ ∈

+=ΩK ΦK

DmDbDδ γδ

δδγ

65


=> Gesamtes Datenaufkommen an einem beliebigen Knotens zu Beginn und im eingeschwungenen Zustand


∑ ∑∈ ∈

+=ΩK ΦK

AnfangAnfangAnfang DmDbDδ γδ

δδγ

∑∈

⋅=ΩK

kDeδ

δ

∑ ∑∈ ∈

+=ΩK ΦK

EndeEndeEnde DmDbDδ γδ

δ δγ

∑ ∑ ∑∈ ∈ ∈

⋅+⋅=ΩK ΦK ET

ii

vDaeDsδ γδ δ

δ

66


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 ∈∈∈⋅+⋅=

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


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

68


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)


69


Mit diesen Werten ergibt sich:

Bei einer angenommenen Zykluszeit von 100msec (tSE + tES) ergibt sich daher ein Hormon-Datendurchsatz von:


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


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


71


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++

⋅+⋅+⋅=

γγγγ

6.4.6 Güte der Taskzuordnung

72


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


73


Gütemaß für einen Knoten Kγ


γ

γ

γγ

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


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

ii

∑∑ ∑Ω∈Ω∈ ∈

⋅== γγ γ

γγγ

75


Berechnung des Anteils SHiγ


≥=

∑∑ ∈∈

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


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

77


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:


≥⋅⋅

=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


Berechnung des Anteils CDiγ


∑∈

=

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


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

iK i

LD

80


Beispiel:

14 Tasks => m = 14

Jede Task benötige 0,5 Knoten => LDiγ = 0,5

5 Knoten sind verfügbar => ω = 5

=>


ωγγ

γ =>=∑∑∈Ω∈

57ET

iK i

LD

81


Möglichst gleiche Verteilung der Last => minimale Prozessorbelastung

Bei Gleichverteilung ergibt sich eine durchschnittliche Prozessorlast von


ωγγ

γ∑∑∈Ω∈= ET

iK

ai

LDL

57

==∑∑∈Ω∈

ωγγ

γ

ETi

Ka

i

LDL

Beispiel:

82


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

83


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

84


Live-Demo


85

Documents

6. Organic Computing - es.cs.uni-frankfurt.de · Einige wichtige Begriffe: ... Rückführung (Verwandtschaft zur Regelungstechnik) ... Aktuator Evaluator Monitor Schnittstelle