- author = "Oliver Krauss",
- title = "Pattern Mining and Genetic Improvement in Compilers and Interpreters",
- school = "Computer Science, Johannes Kepler University",
- year = "2022",
- address = "Linz, Austria",
- month = mar,
- keywords = "genetic algorithms, genetic programming, Genetic Improvement, SBSE",
-
URL = "
https://ssw.jku.at/Teaching/PhDTheses/Krauss/index.html",
-
URL = "
https://ssw.jku.at/Teaching/PhDTheses/Krauss/Dissertation%20Krauss.pdf",
- size = "239 pages",
- abstract = "Writing source code is a challenging task, requiring the understanding of complex concepts, algorithms and programming paradigms. This task becomes increasingly challenging when source code has to be optimized for non-functional properties such as run-time performance, memory usage or energy efficiency. These properties often depend on in-depth knowledge of the language, the compiler and even the hardware architecture the source code will be run on. This thesis deals with the identification and verification of patterns in software that influence such non-functional properties. The goal is to help get an understanding, which patterns should be considered or avoided when optimizing towards a certain feature, and where to apply these patterns in the software. This is achieved by the novel combination of two distinct fields of research. Software Pattern Mining and Genetic Improvement, a Search-Based Software Engineering technique. The approach is applied directly at the compiler and interpreter level. This enables mining of a fine-granular software representation, combining it with in-depth information about the language, and gathering fine-granular performance measurements. A novel algorithm Knowledge-guided Genetic Improvement is presented that allows the generation of multiple semantically equivalent versions of software. These are then mined for discriminative patterns via the novel Independent Growth of Ordered Relationships algorithm. Several bug patterns, often occurring in the mutation operation of Genetic Improvement (GI), have successfully been identified and proven to produce bugs with an average confidence of 90.1percent. Fix patterns reduce these bugs with a confidence of 94percent. Identified patterns have been successfully applied in the field of Genetic Improvement by doubling population diversity, and reducing failing individuals in the population to 36.9percent compared to 80percent identified in related work. This allows Knowledge-guided Genetic Improvement to improve the run-time performance of 22 out of 25 algorithms by an average of 33.5percent. The work also successfully identifies anti-patterns and patterns in the run-time domain that are responsible for this improvement. This thesis lays a foundation for identifying and verifying patterns in the non-functional domain. As a side effect, it also makes the results of experiments in the domain of Genetic Improvement explainable. This opens up opportunities to drive research in the domains Software Pattern Mining and Genetic Improvement even further. In the future, identified patterns may even be directly applicable in a compiler or interpreter.",
- kurzfassung = "Das Entwickeln von Software ist eine anspruchsvolle Aufgabe, die ein Verstaendnis von komplexen Konzepten, Algorithmen und Programmierparadigmen erfordert. Diese Aufgabe wird noch schwieriger, wenn Software fuer bestimmte nicht-funktionale Anforderungen, wie Laufzeit, Speichernutzung oder Energieeffizienz optimiert werden soll. Dieses Verhalten ist oft von der Sprache, dem Compiler und auch der Hardwarearchitektur abhaengig, auf der die Software ausgefuehrt wird und erfordert fundierte Kenntnisse ueber diese. Diese Arbeit beschaeftigt sich mit der Identifikation und Verifikation von Patterns in Software, die solche nicht-funktionale Anforderungen beeinflussen. Das Ziel ist es, verstaendlich zu machen, welche Patterns, an welcher Stelle in der Software, bei der Optimierung einer bestimmten nicht-funktionalen Anforderungen angewendet oder vermieden werden sollen. Dies wird durch die neuartige Kombination zweier Forschungsfelder erreicht. Software Pattern Mining und Genetic Improvement, eine Methode der Suchbasierten Softwareentwicklung. Diese Methodik wird direkt im Compiler und Interpreter angewendet. Dadurch wird die Suche fein-granularen Repraesentationsformen von Software ermoeglicht und mit detaillierten Informationen ueber die Sprache sowie fein-granularer Laufzeitmessungen ermoeglicht. Ein neuartiger Algorithmus Knowledge-guided Genetic Improvement wird vorgestellt, der die Generierung mehrerer semantisch aequivalenter Versionen von Algorithmen ermoeglicht. Diese werden mit dem Independent Growth of Ordered Relationships Algorithmus nach diskriminativen Patterns durchsucht. Identifizierte Bug-Patterns, die oft im Mutations-Operator von Genetic Improvement entstehen, werden mit einer durchschnittlichen Sicherheit von 90.1percent bestaetigt. Patterns zur Praevention der Bugs werden mit 94percent Sicherheit bestaetigt. Diese Patterns wurden erfolgreich in der Domaene Genetic Improvement angewendet. Die Populationsdiversitaet wird verdoppelt, und Individuen, die Laufzeitfehler erzeugen, werden auf 36.9percent im Vergleich zu 80percent aus verwandten Arbeiten reduziert. Dies erlaubt Knowledge-guided Genetic Improvement die Laufzeit von 22 aus 25 getesteten Algorithmen im Durchschnitt um 33.5percent zu reduzieren. In Folge werden Anti-Patterns und Patterns identifiziert, die fuer diese Verbesserung verantwortlich sind. Diese Arbeit legt eine Grundlage fuer die Identifikation und Verifikation von Patterns fuer nichtfunktionale Anforderungen. Als Nebeneffekt koennen so die Ergebnisse von Genetic Improvement erklaerbar und nachvollziehbar gemacht werden. Dies eroeffnet Moeglichkeiten diese Forschung weiter zu vertiefen und voranzutreiben. In Zukunft koennen moeglicherweise sogar Muster identifiziert werden, die direkt im Compiler oder Interpreter anwendbar sind.",
-
notes = "In english
Supervisor Prof. Dr. Dr. h.c.Hanspeter Moessenbeock",
