Please use this identifier to cite or link to this item: doi:10.22028/D291-29814
Title: Applicable and sound polyhedral optimization of low-level programs
Author(s): Doerfert, Johannes
Language: English
Year of Publication: 2018
DDC notations: 004 Computer science, internet
Publikation type: Doctoral Thesis
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.
Link to this record: urn:nbn:de:bsz:291--ds-298142
hdl:20.500.11880/28318
http://dx.doi.org/10.22028/D291-29814
Advisor: Hack, Sebastian
Date of oral examination: 19-Dec-2018
Date of registration: 18-Nov-2019
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
phd_doerfert.pdf2,24 MBAdobe PDFView/Open


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