Automatisierte Leistungsanalyse von Simulationsalgorithmen zur inkrementellen Algorithmenselektion

• Applicant: Dr.-Ing. Roland Ewald
• Subject Area: Software Engineering and Programming Languages
• Term: from 2012 to 2014
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 213221189

• Final Report Year: 2014

Final Report Abstract

In diesem Projekt ging es darum, Informatiker bei der Entwicklung von neuen Simulationsmethoden zu unterstützen, sowie Anwender bei deren Nutzung. Simulationen betreffen viele wichtige Technologieund Wirtschaftsbereiche, beispielsweise die Flugraumüberwachung, die Logistikplanung, oder die biomedizinische Forschung. Ständig werden neue Simulationsmethoden entwickelt, welche die Berechnungen beschleunigen oder präzisieren sollen. Nutzer müssen daher oftmals die Methode auswählen (oder konfigurieren), mit der sie ein bestimmtes Simulationsproblem lösen wollen. Dies ist in vielen Fällen schwierig, und auch Experten fällt es nicht immer leicht herauszufinden, für welche Art von Problemen sich ein neuer Simulationsalgorithmus besser eignet als ein anderes Verfahren. Um diese Fragestellungen leichter zu beantworten wurde in diesem Projekt ein Softwaresystem entwickelt, dass in der Lage ist, automatische Experimente zur Leistungsanalyse solcher Algorithmen zu planen und durchzuführen. Diese Experimente sollen dabei helfen, neue Simulatoren zu analysieren und in der richtigen Situation auszuwählen. Neu war hierbei der Aspekt des inkrementellen Lernens, d.h. die Analyse soll dabei auf vorher gesammelten Daten aufbauen können. Erschwert wird die Analyse dadurch, dass komplexe Simulatoren häufig aus vielen verschiedenen Bausteinen bestehen und sich ihre Leistungsfähigkeit durch Anpassungen am Quelltext über die Zeit verändern kann. Um dieses Problem zu lösen haben wir beispielsweise einen Algorithmus, der eigentlich für die ’Benotung’ von Computerspielern in Multiplayer-Spielen konzipiert wurde, erfolgreich zur Analyse dieser Simulator-Bausteine eingesetzt. Dabei war überraschend für uns, wie gut sich diese Methode für die Bewertung von Softwarebausteinen im Allgemeinen einsetzen lässt; sie ist also nicht nur auf Simulationssoftware beschränkt. Damit unser Experimentiersystem von möglichst vielen Entwicklern verwendet werden kann, die ihre Nutzer bei der Auswahl von Simulatoren unterstützen wollen, haben wir unsere Software so aufgebaut dass sie mit verschiedensten Simulationssystemen zusammenarbeiten kann. Dazu war es nötig, eine Beschreibungssprache für Simulationsexperimente zu entwickeln, die wir SESSL genannt haben. In Analogie zum Möbelstück sind Simulationsexperimente mit SESSL besonders bequem und einfach zu definieren. SESSL hat in den letzten zwei Jahren jedoch ein Eigenleben entwickelt und ist nicht mehr nur für die Entwickler von Simulationssoftware interessant. Auch Studenten und Wissenschaftler aus anderen Fachrichtungen sind bereits auf SESSL aufmerksam geworden und nutzen es, um ihre Simulationsexperimente damit aufzusetzen. Unser Gesamtkonzept konnten wir mit einem lauffähigen Prototypen untermauern, aber es bleiben immer noch viele Fragen offen. Besonders wichtig scheint es zu sein, die vielen verschiedenen Methoden, die in der Informatik zur (empirischen) Analyse von Algorithmen eingesetzt werden, so zu beschreiben dass diese auch automatisch miteinander kombinierbar sind. Dies ist eine große Herausforderung, könnte aber in Zukunft zu ’intelligenten’ Simulationssystemen führen, die selbstständig die passendste Methode für jedes Simulationsproblem auswählen, oder, falls diese unbekannt ist, selbständig und proaktiv entsprechende Leistungsanalysen durchführen.

Publications

• Evaluating Simulation Software Components with Player Rating Systems. In: Proceedings of the 6th International ICST Conference on Simulation Tools and Techniques (SIMUTools), ICST, 2013. – Best Paper Award
  Wienß, Jonathan ; Stein, Michael ; Ewald, Roland
  
• Composing Problem Solvers for Simulation Experimentation: A Case Study on Steady State Estimation. In: PLoS ONE (2014), 9(4): e91948
  Leye, Stefan ; Ewald, Roland ; Uhrmacher, Adelinde M.
  
• SESSL: A Domain-Specific Language for Simulation Experiments. In: ACM Transactions on Modeling and Computer Simulation 24 (2014), Februar, Nr. 2
  Ewald, Roland ; Uhrmacher, Adelinde M.
  
• Using AI Planning to Automate the Performance Analysis of Simulators. In: Proceedings of the 7th International ICST Conference on Simulation Tools and Techniques (SIMUTools), 2014
  Ewald, Roland