Abstract:
Durch den voranschreitenden Trend der Digitalisierung gewinnen intelligente digitale Systeme in vielen Bereichen des täglichen Lebens zunehmend an Bedeutung. Dies betrifft insbesondere auch den Bereich sicherheitskritischer Echtzeitsysteme, für deren sicheren Betrieb die Echtzeitfähigkeit nachgewiesen werden muss. Im Gegensatz zu Anwendungsfeldern ohne diese Anforderung sind effiziente Mehrkernprozessoren in Echtzeitsystemen derzeit noch kaum verbreitet. Der Hauptgrund für die bisherige Dominanz der Einzelkernprozessoren sind fehlende Methoden und Werkzeuge, um parallele Echtzeit-Software für Mehrkernprozessoren zu entwickeln und selbst im ungünstigsten Fall noch eine maximale Ausführungszeit (englisch Worst Case Execution Time, kurz WCET) garantieren zu können. ... mehrIn diesem Kontext besteht eines der wesentlichen Probleme darin, dass sich parallel ablaufende Software-Routinen im Hinblick auf ihre Laufzeit gegenseitig beeinflussen können. In Mehrkernprozessoren geschieht dies vor allem bei gleichzeitigen Zugriffen mehrerer Kerne auf eine gemeinsam genutzte Hardware-Ressource. Geeignete Methoden, um den Einfluss dieser als Interferenz bezeichneten Effekte bei der Software-Entwicklung präzise vorherzusagen und sichere Garantien für die Ausführungszeit abzuleiten, sind Gegenstand aktueller Forschung. Gleiches gilt für Software-Werkzeuge zur automatischen Parallelisierung, die auf harte Echtzeitanwendungen spezialisiert sind.
Diese Arbeit zielt darauf ab, die Anwendbarkeit von Mehrkernprozessoren in Echtzeitsystemen durch Beiträge in den Bereichen der automatischen Software-Parallelisierung, Code-Optimierung und Hardware-Modellierung signifikant zu verbessern. Als Bestandteil einer Werkzeugkette zur automatischen Parallelisierung von sequentieller Echtzeit-Software wird in dieser Arbeit ein Compiler-Werkzeug zur WCET-optimierten parallelen Code-Generierung und ein zugehöriges paralleles Programmiermodell vorgestellt. Hierdurch können -- weitgehend ohne Zutun eines Endanwenders -- gut vorhersagbare parallele Programme erzeugt werden. Durch das Programmiermodell wird dabei sichergestellt, dass die Ausführungszeit, einschließlich der Interferenzeffekte, mit Hilfe einer statischen WCET-Analyse sicher nach oben abgeschätzt werden kann. Als Teil der Code-Generierung stellt die vorliegende Arbeit zwei Optimierungsmethoden vor, die zum einen den Kommunikations- und Synchronisationsaufwand zwischen den Prozessorkernen reduzieren und zum anderen die optimierte Allokation verteilter Speicher in heterogenen Speicherhierarchien ermöglichen. Erstere ist auf des parallele Programmiermodell abgestimmt und erlaubt die optimierte Platzierung von Kommunikations- und Synchronisationsoperationen sowie das Entfernen redundanter Synchronisation auf einer feingranularen Ebene. Die Optimierung der Speicherallokation ergänzt den Ansatz um ein formales Optimierungsmodell zur Zuweisung der Datenfelder eines generierten Programms zu den Speicherbereichen der Zielplattform. Das Modell bezieht dabei sowohl die Kosten für Interferenzeffekte als auch die Speicherhierarchie von Zielplattformen mit verteilten und heterogenen Speichern mit ein. Um die Schritte zur Generierung, Optimierung und Analyse von paralleler Echtzeit-Software weitgehend plattformunabhängig aufbauen zu können, beinhaltet die vorliegende Arbeit außerdem einen Ansatz zur generischen Modellierung von Mehrkernprozessorarchitekturen. Dieser erlaubt es, die Zielplattform mit Hilfe einer entsprechend erweiterten Architekturbeschreibungssprache (ADL) zu beschreiben, wodurch sich die darauf aufbauenden Entwicklungswerkzeuge mit überschaubarem Aufwand auf ein breites Spektrum von Hardware-Plattformen anwenden lassen.
Mit dieser neuartigen Kombination erweitert die vorliegende Arbeit den Stand der Technik um einige wesentliche Bausteine, die die weitgehend automatisierte Parallelisierung von Echtzeit-Software ohne stark einschränkende Annahmen bezüglich der Struktur des Eingabeprogramms ermöglichen. Zu den weiteren Neuerungen dieser Arbeit zählen die Plattformunabhängigkeit bei der WCET-optimierten Software-Parallelisierung und die Berücksichtigung von Interferenzeffekten bei der Speicherallokation in Echtzeitsystemen.
Die experimentelle Evaluation der vorgestellten Methoden und deren prototypischer Umsetzung zeigt, dass die WCET aller betrachteten Testanwendungen von der Parallelisierung profitieren kann. Auf einer Plattform mit vier Prozessorkernen konnte z.B. die WCET einer Anwendung aus dem Bereich der Bildverarbeitung durch die Parallelisierung im Vergleich zum sequentiellen Eingabeprogramm um Faktor 3,21 verbessert werden. Auch die Optimierungsansätze für Kommunikation und Speicherallokation führen größtenteils zu einer deutlichen Verbesserung der WCET. So konnten die durch Interferenzen verursachten Kosten im Zuge der Speicherallokation z.B. um bis zu 49% reduziert werden.
Insgesamt haben die Ergebnisse dieser Arbeit damit das Potential, die effiziente und kostengünstige Nutzung von Mehrkernprozessoren im Bereich harter Echtzeitsysteme wesentlich voranzutreiben.
Abstract (englisch):
Driven by the ongoing trend of digitalization, intelligent digital systems become increasingly important in various areas of daily life. That includes the field of safety-critical real-time systems, which must satisfy real-time constraints to ensure their safe operation. In contrast to application domains without these requirements, efficient multi-core processors are still uncommon in state-of-the-art real-time systems. The main reasons for the dominance of single-core processors are missing methods and tools to develop and analyze parallel real-time software for multi-core processors. ... mehrIn particular, specialized analysis tools are needed to provide guarantees for the Worst-Case Execution Time (WCET) of parallel software. The major problem in that context is that parallelly executed software routines may affect each other's execution times. In multi-core processors, this happens, e.g., when multiple processor cores concurrently access the same shared hardware resource. Suitable methods to precisely predict the impact of these so-called interference effects during design time and derive guarantees for the execution time are subject to ongoing research. That is equally true for software-tools to automatically parallelize programs, which are subject to hard real-time constraints.
The goal of this work is to significantly improve the applicability of multi-core processors in real-time systems by contributing to the state-of-the-art in automated software parallelization, code optimization, and hardware modeling. As part of a tool-chain to automatically parallelize sequential real-time software, this work introduces a compiler tool for WCET-aware parallel code generation and a corresponding parallel programming model. Based on this combination, well-predictable parallel programs can be generated, mostly without requiring end-user interventions. In the process, the programming model ensures that software execution times, including interference effects, can be tightly bounded using a static WCET analysis. As part of the code generation, this work presents two optimization methods that, on the one hand, reduce communication and synchronization overhead and, on the other hand, optimize the allocation of memories within heterogeneous memory hierarchies. The former is adjusted to the programming model and allows for the optimized placement of communication and synchronization operations with a fine granularity. Moreover, redundant synchronization can be detected and removed in the process. The memory allocation scheme supplements the approach with a formal optimization model for mapping the data fields of the application onto the memory segments of the target platform. This model explicitly accounts for the costs of interference effects as well as the memory hierarchy of multi-core processors with distributed and heterogeneous memories. To keep the steps of generating, optimizing, and analyzing the code independent of the target platform, this work includes a generic model for multi-core processor architectures. The latter describes the target platform with an architecture description language (ADL) and allows the corresponding development tools to be applied to a wide range of target platforms without much effort.
With this novel combination, the present work extends the state-of-the-art by several essential building blocks that enable a mostly automated parallelization of real-time software without strong assumptions regarding the structure of the input program. Further novelties of this work are the platform-independence in WCET-aware code parallelization and the inclusion of interference while allocating memories for real-time systems.
The experimental evaluation of the presented methods and their implementation shows that the WCET of all considered test applications can benefit from parallelization. For a platform with four cores, the parallelization method, e.g., improved the WCET of an application from the image-processing domain by factor 3.21 compared to the sequential input program. The two optimization methods for communication and memory allocation result in significant improvements of the WCET in the vast majority of cases as well. The memory allocation, for instance, reduced the costs caused by interference by up to 49%.
Overall, the results of this work have the potential to significantly facilitate the efficient and cost-effective use of multi-core processors in the domain of hard real-time systems.
