Folie 5

Parallele und verteilte Simulation

• Simulation realer Systeme ist komplex und erfordert lange Laufzeiten und hohen Speicherbedarf.
• Die dezentrale Entwicklung einzelner Module, oft mit unterschiedlichen Werkzeugen, führt zur Simulatorkopplung.
• Eine Möglichkeit zur Effizienzsteigerung und Kopplung von Simulatoren ist der Einsatz paralleler und verteilter Systeme.

Parallele Simulation

• Abarbeitung findet auf einem Parallelrechner mit tatsächlichem oder virtuellem gemeinsamem Speicher statt.
• Ein zentrales Management der Ereignisliste dient als globale Datenstruktur.

Verteilte Simulation

• Abarbeitung erfolgt auf einem verteilten System.
• Die Ereignislisten werden dezentral verwaltet, wobei Prozesse über Nachrichtenaustausch kommunizieren.

Ziele paralleler/verteilter Simulation

• Erhöhung der Effizienz in Bezug auf Laufzeit und Speicherplatz.
• Integration verschiedener Module.
• Fehlertoleranz wird angestrebt.

Historische Entwicklung

• Stark ansteigendes Interesse an paralleler/verteilter Simulation in den späten 80er und frühen 90er Jahren.
• Es gab eine Vielzahl theoretischer Ansätze, aber nur wenige praktisch erfolgreiche Anwendungen.
• Eine Phase der Ernüchterung trat ein.
• Die parallele Abarbeitung von Replikationen ist erfolgreich.
• Parallele/verteilte Simulation ist ein interessantes Forschungsgebiet mit Problemen der parallelen Programmierung.
• In beschränkten Einsatzgebieten gibt es positive Ergebnisse, und es existiert Infrastruktur für parallele Simulationsprotokolle.

Unterscheidungsmöglichkeiten

• Parallelisierung durch mehrfache Abarbeitung eines Modells auf mehreren Prozessoren mit unterschiedlichen Zufallszahlen (MRIP).
• Parallelisierung durch Verteilung eines Modells auf mehreren Prozessoren (SRIP) mit Verteilung der Datenstruktur (räumlich) oder der Simulationszeit (zeitlich).
• MRIP ist einfacher zu realisieren als SRIP.

Anforderungen an verteilte/parallele Simulation

• Effizienzsteigerung zur Erzielung genauerer Resultate in vorgegebener Zeit und zur Analyse größerer Modelle.
• Einfache Realisierung mit möglichst wenigen Änderungen am Modell.
• Automatische Parallelisierung.
• Koppelbarkeit von Teilmodellen unterschiedlicher Simulatoren durch Festlegung der Schnittstellen.

5.1 MRIP (Multiple Replications in Parallel)

• Auf jedem Prozessor läuft ein Simulator.
• Simulatoren senden Zwischenergebnisse für alle Resultatmaße zu Kontrollzeitpunkten an den Analysator.
• Die Kontrollzeitpunkte können lokal definiert sein, z.B. alle t Modellzeiteinheiten oder alle k Ereignisse.
• Kommunikation zwischen Analysator und Simulatoren erfolgt über eine Kommunikationsschnittstelle wie Sockets oder MPI.

Einsatzgebiete von MRIP

• Replikationen einer Konfiguration (zentrale Auswertung im Analysator):
• Ein Modell wird mit einem Parametersatz auf mehreren Prozessoren analysiert.
• Voraussetzung sind unabhängige Zufallszahlenströme (ZZ-Ströme), um unabhängige Ergebnisse zu erhalten.
• Anwendung: Simulationsläufe, die auf einem Prozessor eine längere Laufzeit haben.
• Nachteil: mehrfache transiente Phase.
• Parameterstudien (zentrale Auswertung im Analysator):
• Ein Modell wird mit unterschiedlichen Parametern parallel auf mehreren Prozessoren analysiert.
• Voraussetzung: unabhängige oder korrelierte Zufallszahlenströme (ZZ-Ströme) je nach Auswertungsmethode.
• Anwendung: parametrische Studien bzw. Optimierung.
• Nachteil: bei sequentiellen Optimierungsansätzen nicht nutzbar.

Parallele Replikationen einer Konfiguration

• Notwendige Eigenschaften der Simulatoren umfassen die Erzeugung von P unabhängigen ZZ-Strömen.
• Die Ausgabe der Zwischenergebnisse erfolgt über die Kommunikationsschnittstelle.

Einordnung der zu erwartenden Leistungssteigerungen

• P ist die Anzahl der Prozessoren (homogen).
• D bezeichnet Beobachtungen zwischen Kontrollpunkten.
• Nmin ist die Gesamtzahl der benötigten Beobachtungen.
• Np ist die Anzahl der Beobachtungen, die von jedem Prozessor generiert werden.
• f ist der sequentielle Anteil, der von jedem Prozessor separat zu leisten ist, z.B. zur Simulation der transienten Phase.
• Unter der Annahme einer stationären Simulation werden f * Nmin Beobachtungen sequentiell erzeugt.
• Die P Prozessoren müssen (1-f) * Nmin Beobachtungen erzeugen, damit P * Np = (1-f) * Nmin gilt.

Speedup-Berechnung nach Amdahl

• Obere Schranke für Speedup S bei Verwendung von P Prozessoren:
• S = 1 / (f + (1-f)/P) falls P <= (1-f)*Nmin / D
• S = Nmin / (f*Nmin + D) falls P > (1-f)*Nmin / D
• Der maximale Speedup beträgt Smax = Nmin / (f*Nmin + D) bei Verwendung von Pmax = (1-f)*Nmin / D Prozessoren.
• In realen Simulationen sind Nmin, f und D von der Trajektorie abhängig, daher müssen Ergebnisse auf Basis von Erwartungswerten berechnet werden.
• Geringe sequentielle Anteile führen zu einer signifikanten Reduktion des Speedups.

Praktische Anwendung des Ansatzes

• Terminierende Simulation:

  • Analyse durch unabhängige Replikationen.
  • Simulation ohne sequentiellen Anteil (f = 0).
  • Unabhängigkeit der Replikationen, wenn ZZ-Ströme nicht überlappen.

• Stationäre Simulation:

  • Falls eine transiente Phase existiert, muss diese von jedem Prozessor durchlaufen werden.
  • f > 0 gilt in jedem Fall.
  • Tatsächlicher Wert von f hängt vom Verhältnis der Länge der transienten Phase zur Länge des beobachteten Intervalls ab, vergleichbar mit notwendiger Batchgröße einer sequentiellen Simulation.
  • Unabhängigkeit der Prozesse bei nicht überlappenden ZZ-Strömen.

Weitere Beobachtungen

• Gemessene Speedup-Werte ähneln den berechneten Werten.
• MRIP erfordert nur Kommunikation zwischen Simulatoren und Analysator, keinen zusätzlichen Synchronisationsaufwand.
• Der Kommunikationsaufwand kann durch die Wahl von D beeinflusst werden.
• Die Automatisierung des Ansatzes ist relativ einfach.
• Die Prozessoren müssen nicht identisch sein.
• Spezielle statistische Verfahren zur Erkennung der transienten Phase und zur Konfidenzintervallberechnung auf Basis von MRIP existieren.

Parallele Replikationen zur Online-Prognose

• Das Modell eines laufenden Systems wird mit aktuellem Zustand initialisiert, wobei parallele Replikationen den zukünftigen Zustand prognostizieren (falls Simulationszeit < Realzeit).
• Operative Entscheidungen (Scheduling, Personaleinsatz) basieren auf den Simulationsresultaten.
• Lizenbedingungen können die parallele Nutzung einschränken.

MRIP in OMNeT++

• OMNeT++ nutzt das Akaroa-System zur Realisierung von MRIP.
• Akaroa steuert n Simulationsprozesse, sammelt deren Resultate und berechnet Konfidenzintervalle.
• Die Simulationsprozesse werden abgebrochen, wenn die geforderte Genauigkeit erreicht ist.
• Zufallszahlenströme werden aus dem Generator cAkaroaRNG genutzt und von Akaroa verteilt.
• Relevante Resultatvektoren werden durch coutVector definiert.
• Die Ausgabe der Resultatvektoren erfolgt in Dateien mit Namenserweiterung des jeweiligen Hosts (Kommunikation über Dateischnittstelle).
• Keine Änderungen an Simulationsmodellen sind notwendig.

5.2 SRIP (Single Replication in Parallel)

• Allgemeinere Form der Verteilung durch Aufteilung des Simulationsprozesses in mehrere logische Prozesse (LPs), die jeweils einen Teil des Modells beschreiben.
• Prozessoren kommunizieren in der Regel zur Synchronisation und zum Ergebnisaustausch.
• Resultate werden in den Prozessoren während der Simulation oder durch einen separaten Analyseprozess berechnet.
• Die Aufteilung erfordert die Festlegung eines Teilmodellbegriffs und dessen Umsetzung in das Simulationsparadigma.

Mögliche Aufteilungen der Simulationsprozesse

• Raum ist definiert durch Zustandsvariablen,
• die Datenstruktur zur Zustandsbeschreibung wird verteilt. Ereignisse werden generiert basierend am lokalem Zustand.
• Zeit ist gegeben durch die Modellzeit, jeder Prozessor behandelt ein Teilintervall.
• Kombination beider Ansätze ist möglich.

5.2.1 Verteilung bzgl. der Zeit

• Die Zeitachse wird in Intervalle Ii = [Ti, Ti+1) unterteilt.
• Prozessor i simuliert das System im Intervall Ii.
• Theoretisch ist beliebige Parallelisierbarkeit möglich.
• Der Zustand am Ende von Ii muss dem Zustand am Anfang von Ii+1 entsprechen.
• Der Zustand am Ende des Intervalls muss vor Simulation des Intervalls bekannt sein, um Parallelität zu erreichen.
• Konkrete Anwendungen sind nur in speziellen Fällen möglich.

Beispiele für Verteilung bzgl. der Zeit

• Der Endzustand hängt nicht/kaum vom Anfangszustand ab.
• Ein falscher Anfangszustand ist reparierbar.
• Schätzung des Anfangszustands und erneute Simulation bei falscher Schätzung.
• Dynamische Wahl von Ti, sodass am Ende des Intervalls jeweils ein spezieller Zustand erreicht wird (z. B. Regenerationszustand, dann identisch zu MRIP).

Einschub: Regenerative Methode der Simulationsauswertung

• Voraussetzung: Es existiert ein Regenerationszustand, bei dem das zukünftige Modellverhalten unabhängig von der Vergangenheit ist.
• Beispiele: Jeder Zustand in Markov-Prozessen, der Zustand direkt nach Ankunft eines Kunden im leeren System (GI/GI/1), der Zustand nach dem kompletten Neustart in einem System mit Ausfällen und Reparaturen.
• Generell ist die Definition von Regenerationszuständen aber schwierig.
• Die Nutzung von Pseudoregenerationszuständen kann zu verfälschten Ergebnissen führen, aber bei geschickter Wahl keine signifikanten Fehler verursachen.

Typische Pseudoregenerationszustände

• Leeres oder volles System.

Auswertung regenerativer Simulationen

• Regenerationzyklus: Zeit zwischen dem Auftreten des Regenerationszustands.
• Der Messwert Xi gibt die Resultatgröße (akkumuliert) im i-ten Regenerationzyklus.
• τi kennzeichnet die Dauer des i-ten Regenerationzyklus (als Zeitdauer oder Anzahl Kunden oder Ausfälle).
• Ermittelt werden soll E[N] = E[X] / E[T].
• Der Schätzer Ñ = (Σi=1R Xi) / (Σi=1R τi) aus R Regenerationszyklen kann verzerrt sein solange R endlich ist.

Bestimmung von Konfidenzintervallen

• Zufallsvariablen X und T sind in der Regel nicht unabhängig.
• Die Konfidenzintervalle werden mit Standardformeln berechnet, die jedoch spezielle Schätzer für die Varianzen nutzen.

Parallelisierung der regenerativen Methode

• Definition von (Pseudo-)Regenerationspunkten.
• Simulation von Regenerationspunkt zu Regenerationspunkt ohne transiente Phase.
• Parallele Simulation der Regenerationszyklen mit nicht überlappenden Sequenzen von Zufallszahlen.
• Zentrale Sammlung der Ergebnisse in einem Auswertungsprozess.
• Abbruch der Simulation bei Erreichen der geforderten durch den Auswertungsprozess.

5.2.2 Verteilung bzgl. des Raumes

• Das Simulationsmodell wird in disjunkte Teile unterteilt.
• Jeder LP simuliert ein Teilmodell.
• Lokale Ereignisse werden lokal von einem LP simuliert.
• Globale Ereignisse erfordern Kommunikation zwischen den LPs.

Partitionierung des Modells

• Unterteilung der statischen Struktur in disjunkte Teile.
• Mengen von Stationen in einem Warteschlangennetz.
• Mengen von Stellen und Transitionen in einem Petri-Netz.
• Mengen von Ressourcen in einem prozessorrientierten Simulator.
• Subnetze in einem Netzwerksimulator.
• Die Partitionierung erfolgt unabhängig von der verwendeten Rechenarchitektur.

Modelltypspezifische Eigenheiten der Verteilung

• Partitionierung und Schnittstellen sind modell(typ)spezifisch.
• In manchen Fällen kann sich die Zahl der LPs zur Laufzeit ändern (nicht bei Warteschlangennetzen oder Petri-Netzen).
• Lokale Ereignisse können globale Effekte haben und Kommunikation erfordern.
• Die Verteilung der LPs auf Prozessoren ist ein zusätzliches Scheduling-Problem.

Ziel der Partitionierung und Aufteilung der LPs auf Prozessoren

• Möglichst geringe Kommunikation.
• Ereignisse sollen möglichst nur LPs auf einem Prozessor beeinflussen.
• Partitionierung des Modells so, dass fast alle Ereignisse LP-lokal sind.
• Scheduling, dass fast alle Ereignisse lokal auf einem Prozessor sind.
• Problem der Kommunikation zwischen LPs auf unterschiedlichen Prozessoren: Kommunikations Overhead.

Synchrones Vorgehen

• Existenz einer globalen Uhr mit Zeittakt Δ.
• Synchronisation der Prozesse alle Δ Zeiteinheiten.
• LP simuliert die Ereignisse im festen Intervall [i·Δ, (i+1)·Δ) .
• Am Intervallende Synchronisation und Nachrichtenaustausch zwischen LPs.
• Overhead durch zusätzliche Kommunikation alle Δ Zeiteinheiten.
• Einfach zu realisieren, aber oft ineffizient und nur auf spezielle Modelltypen anwendbar.

Asynchrones Vorgehen

• LPs simulieren asynchron ihre Teilmodelle (lokale Zeit LP; lti).
• Es gibt lokale Uhren, aber keine globale Uhr.
• Interaktion zwischen LPs erfolgt über Nachrichten mit lokalem (!) Zeitstempel.
• Empfangene Nachrichten werden im Simulationslauf des Empfängers berücksichtigt.
• Theoretisch breit anwendbar, aber mit dem Problem der Kausalitätsverletzung.

Kausalitätsverletzung

• Ein LP empfängt eine Nachricht eines anderen LPs (mit dem Zeitstempel t), die kleiner als die lokale Zeit (lt) ist.
• Die Effizienz hängt stark von der Systemstruktur ab.
• Kausalitätsverletzungen werden durch Protokolle vermieden (konservative) oder behoben (optimistische).

Konservative Protokolle

• Zuverlässige FIFO-Kanäle zwischen kommunizierenden LPs sind Voraussetzung.
• Jeder Kanal ist Ausgangs- Einngangskanal für einen LP.
• LP i hat die lokale Uhr lt i.
• Ereignisse erhalten lokale Zetsatempel.
• Alle Empfänger erhalten einen Zeteitszempel t = lt.
• LP führt ein Ereigniss zum Zeitpunkt lt aus, sofern immer K_t > lt ist.
• Blockierung des LP bei leerenen Eingabekanälen.
• Pufferüberläufe und Deathlocks können vorkommen.

Deadlocks

• Deadlocks werden durch das Senden von Nullnachrichten mit Zeitstempel vermieden.
• Die Garantien der Botschaften verlangen, keine Nachrichten mit Zeitstempel t kleiner eines anderen zu verwenden.
• Nullnachrichten erfordern lokalen Ausblick.
• Bei jedem Zyklus eine Zeitverzögerung.

Verbesserungen

• Nullznachrichten werden immer auf Abfrage versendet
• Nachrichten immer nur von geblockten LPs
• Löschen nicht aktuelleer Nuüllnachrichten
• Bündelung von Nullnachrichten.

Alternative Deadlockvermeidung

• Entdeckung der Deadlocks durch gobalen Prozess.
• Kreisende Marker können auf Deadlocks aufdmerksam machen.
• Marker werden durch Zyklen besucht.

Weitere konservative Vorgehensweisen

• Flusskontrollen zwischen den LPs können Pufferüberläufe verhindern.
• Der Vorteil ist die relativ einfache Realisierung.
• Es ist ein Basisasatz für Simualationskupplung.

Optimistische Protkolle

• LPs führen immer das lokale Ereignis aus.
• Zustand wird bei Empfang wieder zurückegesetzt.
• FIFO-Übertragung nicht notwendig.

Weitere Merkmale optimistischer Protokolle

• Antinachrichten werden versendet.
• Die potentielle Paralleilität wird besser genutzt.
• Es entstehen größere Overheads und einen HÖherer Verwaltungsaufwand.

Behandlung von Antinechanrichten

• Es können nicht bearbeitete Nachrichten gelöscht werden.
• Bei einem aggressiven Vorgehen, werden Antinateiben versendet.
• Bei einem lazy Vorgehen, werden Nachrichten nicht erneut versendet.
• Mittels Modell können deutliche Vorteile erzielt werden.

Speicherverwaltung beim Arbeiten mit Antinachrichten

• Prozesse umfassen Zeitpunkt der Nachrichten und ihre Variationen.
• Eine untere Schränke von Wert wird mit Algorithmus bestimmt.
• Die Zustände können zum Zeitpunktt < Gelöscht werden.

Behandlung von Speichermangel

• Inkrementelle Zustandsspeicherung kann den Speichemangel behandeln.
• Künstliches Zurücksetzten von LPs kann den Speicher zusätzlich entlasten.
• Ein Kompromiss muss dennoch gefunden werden.

Hybride Protokolle

• Optimismus in konservativen Protokollen.
• Konservatismus in Optimisistischen Protokollen.
• Verwendungsspezifische Protokolle.

Parallele Simulation in OMNET++

• OMNET++ unterstützt parallele Simulation mit Nullnachrichten.
• Module werden auf Prozessoren aufgeteilt.
• Der Datenaustausch geschieht mittels MPI.

Nachteile in OMNET++

• Unterschiedliche Prozessoren nutzen nur Datenaustaushc.
• Nur statische Topologien.
• Keine Variablen.

Konfiguration einer parallelen Simulation

• Die Partitionierung des Modells wird konfiguriert
• Die Datenaustauschklasse und der Name des Protokolls werden angegeben

Weitere Ansätze

• Infrastruktur zur Realisierungen parallele Simulationen.
• Prototypische Java Bibliothek.
• Asynchrone Paralleilität.