Multigranulare Optimierung für heterogene Multicore-Systeme

In dieser Arbeit wird ein Verfahren vorgestellt, wie optimierter C-Code für eingebettete Mehrkernsysteme mit Hilfe einer ebenenübergreifenden Parallelisierung hinweg generiert werden kann. Ziel dabei ist es, die Algorithmenentwicklung von der Optimierung für das tatsächliche Zielsystem zu entkoppeln.

Zunächst werden die vier betrachteten Hierarchieebenen eingeführt und näher auf ihre Interaktionen eingegangen. Die Algorithmus-Ebene befasst sich mit der reinen Implementierung der Funktionalität und wie bekannte Eigenschaften von Algorithmen bereits frühzeitig ausgenutzt werden können. ... mehrAuf der Code-Ebene wird die Darstellung des Algorithmus im Quellcode optimiert. Dazu kommen Code-Transformationen und andere Methoden zum Einsatz, um den Code anschließend besser analysieren und aufteilen zu können. Die Task-Ebene befasst sich mit der Verteilung der einzelnen Tasks auf die verfügbaren Ausführungseinheiten und die Daten-Ebene stellt schließlich die korrekte Synchronisation der Daten zwischen allen Kernen sicher.

Das Verfahren setzt auf die Entwicklung in der Sprache MATLAB und die Erzeugung von C-Code für eingebettete Systeme. Im Anschluss wird näher auf diese Codegenerierung eingegangen, die notwendig ist, um die in MATLAB vorliegenden Algorithmen in statisch analysierbaren C-Code zu konvertieren und nach den Optimierungsschritten den parallelen C-Code für die Zielplattform zu generieren. Fokus liegt auf der Herausforderung, wie aus einer Skriptsprache, bei der Datentypen und Variablengrößen dynamisch zur Laufzeit von einem Interpreter berechnet werden, effizienter C-Code generiert werden kann. Zusätzlich wird beschrieben, wie der korrekte Kontrollfluss einer Anwendung in einer parallelisierten Anwendung sichergestellt werden kann.

Im Folgenden wird die Realisierung der ebenenübergreifenden Parallelisierung genauer erläutert. Dazu wird zunächst die Spezifikation der Zielsysteme über eine Architekturbeschreibung eingeführt, um anschließend die wichtigsten Implementierungen je Ebene vorzustellen. Auf der Algorithmus-Ebene ist dies die Erkennung von bekannten Algorithmen und wie bekannte Eigenschaften ausgenutzt werden können. Die Parallelisierung auf Code-Ebene setzt den Fokus auf Code-Transformationen, die die intrinsische Parallelität der Anwendungen nutzbar machen. Auf der Task-Ebene wird auf die Verteilung von Tasks auf die verfügbaren Ausführungseinheiten eingegangen und welche Algorithmen für das Scheduling zum Einsatz kommen. Die Daten-Ebene befasst sich schließlich mit der Platzierung von Synchronisations- und Kommunikationsinstruktionen, um die korrekte und effiziente Ausführung der parallelisierten Anwendung sicherzustellen.

Schließlich wird das Verfahren mit drei Beispielanwendungen, zwei datenflusslastigen und einer kontrollflusslastigen Anwendung, evaluiert. Dazu werden die angewendeten Optimierungen auf den einzelnen Ebenen beschrieben, wie sie iterativ angewendet werden und wie sich die Ebenen gegenseitig beeinflussen. Messungen auf verschiedenen Hardware-Plattformen runden die Ergebnisse ab.

Abschließend wird eine Zusammenfassung gegeben und mögliche zukünftige Erweiterungen beschrieben.

This thesis presents an approach to generate optimized C code for embedded systems using an iterative multigranular approach across different levels of abstraction. The goal here is to decouple the algorithm development from the optimization for the actual target system.

First, the four hierarchical levels considered are introduced and their interaction is discussed in more detail. The algorithm level deals with the pure implementation of functionality and how known properties of algorithms can be exploited early on. At the code level, the representation of the algorithm in the source code is optimized. ... mehrCode transformations and other methods are used for this purpose, in order to be able to analyze and split the application better afterwards. Finally, the task level deals with the distribution of the individual tasks to the available execution units and the data level ensures the correct synchronization of the data between all cores.

Next, the code generation steps necessary to convert the algorithms initially available in MATLAB into statically analyzable C code and to generate the parallel C code for the target platforms after the optimization steps are discussed and solutions are presented. The challenges of generating efficient C code from a scripting language where data types and variable sizes are computed dynamically at runtime by an interpreter are discussed in more detail. In addition, it is discussed how the correct control flow of an application can be ensured in a parallelized application.

In the following, the realization of cross-level parallelization is described. For this purpose, the specification of the target systems is introduced via an architecture description, and then the most important implementations per level are presented. At the algorithm level, this is the detection of known algorithms and how known properties can be exploited. Parallelization at the code level focuses on code transformations that harness the intrinsic parallelism of applications. The task level deals with the distribution of tasks to the available execution units and which algorithms are used for scheduling. Finally, the data level deals with the placement of synchronization and communication instructions to ensure the correct and efficient execution of the parallelized application.

This approach is finally evaluated with three example applications, two data-flow-heavy and one control-flow-heavy. This is done by describing the optimizations applied at each level, how they are applied iteratively, and how the levels affect each other. Measurements on different hardware platforms complete the results.

Finally, a summary is given and possible future extensions are described.