Abstract:
In vielen Ingenieursdisziplinen werden Modelle verwendet, um Systeme verschiedenster Art auf einem hohen Abstraktionsgrad zu beschreiben. Auf diesem Abstraktionsgrad ist es häufig einfacher, Aussagen über den
Zustand des Systems zu treffen.
Wenn sich Modelle eines Systems ändern – beispielsweise, weil sich das System selbst geändert hat – müssen Analysen auf Grundlage dieses Modells jedoch neu berechnet werden, um weiterhin gültig zu sein. In vielen Fällen ist diese Neuberechnung der Analyseergebnisse zeitkritisch. Da sich oft nur kleine Teile des Modells ändern, könnten zwar große Teile des letzten Analysedurchlaufs durch eine inkrementelle Ausführung der Analyse wiederverwendet werden, in der Praxis ist eine solche Inkrementalisierung aber nicht trivial und oft fehleranfällig. ... mehr
Eine Lösungsmöglichkeit für dieses Problem bietet der Ansatz der impliziten Inkrementalisierung, bei der ein inkrementeller Algorithmus für eine gegebene Analyse aus der Batch-Spezifikation abgeleitet wird. Aus der Spezifikation wird ein dynamischer Abhängigkeitsgraph konstruiert, der es erlaubt, nur die Teile einer Analyse neu auszuwerten, die von einer Änderung tatsächlich betroffen sind. Damit lassen sich Vorteile einer Inkrementalisierung nutzen, ohne dass der Code angepasst werden muss und die Lesbarkeit des Analysecodes leidet.
Leider unterstützen derzeitige Verfahren für implizite Inkrementalisierung nur eine bestimmte Klasse von Analysen, sind auf eine Inkrementalisierung auf Ebene von einzelnen Instruktionen beschränkt oder benötigen eine explizite Zustandsverwaltung. Auch mit diesen Verbesserungen ist unklar, in welchen Fällen eine Inkrementalisierung Vorteile bringt, da in einigen Szenarien Änderungen Schmetterlingseffekte verursachen können und eine Wiederverwertung des letzten Analysedurchlaufs keinerlei Beschleunigungspotential hat.
Diese Dissertation behandelt diese Probleme bei impliziter Inkrementalisierung von Modellanalysen mittels mehrerer Verfahren, die größtenteils kombinierbar sind. Desweiteren wird ein neuer Formalismus vorgestellt,
mit dessen Hilfe Inkrementalisierungssysteme auch für uni- oder bidirektionale Modelltransformationen einsetzbar sind. Um die Korrektheit der entstehenden inkrementellen Modellanalysen zu definieren und zu zeigen,
wird Inkrementalisierung in Kategorientheorie als Funktor beschrieben.
Ein erstes Verfahren ermöglicht als direkte Konsequenz der formalen Darstellung die Inkrementalisierung auf Ebene von Methodenaufrufen, sodass für häufig verwendete Operatoren eine optimierte Inkrementalisierung zur Verfügung gestellt werden kann. Durch Erweiterung des Funktors auf Verteilung lassen sich auf ähnliche Weise auch etwaige Speicherprobleme lösen.
Ein zweites Verfahren vereinfacht die entstehenden dynamischen Abhängigkeitsgraphen, indem Teile der Analyse durch eine generalisierte Betrachtung von Modelländerungen mit mehreren Strategien zusammengefasst werden können. Die Auswahl der Strategien ermöglicht dem Entwickler eine Anpassung der Inkrementalisierung auf einen konkreten Anwendungsfall. Alternativ kann für ein gegebenes Szenario auch durch automatische Entwurfsraumexploration eine (Pareto-) optimale Konfiguration hinsichtlich Speicherverbrauch und Antwortzeit der Aktualisierung eines Analyseergebnisses nach einer Modelländerung gefunden werden.
Die Kombination dieser Verfahren ermöglicht es, die Performanz von Inkrementalisierungen so zu verbessern, dass diese bis auf einmalige Initialisierung nie schlechter ist als die batchmäßige Wiederholung der Analyse, in vielen Fällen aber teils deutlich schneller sein kann. Generische Operatoren, die in vielen Modellanalysen wiederverwendet werden, können für die Inkrementalisierung durch geeignete Algorithmen spezifisch optimiert werden, während komplexe Domänenlogik durch das System optimiert werden kann. Durch den impliziten Ansatz geschehen diese Verbesserungen
vollautomatisch und transparent für den Entwickler der Modellanalyse.
Obwohl der so geschaffene Ansatz Turing-mächtig und somit universell einsetzbar ist, gibt es doch gerade in der modellgetriebenen Entwicklung
eine Klasse von Artefakten, die eine besondere Betrachtung erfordern, da sie sich im Allgemeinen nur schwer mit gewöhnlichen objekt-orientierten Sprachen beschreiben lassen: Modelltransformationen. Daher wird in dieser Dissertation ein neuer Formalismus und eine darauf aufbauende Sprache vorgestellt, die Modelltransformationen so beschreiben, dass diese leicht mit Hilfe eines Inkrementalisierungssystems inkrementell ausgeführt werden
können. Die Synchronisierung einer Modelländerung ist hierbei bewiesen korrekt und hippokratisch.
Alle Verfahren wurden implementiert und in das .NET Modeling Framework integriert, welches Entwickler auf der .NET Plattform bei der modellgetriebenen Entwicklung unterstützen soll. Die entstandenen Vorteile aller Verfahren hinsichtlich Performanz werden anhand von sieben Fallstudien in verschiedenen Domänen validiert. Insbesondere werden hierzu fünf Fallstudien des Transformation Tool Contests (TTC) der Jahre 2015 bis 2017 herangezogen, für die auch mit anderen Ansätzen verfasste Lösungen zur Verfügung stehen. Die Ausdrucksmächtigkeit der Modelltransformationssprache wird durch eine Transformation der in der modellgetriebenen Entwicklung weit verbreiteten Transformationssprache ATL in die neu geschaffene Transformationssprache validiert. Mithilfe dieser Transformation
wird weiterhin die Ausführungsgeschwindigkeit von Modelltransformationen mit der von ATL in einigen Modelltransformationen verglichen.
Die Ergebnisse aus den Fallstudien zeigen gerade bei der Anwendung des Inkrementalisierungssystems auf Modelltransformationen deutliche Performance-Steigerungen im Vergleich zu herkömmlichen Modelltransformationen, aber auch gegenüber anderen inkrementellen Modelltransformationssprachen zeigt der vorgestellte Ansatz deutliche Beschleunigungen, teils um mehrere Größenordnungen. Insbesondere weisen die Fallstudien darauf hin, dass die benötigte Zeit für die Propagation von Änderungen des Eingabemodells in vielen Fällen unabhängig von der Größe des Eingabemodells ist. Gerade bei großen Eingabemodellen kommen so sehr hohe Beschleunigungen zustande.
Die Inkrementalisierung einer Analyse ist dabei immer an das Metamodell gebunden. In der Praxis verwenden aber die meisten eingesetzten Metamodelle nur den eingeschränkten Modellierungsstandard EMOF, der teilweise
zu einer unnötigen Komplexität des Metamodells führt und viele Analysen überhaupt erst notwendig macht. Eine Erweiterung des Modellierungsstandards kann hier einige Klassen von Modellanalysen komplett überflüssig
machen und andere Analysen deutlich vereinfachen, sowie auch die Performance der entsprechenden Analyse beschleunigen.
Abstract (englisch):
In many engineering disciplines, abstract models are used to describe systems on a high level of abstraction. On this abstract level, it is often easier to gain insights about that system that is being described.
When models of a system change – for example because the system itself has changed – any analyses based on these models have to be invalidated and thus have to be reevaluated again in order for the results to stay meaningful. In many cases, the time to get updated analysis results is critical. However, as most often only small parts of the model change, large parts of this reevaluation could be saved by using previous results but such an incremental execution is barely done in practice as it is non-trivial and error-prone.
... mehr
The approach of implicit incrementalization offers a solution by deriving an incremental evaluation strategy implicitly from a batch specification of the analysis. This works by deducing a dynamic dependency graph that allows to only reevaluate those parts of an analysis that are affected by a given model change. Thus advantages of an incremental execution can be gained without changes to the code that would potentially degrade its understandability.
However, current approaches to implicit incremental computation only support narrow classes of analysis, are restricted to an incremental derivation at instruction level or require an explicit state management. In addition, changes are only propagated sequentially, meanwhile modern multi-core architectures would allow parallel change propagation. Even with such improvements, it is unclear whether incremental execution in fact brings advantages as changes may easily cause butterfly effects, making a reuse of previous analysis results pointless (i.e. inefficient).
This thesis deals with the problems of implicit incremental model analyses by proposing multiple approaches that mostly can be combined. Further, the thesis suggests a new formalism how this incrementalization system can be used to empower incremental, uni- or bidirectional model transformations. To define and ensure the correctness of the resulting incremental evaluation strategy, the thesis presents a formalization of the incrementalization process using functors from category theory.
A first approach as a direct consequence of the formalization allows an incrementalization at the level of method calls such that often used methods can be annotated with an optimized incremental execution algorithm. By
extending the functor to distributed computing, memory problems can be resolved.
A second approach simplifies dynamic dependency graphs by generalizing model changes and thus summarizing parts of the analysis using several strategies. The selection of strategies gives the developer a chance to adjust the incrementalization process to a given scenario. Alternatively, an automated design space exploration can be performed to find a (Pareto-)optimal configuration with regard to memory consumption and response time of the analysis to a given model change.
The combination of these approaches improves the incrementalization process such that it never gets worse than batch execution but in many cases gains significant speedups. Generic operators to be reused in many
analyses can be optimized by choosing appropriate algorithms whereas complex domain logic can be optimized for incremental execution by the incrementalization system. The implicit nature of the overall approach allows these improvements to happen automatically and transparent to the developer of the analysis.
Although the presented approach is Turing-complete and therefore universally applicable, especially in the context of model-driven engineering a special class of artifacts deserves a special investigation as they are usually hard to describe with general-purpose languages: Model transformations. Therefore, we propose a new formalism and a language to describe uni- or bidirectional model transformations in a way that they can profit from the incrementalization system for analyses. For this formalism, we can proof a correct and hippocratic synchronization process.
All approaches have been implemented and integrated into the .NET Modeling Framework that supports developers in model-driven engineering. The advantages of all approaches regarding performance are validated using seven case studies. In particular, we use five case studies from the Transformation Tool Contest (TTC) from the years 2015 to 2017 for which also solutions using other tools are available. The expressiveness of the model transformation approach is validated by a higher-order transformation from the commonly used ATL transformation language into the language presented in this thesis. Using this transformation, also the performance of model transformations is compared to ATL for a number of model transformations.
The results of the case studies show that especially for the application of the proposed incrementalization systems to model transformation, significant speedups compared to classic model transformations, but also compared to existing incremental model transformation languages can be achieved, often by multiple orders of magnitude. In particular, the case studies suggest that time to propagate a change in the source model is often independent from the size of the input model. Especially for large input models, this causes large speedups.
The incrementalization of a model analysis is always bound to the metamodel. However, metamodels used in practice only use a subset of the commonly used modeling standard MOF. This sometimes causes a high accidental complexity of the metamodel and necessitates a range of analyses. An extension of the modeling language can help to make several model analyses obsolete an simplify others, thereby also improving the performance characteristics of these analyses.
