Statisches Scheduling in RT-Netzwerken Betrachtung zweier Ansätze

Statisches Schedulingin RT-Netzwerken

Betrachtung zweier Ansätze

Marcus Merzmarcus.merz@ourarsenal.com

21.01.2005

Marcus Merzmarcus.merz@ourarsenal.com

Inhalt des Vortrages

• Einführung• Backtracking• Antz• Agenten• Rückblick /Ausblick

Einführung

Marcus Merzmarcus.merz@ourarsenal.com

Marcus Merzmarcus.merz@ourarsenal.com

Folie 4

Inhalt

Einführung

Backtracking

Antz

Agenten

Rückblick / Ausblick

Wissenswertes

•nur harte Echtzeit wird betrachtet

•Gesamtzykluszeit = kgV aller Zyklen

•kleinster Zeitschritt = ggT aller Sendezeiten

•Offset = Abstand Nullzeit bis ersten Sendung

Backtracking

Marcus Merzmarcus.merz@ourarsenal.com

Marcus Merzmarcus.merz@ourarsenal.com

Folie 6

Inhalt

Einführung

Backtracking

Antz

Agenten

Rückblick / Ausblick

Backtracking

•klassisches Verfahren

•betrachtet alle Konstellationen

•erschöpfende Suche

•rekursiv leicht formulierbar

•hoher Resourcenbedarf

Marcus Merzmarcus.merz@ourarsenal.com

Folie 7

Inhalt

Einführung

Backtracking

Antz

Agenten

Rückblick / Ausblick

Ablauf

Schedule(KL-Liste) {

1. wähle KL aus KL-Liste

2. Keine KL mehr vorhanden -> fertig

3. bestimme nächsten Sende-Offset

4. Falls kein Offset mehr vorhanden gehe zu 9.

5. prüfe auf Konflikt

6. bei Konflikt gehe zu 3.

7. Schedule(Restliche KLs)

8. Falls Misserfolg bei 7. meldet gehe zu 3.

9. Melde Mißerfolg

}

Marcus Merzmarcus.merz@ourarsenal.com

Entscheidungsbaum

KL-Wahl

Offset-Wahl

Entscheidungsbaum wird ggf. komplett durchgearbeitet

......

... ..

. .

.........

...... ... ...

.

.

.

Marcus Merzmarcus.merz@ourarsenal.com

Folie 9

Inhalt

Einführung

Backtracking

Antz

Agenten

Rückblick / Ausblick

• Priorisierung der KL (# Konflikte, RT-Klasse)

• Verwendung sinnvoller Offsets

• Änderung der Konfliktauflösung

• wie gehabt: Offsets durchgehen

• Backtracking nur auf Konflikt-KL

• Notnagel: normales Verhalten

Verbesserungen

Marcus Merzmarcus.merz@ourarsenal.com

Folie 10

Inhalt

Einführung

Backtracking

Antz

Agenten

Rückblick / Ausblick

• Algorithmus springt durch den Entscheidungsbaum

->Verringerung des Backtracking

-> schneller

• Lösung wird immer noch gefunden

• Erhöhung der logischen Komplexität

Folgen der Verbesserung

Marcus Merzmarcus.merz@ourarsenal.com

Folie 11

Inhalt

Einführung

Backtracking

Antz

Agenten

Rückblick / Ausblick

Fazit

• Basisalgorithmus einfach

• Verbesserung komplex -> fehlerträchtig

• wg. Komplexität schwer auf andere RT-Klassen erweiterbar

• schwer nachvollziehbar

Antz

Marcus Merzmarcus.merz@ourarsenal.com

Marcus Merzmarcus.merz@ourarsenal.com

Folie 13

Inhalt

Einführung

Backtracking

Antz

Agenten

Rückblick / Ausblick

ACO (Ant Colony Optimization) Ansatz

• Abbildung des Problems auf eine Ameisenkolonie

• jede Ameise erfüllt nur einfache Aufgaben

• Kommunikation erfolgt nur über Duftstoffe

• viele Ameisen zusammen lösen ein komplexes Problem (z.B. Shortest Path)

-> emergente Intelligenz

Marcus Merzmarcus.merz@ourarsenal.com

Folie 14

Inhalt

Einführung

Backtracking

Antz

Agenten

Rückblick / Ausblick

Netzwerk aus Ameisensicht

• Netzwerk = Ameisenhaufen

• Teilnehmer = Kammern

• Switches = Abzweigungen

• Verbindungen = Tunnel

• KL = Wege

• Kleinster Zeitschritt = Paket

• Sendung = mehrer Pakete

Marcus Merzmarcus.merz@ourarsenal.com

Folie 15

Inhalt

Einführung

Backtracking

Antz

Agenten

Rückblick / Ausblick

Problemspezifisches

• exklusive Nutzung der Tunnel

• Ameisen vertreten je eine KL

• Ameisen haben eine gewisse Priorität

• Markierungen identifizieren Ameisen (ID + Priorität) = Duftstoff

Marcus Merzmarcus.merz@ourarsenal.com

Folie 16

Inhalt

Einführung

Backtracking

Antz

Agenten

Rückblick / Ausblick

Aufgaben einer Ameise

• Transport eines Pakets

• Durchführung einer Sendung

• Markierungen setzen

• Markierungen bei Konflikt entfernen

• Zyklus einhalten

• Erfolge merken

• eigene Priorität ändern

Marcus Merzmarcus.merz@ourarsenal.com

Folie 17

Inhalt

Einführung

Backtracking

Antz

Agenten

Rückblick / Ausblick

Ablauf eines Schedulingschrittes

Dauer: 1. Paket

1. alle Ameisen markieren bei Bedarf ihren Weg

2. Ameisen gehen nacheinander ihre Wege zurück (nach Folge Ihrer Priorität)

o ggf. Entfernung ihrer Markierung

3. Alle Ameisen fertig -> neuer Schritt

Marcus Merzmarcus.merz@ourarsenal.com

Folie 18

Inhalt

Einführung

Backtracking

Antz

Agenten

Rückblick / Ausblick

Ablauf eines Schedulingschrittes

TN TN

TN TN TN TN TN TN

TN

TN TN

TN

SW

SW

SW

SWSW

SW

SW

TN

Alle Ameisen markieren ihren Weg

TN TN

TN TN TN TN TN TN

TN

TN TN

TN

SW

SW

SW

SWSW

SW

SW

TN

Rot prüft auf stärkere Markierungen auf dem Weg -> nein -> Rot gewinnt

TN TN

TN TN TN TN TN TN

TN

TN TN

TN

SW

SW

SW

SWSW

SW

SW

TN

Grün prüft auf stärkere Markierungen auf dem Weg -> Rot ist stärker

TN TN

TN TN TN TN TN TN

TN

TN TN

TN

SW

SW

SW

SWSW

SW

SW

TN

Grün hat verloren -> Entfernung der Markierung

TN TN

TN TN TN TN TN TN

TN

TN TN

TN

SW

SW

SW

SWSW

SW

SW

TN

Blau prüft auf stärkere Markierung auf dem Weg -> nein -> Blau gewinnt

TN TN

TN TN TN TN TN TN

TN

TN TN

TN

SW

SW

SW

SWSW

SW

SW

TN

Priorität:

1. Rot

2. Grün

3. Blau

Marcus Merzmarcus.merz@ourarsenal.com

Folie 19

Inhalt

Einführung

Backtracking

Antz

Agenten

Rückblick / Ausblick

Falsche Abfolge beim Scheduling

TN TN

TN TN TN TN TN TN

TN

TN TN

TN

SW

SW

SW

SWSW

SW

SW

TN

Alle Ameisen markieren ihren Weg

TN TN

TN TN TN TN TN TN

TN

TN TN

TN

SW

SW

SW

SWSW

SW

SW

TN

Rot prüft auf stärkere Markierungen auf dem Weg -> nein -> Rot gewinnt

TN TN

TN TN TN TN TN TN

TN

TN TN

TN

SW

SW

SW

SWSW

SW

SW

TN

Blau prüft auf stärkere Markierungen auf dem Weg -> Grün ist stärker

TN TN

TN TN TN TN TN TN

TN

TN TN

TN

SW

SW

SW

SWSW

SW

SW

TN

Priorität:

1. Rot

2. Grün

3. Blau

Blau hat verloren -> Entfernung der Markierungen

TN TN

TN TN TN TN TN TN

TN

TN TN

TN

SW

SW

SW

SWSW

SW

SW

TN

Grün prüft auf stärkere Markierungen auf dem Weg -> Rot ist stärker

TN TN

TN TN TN TN TN TN

TN

TN TN

TN

SW

SW

SW

SWSW

SW

SW

TN

Grün hat verloren -> Entfernung der Markierungen

TN TN

TN TN TN TN TN TN

TN

TN TN

TN

SW

SW

SW

SWSW

SW

SW

TN

Marcus Merzmarcus.merz@ourarsenal.com

Folie 20

Inhalt

Einführung

Backtracking

Antz

Agenten

Rückblick / Ausblick

Priorisierung

• wichtigster Mechanismus

• Ameisen ändern Priorität

• + falls der Bedarf steigt

• + bei Weg-Gewinn

• - je regelmäßiger eine Sendung durchgeht

-> Chance für alle Ameisen

Marcus Merzmarcus.merz@ourarsenal.com

Folie 21

Inhalt

Einführung

Backtracking

Antz

Agenten

Rückblick / Ausblick

Wie ergibt sich ein Plan?

• System erreicht stabilen Zustand

• alle Ameisen sind immer erfolgreich

• die Prioritäten sind ausgeglichen

• Zeitstempel des ersten Pakets einer Sendung = Offset

Marcus Merzmarcus.merz@ourarsenal.com

Folie 22

Inhalt

Einführung

Backtracking

Antz

Agenten

Rückblick / Ausblick

Fazit

• Einfacher Ansatz

• Komplexität entsteht durch Zusammenwirken einfacher Algorithmen

• Leicht zu implementieren

• Leicht erweiterbar

• Brute-Force Suche

• Problem: Abbruchbedingung!!!

Agenten

Marcus Merzmarcus.merz@ourarsenal.com

Marcus Merzmarcus.merz@ourarsenal.com

Folie 24

Inhalt

Einführung

Backtracking

Antz

Agenten

Rückblick / Ausblick

Einführung

• Agentensystem löst eine Aufgabe

• Jeder Agent versucht seine Aufgabe zu erfüllen

• Interaktion mit anderen Agenten

• Verhandlungen / Diskussion der Argumente

• mode(rner) Ansatz

Marcus Merzmarcus.merz@ourarsenal.com

Folie 25

Inhalt

Einführung

Backtracking

Antz

Agenten

Rückblick / Ausblick

Agenten beim Scheduling

• allg. Ziel: Schedule erstellen

• egoistisches Ziel: Anforderungen einer KL erfüllen

• Argumente für Verhandlungen z.B.:

• Wichtigkeit

• Bedarf (Ablauf des Zyklus)

• aktuelle Sendung beenden

Marcus Merzmarcus.merz@ourarsenal.com

Folie 26

Inhalt

Einführung

Backtracking

Antz

Agenten

Rückblick / Ausblick

Fazit

• benötigt ausgeklügelte Synchronisation

• erweiterbar über Abänderung der Verhandlungstaktik

• gute Nachvollziehbarkeit

Rückblick /Ausblick

Marcus Merzmarcus.merz@ourarsenal.com

Marcus Merzmarcus.merz@ourarsenal.com

Folie 28

Inhalt

Einführung

Backtracking

Antz

Agenten

Rückblick / Ausblick

Rückblick

• Ansätze zeigen Schwierigkeit des Problems

• Backtracking

+ terminiert, erschöpfend

- resourcenhungrig, schwer erweiterbar, komplex

• Antz

+ erweiterbar, leicht implementierbar

- Abbruchbedingung unklar, nur eine Lösung, Brute-Force

Marcus Merzmarcus.merz@ourarsenal.com

Folie 29

Inhalt

Einführung

Backtracking

Antz

Agenten

Rückblick / Ausblick

Ausblick

• Ameisenlösung vielversprechend

• geschickte Priorisierung nötig

• Abbruchbedingung ist zu bestimmen

• mehr Intelligenz für Ameisen -> Verringerung der Berechnungsschritte

Das wars....

Noch Fragen?Marcus Merz

marcus.merz@ourarsenal.com