System-Level Mapping, Analysis, and Management of Real-Time Applications in Many-Core Systems

Language
en
Document Type
Doctoral Thesis
Issue Date
2021-12-20
Issue Year
2021
Authors
Pourmohseni, Behnaz
Editor
Abstract

Heterogeneous many-core platforms are becoming the de facto standard architectures for embedded systems, fulfilling their high demand for computational power consequent to the rapid increase in the number and the workload of the applications in such systems. Contrarily to historically being statically one-time programmed and the mix of running applications being fixed, modern embedded systems are often subject to a highly dynamic environment in which the mix of concurrently executed applications, the availability of resources, and the non-functional requirements of each application may change at run time on-demand. This necessitates adaptive application mapping and system management schemes to effectively cope with the system dynamism. In recent years, applications with hard real-time requirements are being increasingly observed in emerging embedded systems in various time-critical areas, e.g., automotive, telecommunications, and avionics. In this context, novel design methodologies are required to enable an adaptive mapping and management of hard real-time applications on many-core platforms with verified worst-case timing guarantees.

Recently, so-called Hybrid Application Mapping (HAM) methodologies have been proposed that split the design process into an offline application mapping phase and an online system management phase and, thereby, can enable a dynamic mapping and management of hard real-time applications on many-core platforms. In HAM, for each application, a set of high-quality mapping alternatives with diverse resource requirements and verified timing guarantees are computed offline in a Design Space Exploration (DSE). These mappings are then used online by a Run-time Platform Manager (RPM) to launch the application on-demand by selecting a precomputed mapping that adheres to the current timing constraints of the application and the resource availability in the system. In line with this hybrid scheme, the work at hand proposes a collection of methodologies, analyses, and techniques that enable an automated mapping and adaptive management of hard real-time applications on heterogeneous many-core platforms with verified timing guarantees.

Foremost, a formal timing analysis technique is proposed which can derive worst-case timing guarantees for hard real-time applications in (heterogeneous) many-core systems. In light of this analysis, a novel mapping optimization approach is proposed in which the amount of resources allocated per mapping is fine-tuned according to the timing requirements of the application to obtain high-quality mappings with satisfactory timing guarantees and enhanced resource efficiency.

In many-core systems, hard real-time applications are particularly susceptible to built-in autonomous Dynamic Thermal Management (DTM) mechanisms which are responsible for preserving the thermal safety of the system. At the sight of thermal violations (overheating), DTM mechanisms suspend or decelerate the execution of the applications that are running in the thermally affected regions which may lead to the violation of their real-time constraints. To eliminate such fatal interferences, this work proposes a thermally composable HAM methodology that preserves the thermal safety of the system proactively at all times and, thereby, eliminates the exposure of real-time applications to DTM without jeopardizing the thermal integrity of the system.

The offline DSE in HAM typically delivers a large set of Pareto-optimal mappings which imposes a considerable management overhead on the RPM and may degrade its responsiveness. This can be particularly fatal for hard real-time applications due to their strict dependence on prompt reactions from the RPM, e.g., upon a change in their timing constraints. As a remedy, this work proposes an automatic mapping-set distillation methodology that distills a promising subset of the mappings for online use to alleviate the RPM’s overhead while retaining a diverse blend of quality- and resource-demand trade-offs to address various run-time scenarios.

For a seamless satisfaction of the timing constraints of hard real-time applications in many-core systems, on-the-fly adaptation of their mappings becomes inevitable in view of drastic changes in their timing constraints or the failure of resources they use, e.g., due to faults or overheating. To that end, this work proposes two mapping adaptation methodologies for hard real-time applications in many-core systems. In the first approach, adaptations are realized in the form of a reconfiguration between precomputed mappings, while the second approach empowers fine-grained mapping adaptations in the form of the migration of any subset of the application’s tasks to any desired locations. Both methodologies are supplied with formal timing analysis techniques and lightweight admission checks to verify the real-time conformity of each adaptation option online according to the current timing constraints of the application.

Abstract

Eingebettete Systeme in verschiedenen Bereichen, z. B. Automobil, Telekommunikation und Industrieautomatisierung, beinhalten zunehmend Anwendungen mit harten Echtzeitanforderungen. Bei Anwendungen dieser Art ist die Einhaltung der applikationsspezifischen zeitlichen Beschränkungen von entscheidender Bedeutung, da eine Verletzung dieser zum Systemausfall oder im schlimmsten Fall sogar zur Gefährdung von Menschen führen kann. In den letzten Jahren ist eine rasche Zunahme der Anzahl und der Dynamik von Anwendungen in eingebetteten Systemen zu beobachten. Der daraus resultierende massive Bedarf an Rechenleistung wird voraussichtlich dazu führen, dass (heterogene) Vielkernarchitekturen in naher Zukunft zu der De-Facto-Standard-Zielplattform in diesem Bereich werden.

In diesem Zusammenhang sind neuartige Entwurfsmethoden erforderlich, die eine adaptive Abbildung und Verwaltung von Anwendungen auf Vielkernplattformen ermöglichen, um eine hohe Auslastung der zugrundeliegenden Rechenressourcen zu erreichen und gleichzeitig die individuellen Anforderungen der Anwendungen zu erfüllen. Die Einhaltung dieser Anforderungen, die sowohl funktionale (z. B. Echtzeit) als auch nichtfunktionale Anforderungen beinhalten, muss über die gesamte Lebensdauer der Anwendung hinweg garantiert werden. Dies stellt besonders im Hinblick auf die sich stetig und unvorhersehbar ändernden Ausführungsbedingungen (z. B. Art und Anzahl der ausgeführten Anwendungen, die Menge der Arbeitslast oder die Verfügbarkeit der Systemressourcen) eine signifikante Herausforderung dar. Zu diesem Zweck schlägt diese Arbeit eine Reihe von Methoden, Analysen und Techniken vor, die sich mit den wichtigsten Entwurfsherausforderungen harter Echtzeitsysteme für heterogene Vielkernplattformen befassen. Zusammen ermöglichen die Beiträge dieser Arbeit eine automatisierte Abbildung und adaptive Verwaltung von Anwendungen mit harten Echtzeitanforderungen auf Vielkernplattformen mit verifizierten Laufzeitgarantien entsprechend ihrer Echtzeitanforderungen. Im Folgenden werden die wichtigsten Beiträge dieser Arbeit zusammengefasst.

Angesichts des hohen Rechenaufwands von Zeitanalyseverfahren beruht die adaptive Abbildung und Verwaltung von harten Echtzeitanwendungen auf Vielkernplattformen notwendigerweise auf einem hybriden Anwendungsabbildungsschema (englisch: Hybrid Application Mapping (HAM)). Die HAM-Methodik besteht aus einer Phase zur Charakterisierung der Anwendungen zur Entwurfszeit. Dieser folgt ein dynamisches Laufzeitmanagemant während ihrer Ausführung, die dabei die zur Entwurfszeit gewonnen Charakteristika ausnutzt. Zur Entwurfszeit wird die Optimierung, Analyse und Bewertung der Abbildungsmöglichkeiten jeder Anwendung auf die Zielplattform in einer automatischen Entwurfsraumexploration (englisch: Design Space Exploration (DSE)) durchgeführt, um eine Menge Pareto-optimaler Abbildungsalternativen mit verifizierten Zeitgarantien und unterschiedlichen Ressourcenanforderungen zu berechnen. Zur Laufzeit werden die berechneten Abbildungsalternativen für jede Anwendung einem Laufzeit-Plattformmanager (englisch: Run-time Platform Manager (RPM)) zur Verfügung gestellt, um jede Anwendung bei Bedarf entsprechend einer vorberechneten Abbildung zu starten, die zu den Echtzeitanforderungen der Anwendung und der Verfügbarkeit von Ressourcen passt. Da die rechenintensive Optimierung und Auswertung der relavanten Charakteristiken der betrachteten Abbildungen bereits zur Entwurfzeit stattgefunden hat, ermöglicht HAM ein skalierbares Laufzeitmanagement adaptiver Echtzeitanwendungen mit geringem Rechenaufwand. Im Folgenden sind die Beiträge dieser Arbeit zusammengefasst.

Als ersten Beitrag schlägt diese Arbeit eine formale Zeitanalyse vor, die verschiedene Arten von zeitlichen Garantien für Echtzeitanwendungen in Mehrkernsystemen ableiten kann. Basierend auf dieser Analyse wird ein neuartiger Ansatz zur Optimierung der Abbildungen auf Vielkernplattformen vorgeschlagen, bei dem die Menge der pro Abbildung zugewiesenen Ressourcen entsprechend den Anforderungen der Anwendung bezüglich Zeit und Rechenleistung fein abgestimmt wird, um qualitativ hochwertige Abbildungen mit zufriedenstellenden Laufzeitgarantien und verbesserter Ressourceneffizienz zu erhalten.

In Mehrkernsystemen sind Anwendungen mit harten Echtzeitanforderungen besonders anfällig für die autonomen eingebauten Mechanismen des dynamischen Temperaturmanagements (englisch: Dynamic Thermal Management (DTM)), die für die Einhaltung der thermischen Sicherheit des Systems verantwortlich sind. Beim Auftreten von Überhitzung unterbrechen oder verlangsamen die DTM-Mechanismen die Ausführung der Anwendungen, die in den thermisch betroffenen Regionen laufen, was zur Verletzung ihrer Echtzeitanforderungen führen kann. Um solche fatalen Interferenzen zu eliminieren, schlägt diese Arbeit eine neuartige HAM-Methodik vor, die die thermische Sicherheit des Systems jederzeit proaktiv bewahrt und dadurch verhindert, dass Echtzeitanwendungen den DTM-Mechanismen ausgesetzt werden, ohne die thermische Integrität des Systems zu gefährden.

Die DSE in HAM-Methodiken liefert in der Regel eine riesige Menge an Paretooptimalen Abbildungsalternativen, die dem RPM einen erheblichen Managementaufwand aufbürden und seine Reaktionsfähigkeit verschlechtern. Dies kann insbesondere für Echtzeitanwendungen fatal sein, da sie—beispielsweise bei Ausfall einer der von ihnen genutzten Ressourcen—auf eine schnelle Reaktion des RPM angewiesen sind. Als Abhilfemaßnahme schlägt dies Arbeit eine automatische Destillationsmethode vor. Ihre Aufgabe ist es, eine Teilmenge der Pareto-optimalen Abbildungsalternativen zu bestimmen, die dann dem Laufzeitmanagement zur Verfügung stehen. Das Ziel dabei ist, den Overhead des RPM zu verringern, während gleichzeitig die beibehaltenen Abbildungsalternativen im Hinblick auf Qualität und Ressourcenbedarf sehr divers sind, um verschiedenen Laufzeitszenarien und -anforderungen gerecht zu werden.

Um zu garantieren, dass Echtzeitanforderungen auch bei unerwarteten Laufzeitereignissen, z. B. beim Ausfall von Ressourcen, erfüllt werden können, ist es notwendig, die Abbildungen von Echtzeitanwendungen zur Laufzeit dynamisch anpassen zu können. Zu diesem Zweck schlägt diese Arbeit zwei Methoden zur dynamischen Anpassung der Abbildung von Anwendungen mit harten Echtzeitanfoderungen in Vielkernsystemen vor. Im ersten Ansatz werden Anpassungen in Form einer Rekonfiguration zwischen vorberechneten Abbildungen realisiert, während der zweite Ansatz feingranulare Anpassungen der Abbildungen in Form der Migration einer beliebigen Teilmenge der Tasks der Anwendung zwischen beliebigen Kernen im System ermöglicht. Beide Methoden bieten formale Zeitanalysen und leichtgewichtige Zulassungsprüfungen, um die Echtzeit-Konformität jeder Anpassungsoption entsprechend den Zeitbeschränkungen der Anwendung zur Laufzeit zu überprüfen.

DOI
Faculties & Collections
Zugehörige ORCIDs