Simultane Ereignisse bei der diskreten, ereignisgesteuerten Simulation von Rechnernetzen

Die diskrete, ereignisgesteuerte Simulation (DES) ist eine weit verbreitete Technik zur Analyse und Leistungsbewertung von Systemen. Auf Grund ihrer einfachen Grundstruktur ist die DES für alle System einsetzbar, deren Abläufe durch Ereignisse zu diskreten Zeitpunkten modelliert werden können. Sämtliche Ereignisse des Systems sind in einer Ereignisliste gespeichert und werden von einem Scheduler in der Reihenfolge ihrer Zeitstempel ausgeführt.

Eine bekannte Herausforderung bei der diskreten, ereignisgesteuerten Simulation ist das Auftreten von simultanen Ereignissen. Dies sind zwei oder mehr Ereignisse, die den gleichen Zeitstempel haben, also exakt gleichzeitig ausgeführt werden sollen. Da verschiedene Ausführungsreihenfolgen simultaner Ereignisse zu unterschiedlichen Zuständen, und damit zu unterschiedlichen Simulationsergebnissen führen können, steht der Scheduler vor der Frage, wie er bei simultanen Ereignissen handeln soll. Üblicherweise bestimmen Simulations-Tools in einem solchen Fall mit Hilfe von Tie-Breaking-Rules gezielt eine Ausführungsreihenfolge, um ein reproduzierbares Simulationsergebnis zu gewährleisten.

Es ist allerdings nicht ersichtlich, warum Tie-Breaking-Rules eine Lösung darstellen: Indem nur eine von u. U. vielen möglichen Ausführungsreihenfolgen simultaner Ereignisse ausgewählt wird, werden alle anderen Simulationsergebnisse implizit als inkorrekt eingestuft. Dabei können viele oder sogar sämtliche Ausführungsreihenfolgen gleichermaßen zu korrekten Simulationsergebnissen führen. Es ist deshalb sinnvoll, dem Benutzer der Simulation Möglichkeiten zur Verfügung zu stellen, die Auswirkungen simultaner Ereignisse auf Simulationsergebnisse zu untersuchen.

Mit dieser Zielsetzung sind im DFG-Projekt Simultane Ereignisse bei der diskreten, ereignisgesteuerten Simulation von Rechnernetzen Methoden entwickelt worden, mit denen verschiedene Ausführungsreihenfolgen simultaner Ereignisse analysiert werden können: Mit so genannten Branching-Verfahren kann die Simulation bei einem Auftreten simultaner Ereignisse verzweigt werden. Die konzipierten Branching-Verfahren sind im Simulationstool MOOSE praktisch umgesetzt worden, wobei verschiedene Techniken zur Steigerung der Effizienz verwendet wurden.

Nachdem MOOSE zunächst als sequentielles Simulationstool realisiert wurde, sind im weiteren Projektverlauf verschiedene Möglichkeiten der Parallelisierung verfolgt worden. Im ersten Ansatz wurde MOOSE so erweitert, dass bei einem Auftreten simultaner Ereignisse mehrere Simulationszweige auf weitere zur Verfügung stehende Rechner verteilt werden können, um durch die parallele Berechnung die Gesamtlaufzeit der Simulation zu reduzieren. Im zweiten Ansatz wurde MOOSE schließlich zu einem echten verteilten Simulationstool weiterentwickelt, bei dem ein Simulationsszenario in mehrere logische Prozesse aufgeteilt und auf die beteiligten Rechner verteilt wird. In diesem Fall simulieren mehrere Rechner stets gemeinsam an einem Simulationsszenario. Zur Synchronisation der Prozesse wurden sowohl konservative als auch optimistische Synchronisationsmechanismen verwendet und in beiden Fällen Konzepte zur Behandlung und Untersuchung simultaner Ereignisse entwickelt. Dadurch wurde ein wichtiger Beitrag im Forschungsgebiet der verteilten Simulation geleistet.