Avoiding of Redundant Computations in Simulation Parameter Studies by Memoization
Final Report Abstract
Für die Entwicklung und Optimierung von Kommunikationssystemen sind Simulationen unverzichtbar. Im Rahmen von Parameterstudien wird ein Modell des betrachteten Systems vielfältig in unterschiedlichen Konfigurationen simuliert, um frühzeitig Aussagen über das Verhalten des untersuchten Systems zu erlangen. Die Laufzeit steigt mit der Komplexität des Modells und der Größe des zu simulierenden Netzwerks im Allgemeinen stärker als linear und wird deshalb oft zum kritischen Flaschenhals für Forschung und Entwicklung. Bislang wurde die Simulationszeit primär durch mehr Rechenleistung (zusätzliche Prozessorkerne und verteilte parallele Simulation) reduziert. Das theoretische Optimum wird hierbei bereits in vielen Fällen nahezu erreicht. Um trotzdem bei stetig steigender Modellkomplexität weitere Verbesserungen vornehmen zu können, müssen grundlegend neue Ansätze zur Reduktion der Simulationslaufzeit gefunden werden. Bereits in Vorstudien dieses Projekts sowie aufgrund langjähriger Erfahrung mit der Simulation von Netzwerken konnten wir beobachten, dass in Parameterstudien oft viele komplexe Berechnungen wiederholt durchgeführt werden, was eigentlich überflüssig ist. Diese wurden bislang leider nicht automatisch erkannt. Hieraus leitet sich die Forschungsfrage dieses Vorhabens ab: Können redundante Berechnungen in Parameterstudien automatisch erkannt und vermieden werden? Falls ja, bis zu welchem Grad? Diese Laufzeitreduktion soll orthogonal bzw. ergänzend zur Parallelisierung erfolgen und bietet ein großes Optimierungspotential, um bei gleicher Rechenleistung noch komplexere und genauere Simulationsmodelle untersuchen zu können. Unser Ansatz zur Vermeidung redundanter Berechnungen basiert auf dem Konzept der Memoisierung (englisch: Memoization). Hierbei werden Ergebnisse einer Berechnung in einem Ergebnis-Cache zwischengespeichert und bei späterem Bedarf direkt verwendet. Dies kann manuell erfolgen, muss dann aber für jedes Simulationsmodell individuell umgesetzt werden; das ist mit hohem Aufwand für die Entwickler verbunden. Ziel dieses Vorhabens war daher die Untersuchung von Konzepten zur automatisierten Memoisierung. Im Rahmen des Projekts gelang es uns, zu demonstrieren, dass selbst die größeren Herausforderungen, die Eingabeprogramme zu bieten haben können (insbesondere die nahezu beliebige Benutzung von Zeigern zur Adressierung von Ein- und Ausgaben der zu memoisierenden Berechnung), im Grundsatz adressierbar sind. Limitierungen ergeben sich jedoch vor allem dann, wenn während der Memoisierung unentscheidbare Probleme (z. B. durch Aliasing) entschieden werden mussten. Es ist unserem Ansatz hierbei allerdings möglich, das Auftreten einer derartigen Limitierung zu erkennen und die Memoisierung abzubrechen und nur im sicheren Fall durchzuführen. Des weiteren gelang es uns, mittels Abschätzungen von Programmlaufzeiten auf Basis einer Parameterstudie die vielversprechendste Berechnung für die Memoisierung zu identifizieren. Somit lässt sich ein vollautomatisches Werkzeug konstruieren, dass die Memoisierungsblöcke erkennt und optimiert. Auch eine Kombination mit Parallelisierung ist möglich, so dass es uns gelang die Simulationen einer beispielhaften Parameterstudie auf einem 12-Kern-System und den Faktor 600 zu beschleunigen.
Publications
- Automated Memoization for Parameter Studies Implemented in Impure Languages 1, 2 . In Proc. of the 4th ACM SIGSIM Conference on Principles of Advanced and Discrete Simulation (SIGSIM PADS), 2016, S. 221–232
M. Stoffers, D. Schemmel, O. Soria Dustmann und K. Wehrle
(See online at https://doi.org/10.1145/2901378.2901386) - Automated Memoization: Automatically Identifying Memoization Units in Simulation Parameter Studies. In Proceedings of the 21st IEEE/ACM International Symposium on Distributed Simulation and Real Time Applications (DS-RT), 2017, S. 33–42
M. Stoffers, R. Bettermann und K. Wehrle
(See online at https://doi.org/10.1109/DISTRA.2017.8167664) - Code-transparent Discrete Event Simulation for Time-accurate Wireless Prototyping. In Proc. of the 5th ACM SIGSIM Conference on Principles of Advanced and Discrete Simulation (SIGSIM PADS), 2017
M. Serror, J. C. Kirchhof, M. Stoffers, K. Wehrle und J. Gross
(See online at https://doi.org/10.1145/3064911.3064913) - On Automated Memoization in the Field of Simulation Parameter Studies. ACM Transactions on Modeling and Computer Simulation (TOMACS) 28(4), 2018, S. 26:1–26:25
M. Stoffers, D. Schemmel, O. Soria Dustmann und K. Wehrle
(See online at https://doi.org/10.1145/3186316) - Automated Optimization of Discrete Event Simulations without Knowing the Model. Reports on Communications and Distributed Systems. Shaker. 2019
M. Stoffers
