Applicable and sound polyhedral optimization of low-level programs

Abstract

Aktuelle und zukünftige Computersysteme zeichnen sich durch verschiedenartige Mehrkernprozessoren, sowie programmierbare und spezialisierte Hardwarebeschleuniger aus. Zudem wird die Speicherhierarchie tiefer und oft durch Speicher mit niedriger Latenz, oder hoher Bandbreite, erweitert. Der Programmierer kann dieses enorme Potential allein nicht nutzen. Übersetzer müssen Einblick in das Programmverhalten geben, oder sogar Berechnungen und Daten selbst verwalten. Für beides brauchen sie eine ganzheitliche Sicht auf das Programm, da auch lokale Transformationen, die die Ausführungsreihenfolge, die Recheneinheit und das Speicherlayout unverändert lassen, nicht ausreichen um vielfältige Systeme auszulasten. Das Polyedermodell, eine mathematische Programmdarstellung und ein Transformationsrahmenwerk, hat große Erfolge bei der Bewältigung verschiedener Probleme im Kontext vielfältiger Systeme erzielt. Obwohl die Analyse- und Transformationsfähigkeiten weithin anerkannt sind, wird auch allgemein angenommen, dass es zu restriktiv ist für Programme aus der Praxis. In dieser Arbeit verbessern wir die Anwendbarkeit und Rentabilität von Techniken basierend auf dem Polyedermodell. Unsere Bemühungen garantieren eine korrekte Programmdarstellung und führen neue Anwendungen ein um die verfügbaren Informationen in der polyedrischen Programmdarstellung zu nutzen. Diese sind eigenständige Optimierungen und Techniken zur Ableitung von abstrakten Programmeigenschaften.

Computers become increasingly complex. Current and future systems feature configurable hardware, multiple cores with different capabilities, as well as accelerators. In addition, the memory subsystem becomes diversified too. The cache hierarchy grows deeper, is augmented with scratchpads, low-latency memory, and high-bandwidth memory. The programmer alone cannot utilize this enormous potential. Compilers have to provide insight into the program behavior, or even arrange computations and data themselves. Either way, they need a more holistic view of the program. Local transformations, which treat the iteration order, computation unit, and data layout as fixed, will not be able to fully utilize a diverse system. The polyhedral model, a high-level program representation and transformation framework, has shown great success tackling various problems in the context of diverse systems. While it is widely acknowledged for its analytical powers and transformation capabilities, it is also widely assumed to be too restrictive and fragile for real-world programs. In this thesis we improve the applicability and profitability of polyhedral-model-based techniques. Our efforts guarantee a sound polyhedral representation and extend the applicability to a wider range of programs. In addition, we introduce new applications to utilize the information available in the polyhedral program representation, including standalone optimizations and techniques to derive high-level properties.