Sprungmarken

Servicenavigation

Hauptnavigation

Sie sind hier:

Hauptinhalt

Abschlussarbeiten

aus dem Bereich "Modellierung und Simulation":

Im folgenden werden mehrere Themen stichwortartig skizziert. Eine genauere Festlegung der Inhalte erfolgt nach Absprache mit dem Ansprechpartner/Betreuer.


Verteilungen/Prozesse


1 Sammlung von Traces (Bachelorarbeit; Ansprechpartner: Dr. Bause)
   • Sammlung von Traces aus Internetquellen mit Schwerpunkt auf Performance-relevanten Daten.
   • Festlegung eines Standardformats inkl. Konvertierungstools zur Nutzung in anderen Tools.
   • Fitten der Verteilung/Prozess mit ein bis zwei Verfahren aus ProFiDo.
   • Klassifizierung/Einschätzung der Traces aus Sammlung in leicht/mittel/schwer zu ”fittende” Traces.


2 Vergleich verschiedener Algorithmen aus ProFiDo (Bachelorarbeit; Ansprechpartner: Dr. Bause)
   • Ggf. aufbauend auf obiger Trace-Sammlung experimentelles Herausfinden ”guter” Programm-Parameter.
   • Heuristische Regeln für die Wahl des Verfahrens anhand trace-spezifischer Kenngrößen.
   • Toolunterstützung zur Bestimmung geeigneter Programm-Parameter.

3 Analyse der Anpassungsgüte in ProFiDo (Masterarbeit; Ansprechpartner: Prof. Dr. Buchholz)
   • Graphische Darstellung der Anpassungsgüte theoretischer Verteilungen an empirische Daten durch QQ-, PP- oder Box-Plots.
   • Integration von Anpassungstest wie χ2 -, KS- oder AD-Test.
   • Falls möglich Nutzung von Standardsoftware wie R oder Python-Bibliotheken zur Realsierung der Komponenten.
   • Unterstützung bei der vergleichenden Bewertung mehrerer angepasster Verteilungen.

4 Untersuchung von Korrelationen in Fehlertraces und ihrer Modellierung durch MAPs (Masterarbeit; Ansprechpartner: Prof. Dr. Buchholz)
   • Analyse von Fehlertraces auf inhomogene und korrelierte Ausfallzeiten.
   • Visualisierung der Abhängigkeiten.
   • Anpassung von MAPs an die Daten mit Hilfe von ProFiDo.
   • Test der Anpassungsgüte.

5 Methoden zur Parameterschätzung von Standardverteilungen und ihre Integration in ProFiDo (Bachelorarbeit; Ansprechpartner: Prof. Dr. Buchholz)
   • Implementierung der ML-Schätzer für Standardverteilungen aus Law.
   • Bestimmung der Verteilungsparameter anhand ausgewählter Traces.
   • Vergleich verschiedener Verteilungen untereinander und mit angepassten Phasenverteilungen auf Basis ausgewählter Kennzahlen (Momente, Quantile, Histogramme).


Analytische/Numerische Modelle/Verfahren


6 M/M/1 oder G/G/1 Resultate (Bachelorarbeit; Ansprechpartner: Dr. Bause)
   • umfassende Darstellung der Resultate aus der Literatur. Die Resultate sollten neben stationären auch transiente Ergebnisse beinhalten.
   • Tool zur M/M/1 od. G/G/1-Analyse erstellen, welches alle theoretischen Resultate anzeigt bzw. visualisiert.


7 Markov Decision Processes (Bachelorarbeit; Ansprechpartner: Dr. Bause)
    • Tool/GUI zur Definition MDPs.
    • Visualisierung elementarer Algorithmen (value/policy iteration).
    • Anwendung auf konkrete Beispiele,
       z.B. analog Agent walk Beispiel, siehe
        http://www.microveggies.com/csci/index.php/9-csci-3202-lecture-notes/31-lecture12-markov-decision-processe
        https://mpatacchiola.github.io/blog/2016/12/09/dissecting-reinforcement-learning.html


8 Schrankenberechnung für Concurrent MDPs (Masterarbeit; Ansprechpartner: Prof. Dr. Buchholz)
    • Vorstellung der Modelle aus [6] und [14].
    • Beschreibung deterministischer und zyklischer Politiken für CMDPs.
    • Berechnung von Schranken für deterministische stationäre Politiken mit Hilfe von ILPs und Schnittebenen (als Erweiterung des Ansatzes aus [6]).



Simulation


9 Toolvergleich (Bachelorarbeit; Ansprechpartner: Dr. Bause)
    • Vergleich OMNeT++ und AnyLogic hinsichtlich Laufzeit, Speicherplatz und ”Ergebnisqualität”.
    • einfache Vergleichsmodelle z.B. aus dem Bereich der Warteschlangennetze: tandem, tandem with blocking, central server-Modelle (mit und ohne memory constraints), producer/consumer-Modelle
    • Der Vergleich sollte auch die eventuelle Nutzung von GPUs berücksichtigen.

10 Ansätze zum Screening von Parametern in Simulationsstudien (Masterarbeit; Ansprechpartner: Prof. Dr. Buchholz)
      • Vorstellung von Ansätzen zum Faktorscreening aus der Literatur [8, 17,18].
      • Implementierung der Verfahren in C++ oder Java zur Nutzung in Kombination mit einem Simulationswerkzeug (z.B. OMNeT++, AnyLogic).
      • Empirische Bewertung der Verfahren anhand einiger Beispielmodelle.


Auswertung


11 Statische Verfahren (Bachelorarbeit; Ansprechpartner: Dr. Bause)
      • Vorgegebene endliche Datenmenge.
      • Effiziente Verfahren zur Ermittlung von typischen Kenngrößen (mean, median, moments, confidence interval for mean, curtosis, . . .) implementieren.
      • Evtl. Erweiterung auf Prozess-Kenngrößen (auto-correlation, joint moments).
      • Toolentwicklung; Unix-ASCII-basiert, ggf. unter Ausnutzung vorhandener GPUs.


12 Dynamische Verfahren (Bachelorarbeit; Ansprechpartner: Dr. Bause)
      • On the fly statistische Analyse eines Datenstromes ("streaming statistical analysis")
      • typische Kenngrößen wie unter Nr. 11 (Statische Verfahren).
      • Evtl. Erweiterung auf Prozess-Kenngrößen (auto-correlation, joint moments).
      • Toolentwicklung; Unix-ASCII-basiert, ggf. unter Ausnutzung vorhandener GPUs.

13 Bootstrapping Ansätze zur Bestimmung von Konfidenzbändern für Verteilungsfunktionen (Bachelorarbeit; Ansprechpartner: Prof. Dr. Buchholz)
      • Vorstellung des Bootstrapping-Ansatzes zzur Bestimmung von Konfidenzbändern von Verteilungsfunktionen (z.B. der Verweilzeit in einem System) [9, 10].
      • Implementierung der Verfahren im Kontext von OMNeT++.
      • Empirische Bewertung der Konfidenzbänder auf Basis einfacher Beispiele.


Tools


14 SLA-Tool :  Experimentserien (Bachelorarbeit; Ansprechpartner: Dr. Bause)
      • Unterstützung zur Durchführung von Experimentserien in das SLA-Tool integrieren.
      • Verwaltung von Ergebnissen integrieren.


15 SLA-Tool : Validierung/Vergleich mit Simulation (Bachelorarbeit; Ansprechpartner: Dr. Bause)
      • Validierung: Werden die Grenzen eingehalten?
      • Vergleich: Wie ”brauchbar” sind die Grenzen in der Praxis?
      • ”typische” kleinere Modelle verwenden, hierzu Literatursichtung.
       • Einschätzung der Abbildbarkeit bzw. approximativen Darstellung der Modelle in SLA.


16 Erstellung eines Editors für PH-Graphen (Bachelorarbeit; Ansprechpartner: Prof. Dr. Buchholz)
      • Beschreibung der Klasse der PH-Graphen aus [2].
      • Entwurf und prototypische Implementierung eines Editors zur Spezifikation von PH-Graphen.
      • Anbindung der numerischen Verfahren zur Bestimmung kürzester Wege im Graphen.
      • Definition eines adäquaten Ausgabeformats für PH-Graphen.


Parallelisierung


17 Parallelisierung iterativer Lösungsalgorithmen für Markov Ketten mit OpenMP (Masterarbeit; Ansprechpartner: Prof. Dr. Buchholz)
      • Untersuchung von Parallelisierungsstrategien für Vektor-Matrix-Multiplikationen und weitere Basisoperationen iterativer Lösungsmethoden.
      • Prototypische Implementierung der Verfahren im Kontext von USENUM auf Mehrkernprozessoren.
      • Vergleich sequentieller und paralleler Implementierung anhand ausgesuchter Beispielmodelle.


18 GPU-Implementierung von Operationen auf HTDs (Masterarbeit; Ansprechpartner: Prof. Dr. Buchholz)
      • Beschreibung der hierarchsichen Tucker Dekomposition und der zugehörigen Operationen [11].
      • Parallelisierung der C-Implementierung aus [5] mit Hilfe von CUDA.
      • Vergleich sequentieller und GPU-Implementierung.


Literatur

[1] J. Banks (eds.). Handbook of simulation. Principles, Methodology, Advances, Applications, and Practice. John Wiley & Sons, 1998.
[2] Peter Buchholz, Iryna Felko. PH-graphs for analyzing shortest path problems with correlated traveling times. Computers & OR 59: 51-65 (2015).
[3] F. Bause, J. Kriege. Correlated Random Number Generation for Simulation Experiments. 16. ASIM Fachtagung (ASIM 2015), Simulation in Produktion und Logistik, TU Dortmund,
          23. bis 25. September 2015, Markus Rabe & Uwe Clausen (eds.), Fraunhofer IRB Verlag, Stuttgart 2015, pp. 641–650, ISBN 978-3-8396-0936-1.
[4] F. Bause, P. Buchholz. SLA Tool. In Proc. of the 19th International GI/ITG Conference on Measurement, Modelling and Evaluation of Computing Systems,
         German R., Hielscher KS., Krieger U. (eds) Measurement, Modelling and Evaluation of Computing Systems. MMB 2018, LNCS 10740, Springer, Cham, 2018, pp. 302--306.
[5] Peter Buchholz, Tugrul Dayar, Jan Kriege, M. Can Orhan. On compact solution vectors in Kronecker-based Markovian analysis. Perform. Eval. 115: 132-149 (2017).
[6] P. Buchholz, D. Scheftelowitsch Computation of weighted sums of rewards for concurrent MDPs. Math. Meth. of OR 89(1): 1-42 (2019).
[7] G. Bolch, S. Greiner, H. de Meer, K. Trivedi. Queueing Networks and Markov Chains. 2nd eds., 2006.
[8] Russell C. H. Cheng. Searching for Important Factors: Sequential Bifurcation under Uncertainty. Winter Simulation Conference 1997: 275-280.
[9] Russell C. H. Cheng. Bootstrapping simultaneous confidence bands. Winter Simulation Conference 2005: 240-247.
[10] Russell Cheng. Bootstrap confidence bands and goodness-of-fit tests in simulation input/output modelling. Winter Simulation Conference 2015: 16-30.
[11] Daniel Kressner, Christine Tobler. Algorithm 941: htucker - A Matlab Toolbox for Tensors in Hierarchical Tucker Format. ACM Trans. Math. Softw. 40(3): 22:1-22:22 (2014).
[12] A. Law, W. Kelton. Simulation modeling and analysis. 5th ed., McGraw Hill, 2014.
[13] P. Buchholz, S. Vastag. An Introduction to SLA Calculus for the Analytical Validation of SLAs. http://ls4-www.cs.tu-dortmund.de/download/buchholz/sla.pdf
[14] Lauren N. Steimle, David L. Kaufman, Brian T. Denton. Multi-model Markov Decision Processes Under revision, available at http://www.optimization-online.org/DB HTML/2018/01/6434.html
[15] OMNeT++ Community Site. http//www.omnetpp.org/.
[16] S. Vastag. SLA Calculus. Dissertation, Technische Universität Dortmund, Fakultät für Informatik, Dortmund, 2014.
[17] Hong Wan, Bruce E. Ankenman, Barry L. Nelson. Controlled Sequential Bifurcation: A New Factor-Screening Method for Discrete-Event Simulation. Operations Research 54(4): 743-755 (2006).
[18] Reza Yaesoubi, Stephen D. Roberts, Robert W. Klein. A modification of Cheng’S method: An alternative Factor Screening method for stochastic simulation models. Winter Simulation Conference 2010: 1034-1047.