Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-2255
Main Title: A Framework for Intelligent Speculative Compiler Optimizations and its Application to Memory Accesses
Translated Title: Ein Framework für intelligente spekulative Compileroptimierungen und seine Anwendung zur Optimierung von Speicherzugriffen
Author(s): Alvincz, Lars
Advisor(s): Glesner, Sabine
Granting Institution: Technische Universität Berlin, Fakultät IV - Elektrotechnik und Informatik
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: In dieser Arbeit stellen wir unser konzeptuelles Framework für intelligente spekulative Compileroptimierungen (FrISCO, Framework for Intelligent Speculative Compiler Optimizations) vor sowie die Anwendung des Frameworks, um Speicherzugriffe zu optimieren. Das Ziel des Frameworks ist es, Compilern Wissen über das Laufzeitverhalten von Programmen verfügbar zu machen, um die Kluft zwischen statischen Programmanalysen einerseits und dem dynamischen Programmverhalten anderseits zu überbrücken. Dadurch wird das Problem der Überapproximation gelöst, das den statischen Programmanalysen inhärent ist, und das Optimierungspotential vergrößert. Die grundlegende Idee unseres Frameworks besteht darin, im Compiler unsichere, aber dafür präzisere Programmanalysen zuzulassen und deren Ergebnisse in spekulativen Optimierungen zu verwenden, um ein präzises Kostenmodell zu erstellen. Dabei wird die Programmkorrektheit in allen Fällen gewahrt. Wir verwenden Heuristiken, um das dynamische Programmverhalten vorherzusagen. Wir stellen ein Verfahren vor, um solche Heuristiken automatisch in einer einmaligen Trainingsphase anhand von Profilingdaten mittels Maschinellen Lernens zu erzeugen. Außerdem schlagen wir vor, ähnliche Programme in Klassen zusammenzufassen. Dies kann automatisch durch eine Clusteranalyse erfolgen. Wir trainieren jeweils eine spezialisierte Heuristik pro Programmklasse sowie einen Programmklassenprediktor. Damit läßt sich das Verhalten beliebiger Programme präzise vorhersagen, indem die am besten geeignete Heuristik ausgewählt wird. Die resultierende kombinierte Heuristik ist hochgradig skalierbar und kann automatisch in ausführbaren, hoch skalierbaren Code überführt werden, der dann in den Compiler integriert werden kann. Wir stellen einen allgemeinen Optimierungsalgorithmus vor, auf den die meisten existierenden Optimierungen abgebildet werden können. Der Algorithmus transformiert das Programm schrittweise und verwendet dabei ein Kostenmodell um sicherzustellen, dass in jedem Schritt die beste Transformation ausgewählt wird. Das konzeptuelle Framework lässt sich auf eine breite Spanne von Programmverhalten und -optimierungen anwenden. Im zweiten Teil dieser Arbeit zeigen wir, wie wir das Framework anwenden, um Speicherzugriffe zu optimieren. Das ist ein sehr wichtiges Optimierungsproblem aufgrund des Memory Gaps. Für das angewandte Framework stellen wir eine neue Optimierung vor, die spekulative Code-Verschiebung durchführt, um die effektive Latenz von Ladebefehlen zu reduzieren. Dabei können sämtliche Arten von Abhängigkeiten überwunden werden. Das Kostenmodell basiert auf den Abhängigkeitswahrscheinlichkeiten für Speicherzugriffe sowie den Latenzen der Ladebefehle. Wir haben das angewandte Framework vollständig implementiert. Als Plattform verwenden wir den Intel Itanium2-Prozessor, der spekulative Optimierung hardwareseitig unterstützt. Mit unseren Experimenten konnten wir zeigen, dass die Heuristiken das Speicherverhalten von Programmen präzise vorhersagen können, insbesondere dank unseres Konzepts der Programmklassifikation. Weiterhin konnten wir mit Laufzeitexperimenten zeigen, dass unsere spekulative Optimierung mithilfe des Kostenmodells signifikante Laufzeitverbesserungen erreichte sowie in keinem Fall zu einer Verschlechterung führte.
In this thesis, we present a conceptual Framework for Intelligent Speculative Compiler Optimizations (FrISCO) and its application to the optimization of memory accesses. The framework aims at providing compilers with knowledge about the run-time behavior of programs to bridge the gap between static program analyses on the one hand and dynamic program behavior on the other. This solves the problem of over-approximation, which is inherent to static program analyses, and increases the optimization potential. We use machine learning to make the knowledge available to the compiler. The principal idea of our framework is to admit unsafe, yet more precise program analyses within the compiler and to use their results in speculative optimizations, which use the information to derive precise cost models and which guarantee program correctness in case of misspeculation. In our approach, we use heuristics to predict the dynamic program behavior. We present a method to generate such heuristics automatically in a one-off training phase from profiling data using machine learning. Additionally, we propose to perform program classification to group programs with similar behavior together, which can be done automatically via cluster analysis. Based on the clustering, we train one specialized heuristics for each class as well as a program class predictor. With that, we can precisely predict the behavior of arbitrary programs by selecting the most appropriate heuristics. The obtained overall heuristics is highly scalable and can be automatically translated to executable code to be integrated within compiler optimizations. We present a general optimization algorithm, onto which most existing optimizations can be mapped. The algorithm iteratively transforms the program. To ensure that the best transformation is found in each step, the algorithm uses a cost model that is evaluated with the help of the heuristics. The conceptual framework is applicable to a wide range of program behavior and program optimizations. In the second part of this thesis, we show the application of the framework to the optimization of memory accesses, which is a highly important optimization problem due to the memory gap. For the applied framework, we present a novel optimization algorithm that performs speculative code motion to reduce the effective latency of load instructions. During code motion, the algorithm overcomes memory dependencies, register dependencies, and control dependencies, and it maintains a precise cost model which captures the effect of each transformation on the latency of the optimized load. The cost model relies on information about the memory behavior of a program, namely the probability of memory dependencies and load latencies. We present how to build heuristics for that via machine learning. We fully implemented the instantiated framework. As target architecture, we chose the Intel Itanium2 processor, a modern VLIW processor with hardware support for speculation. In our experiments, we could first show that the heuristics predict the memory behavior precisely, especially due to our concept of program classification. Second, our run-time experiments demonstrate that our speculative optimization, with the help of the heuristics, significantly improves program performance and avoids performance degradation due to the cost model.
URI: urn:nbn:de:kobv:83-opus-23579
http://depositonce.tu-berlin.de/handle/11303/2552
http://dx.doi.org/10.14279/depositonce-2255
Exam Date: 17-Jul-2009
Issue Date: 30-Sep-2009
Date Available: 30-Sep-2009
DDC Class: 004 Datenverarbeitung; Informatik
Subject(s): Compiler
Compileroptimierung
Maschinelles Lernen
Speicherabhängigkeiten
Spekulative Optimierung
Compiler
Compiler Optimization
Machine Learning
Memory Dependencies
Speculative Optimization
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 4 Elektrotechnik und Informatik » Institut für Softwaretechnik und Theoretische Informatik » Publications

Files in This Item:
File Description SizeFormat 
Dokument_49.pdf1,71 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.