Moderne Computersysteme bieten Anwendern und Anwendungsentwicklern ein hohes Maß an Parallelität und Heterogenität. Die effiziente Nutzung dieser Systeme erfordert jedoch tiefgreifende Kenntnisse, z.B. der darunterliegenden Hardware-Plattform und den notwendigen Programmiermodellen, und umfangreiche Arbeit des Entwicklers. In dieser Thesis bezieht sich die effiziente Nutzung auf die Gesamtausführungszeit der Anwendungen, den Energieverbrauch des Systems, die maximale Temperatur der Verarbeitungseinheiten und die Zuverlässigkeit des Systems. Neben den verschiedenen Optimierungszielen muss ein Anwendungsentwickler auch die spezifischen Einschränkungen und Randbedingungen des Systems berücksichtigen, wie z. ... mehrB. Deadlines oder Sicherheitsgarantien, die mit bestimmten Anwendungsbereichen einhergehen. Diese Komplexität heterogener Systeme macht es unmöglich, alle potenziellen Systemzustände und Umwelteinflüsse, die zur Laufzeit auftreten können, vorherzusagen.
Die System- und Anwendungsentwickler sind somit nicht in der Lage, zur Entwurfszeit festzulegen, wie das System und die Anwendungen in allen möglichen Situationen reagieren sollen. Daher ist es notwendig, die Systeme zur Laufzeit der aktuellen Situation anzupassen, um ihr Verhalten entsprechend zu optimieren. In eingebetteten Systemen mit begrenzten Kühlkapazitäten muss z.B. bei Erreichen einer bestimmten Temperaturschwelle eine Lastverteilung vorgenommen, die Frequenz verringert oder Verarbeitungseinheiten abgeschaltet werden, um die Wärmeentwicklung zu reduzieren.
Normalerweise reicht es aber nicht aus, einfach nur auf einen ungünstigen Systemzustand zu reagieren. Das Ziel sollte darin bestehen, ungünstige oder fehlerhafte Systemzustände vor dem Auftreten zu vermeiden, um die Notwendigkeit des Aufrufs von Notfallfunktionen zu verringern und die Benutzerfreundlichkeit zu verbessern. Anstatt beispielsweise die Wärmeentwicklung durch eine Neuverteilung der Anwendungen zu reduzieren, könnten proaktive Mechanismen kritische Temperaturen bereits im Vorfeld vermeiden, indem sie bestimmte unkritische Aufgaben verzögern oder deren Genauigkeit oder QoS verringern. Auf diese Weise wird die Systemlast reduziert, bevor ein kritischer Punkt erreicht wird.
Lösungen des aktuellen Stands der Technik wie einheitliche Programmiersprachen oder Laufzeitsysteme adressieren einige der oben genannten Herausforderungen, jedoch existiert kein Ansatz, der in der Lage ist, eine Optimierung mehrerer sich widersprechender Zielfunktionen dynamisch und vor allem proaktiv durchzuführen. Ein Konzept, das diese komplexe Aufgabe für den Entwickler übernimmt und eine Möglichkeit zur dynamischen und proaktiven Anpassung an Veränderungen bietet, ist die Selbstorganisation. Selbstorganisation ist jedoch definiert als ein Prozess ohne externe Kontrolle oder Steuerung. Im Kontext der Systemoptimierung kann dies leicht zu unerwünschten Ergebnissen führen. Ein Ansatz, der Selbstorganisation mit einem Kontrollmechanismus kombiniert, welcher auf Robustheit und Widerstandsfähigkeit gegenüber äußeren Störungen abzielt, ist Organic Computing. Das bestimmende Merkmal von Organic Computing ist eine Observer/Controller-Architektur. Das Konzept dieser Architektur besteht darin, den aktuellen Zustand des Systems und der Umgebung zu überwachen, diese Daten zu analysieren und auf der Grundlage dieser Analyse Entscheidungen über das zukünftige Systemverhalten zu treffen. Organic Computing ermöglicht es also auf der Grundlage der vergangenen und des aktuellen Zustands proaktiv Mechanismen auszuwählen und auszulösen, die das System optimieren und unerwünschte Zustände vermeiden.
Um die Vorteile des Organic Computings auf moderne heterogene Systeme zu übertragen, kombiniere ich den Organic Computing-Ansatz mit einem Laufzeitsystem. Laufzeitsysteme sind ein vielversprechender Kandidat für die Umsetzung des Organic Computing-Ansatzes, da sie bereits die Ausführung von Anwendungen überwachen und steuern. Insbesondere betrachte und bearbeite ich in dieser Dissertation die folgenden Forschungsthemen, indem ich die Konzepte des Organic Computings und der Laufzeitsysteme kombiniere:
• Erfassen des aktuellen Systemzustands durch Überwachung von Sensoren und Performance Countern
• Vorhersage zukünftiger Systemzustände durch Analyse des vergangenen Verhaltens
• Nutzung von Zustandsinformationen zur proaktiven Anpassung des Systems
Ich erweitere das Thema der Erfassung von Systemzuständen auf zwei Arten.
Zunächst führe ich eine neuartige heuristische Metrik zur Berechnung der Zuverlässigkeit einer Verarbeitungseinheit ein, die auf symptombasierter Fehlererkennung basiert. Symptombasierte Fehlererkennung ist eine leichtgewichtige Methode zur dynamischen Erkennung von soften Hardware-Fehlern durch Überwachung des Ausführungsverhaltens mit Performance Countern. Die dynamische Erkennung von Fehlern ermöglicht dann die Berechnung einer heuristischen Fehlerrate einer Verarbeitungseinheit in einem bestimmten Zeitfenster. Die Fehlerrate wird verwendet, um die Anzahl der erforderlichen Ausführungen einer Anwendung zu berechnen, um eine bestimmte Ergebniszuverlässigkeit, also eine Mindestwahrscheinlichkeit für ein korrektes Ergebnis, zu gewährleisten. Ein wichtiger Aspekt der Zustandserfassung ist die Minimierung des entstehenden Overheads.
Ich verringere die Anzahl der für OpenMP-Tasks notwendigen Profiling-Durchläufe durch Thread-Interpolation und Überprüfungen des Skalierungsverhaltens. Zusätzlich untersuche ich die Vorhersage von OpenCL Task-Ausführungszeiten. Die Prädiktoren der Ausführungszeiten werden mit verschiedenen maschinellen Lernalgorithmen trainiert. Als Input werden Profile der Kernel verwendet, die durch statische Codeanalyse erstellt wurden.
Um in dieser Dissertation zukünftige Systemzustände vorherzusagen, sollen Anwendungen vorausgesagt werden, die in naher Zukunft im System vorkommen werden. In Kombination mit der Ausführungsdatenbank ermöglicht dies die Schätzung der anstehenden Kosten, die das System zu bewältigen hat.
In dieser Arbeit werden zwei Mechanismen zur Vorhersage von Anwendungen/Tasks entwickelt. Der erste Prädiktor zielt darauf ab, neue Instanzen unabhängiger Tasks vorherzusagen. Der zweite Mechanismus betrachtet Ausführungsmuster abhängiger Anwendungen und sagt auf dieser Grundlage zukünftig auftretende Anwendungen vorher. Beide Mechanismen verwenden eine Vorhersagetabelle, die auf Markov-Prädiktoren und dem Abgleich von Mustern basiert.
In dieser Arbeit wird das Wissen, das durch die Systemüberwachung und die Vorhersage zukünftiger Anwendungen gewonnen wird, verwendet, um die Optimierungsziele des Systems proaktiv in Einklang zu bringen und zu gewichten. Dies geschieht durch eine Reihe von Regeln, die eine Systemzustandsbeschreibung, bestehend aus dem aktuellen Zustand, Vorhersagen und Randbedingungen bzw. Beschränkungen, auf einen Vektor aus Gewichten abbilden. Zum Erlernen der Regelmenge wird ein Extended Classifer System (XCS) eingesetzt. Das XCS ist in eine hierarchische Architektur eingebettet, die nach den Prinzipien des Organic Computing entworfen wurde. Eine wichtige Designentscheidung ist dabei die Auslagerung der Erstellung neuer Regeln an einen Offline-Algorithmus, der einen Simulator nutzt und parallel zum normalen Systemablauf ausgeführt wird. Dadurch wird sichergestellt, dass keine ungetesteten Regeln, deren Auswirkungen noch nicht bekannt sind, dem laufenden System hinzugefügt werden. Die sich daraus ergebenden Gewichte werden schließlich verwendet, um eine Bewertungsfunktion für List Scheduling-Algorithmen zu erstellen.
Diese Dissertation erweitert das Forschungsgebiet der Scheduling-Algorithmen durch zwei Mechanismen für dynamisches Scheduling.
Die erste Erweiterung konzentriert sich auf nicht sicherheitskritische Systeme, die Prioritäten verwenden, um die unterschiedliche Wichtigkeit von Tasks auszudrücken. Da statische Prioritäten in stark ausgelasteten Systemen zu Starvation führen können, habe ich einen dynamischen Ageing-Mechanismus entwickelt, der dazu in der Lage ist, die Prioritäten der Tasks entsprechend der aktuellen Auslastung und ihrer Wartezeiten anzupassen. Dadurch reduziert der Mechanismus die Gesamtlaufzeit über alle Tasks und die Wartezeit für Tasks mit niedrigerer Priorität.
Noch ist eine große Anzahl von Anwendungen nicht dazu bereit, den hohen Grad an Parallelität zu nutzen, den moderne Computersysteme bieten. Ein Konzept, das versucht dieses Problem zu lösen, indem es mehrere verschiedene Prozesse auf demselben Rechenknoten zur Ausführung bringt, ist das Co-Scheduling. In dieser Dissertation stelle ich einen neuartigen Co-Scheduling-Mechanismus vor, welcher die Task-Schedules mehrerer Laufzeitsysteminstanzen optimiert, die auf demselben Rechenknoten ausgeführt werden. Um die notwendigen Informationen zwischen den Laufzeitsysteminstanzen zu teilen, speichert der Mechanismus die Daten in Shared Memory. Sobald ein Laufzeitsystem neue Tasks in das System einfügt, prüft der Mechanismus, ob die Berechnung eines neuen Schedules sinnvoll ist. Wird die Entscheidung getroffen, einen neuen Schedule zu berechnen, setzt der Mechanismus Simulated Annealing ein, um alle Tasks, die bisher noch nicht mit ihrer Ausführung begonnen haben, neu auf Ausführungseinheiten abzubilden.
Zusammenfassend lässt sich sagen, dass diese Arbeit neuartige Mechanismen und Algorithmen sowie Erweiterungen zu verschiedenen Forschungsgebieten anbietet, um ein proaktives selbst-organisierendes System zu implementieren, das sich an neue und unbekannte Situationen anpassen kann.
Dabei wird die Komplexität für Benutzer und Anwendungsentwickler reduziert, indem die Entscheidungsfindung in das System selbst ausgelagert wird. Gleichzeitig sorgt dieser Ansatz für eine effiziente Nutzung der Ressourcen des Systems. Insgesamt leistet diese Arbeit die folgenden Beiträge zur Erweiterung des Stands der Forschung:
• Einführung einer neuartigen heuristischen Metrik zur Messung der Zuverlässigkeit von Verarbeitungseinheiten. Die Metrik basiert auf einer leichtgewichtigen Methode zur Fehlererkennung, genannt symptombasierte Fehlererkennung. Mit der symptombasierten Fehlererkennung ist es möglich, mehrere injizierte Fehlerklassen und Interferenzen, die Soft-Hardware-Fehler simulieren, sowohl auf einer CPU als auch auf einer GPU zuverlässig zu erkennen. Darüber hinaus werden diese Ergebnisse durch Welch's t-Test statistisch bestätigt.
• Vorschlag eines Vorhersagemodells für die Ausführungszeit von OpenCL Kerneln, das auf statischer Code-Analyse basiert. Das Modell ist in der Lage, die schnellste Verarbeitungseinheit aus einer Menge von Verarbeitungseinheiten mit einer Genauigkeit von im schlechtesten Fall $69\,\%$ auszuwählen. Zum Vergleich: eine Referenzvariante, welche immer den Prozessor vorhersagt, der die meisten Kernel am schnellsten ausführt, erzielt eine Genauigkeit von $25\,\%$. Im besten Fall erreicht das Modell eine Genauigkeit von bis zu $83\,\%$.
• Bereitstellung von zwei Prädiktoren für kommende Tasks/Anwendungen. Der erste Mechanismus betrachtet unabhängige Tasks, die ständig neue Task-Instanzen erstellen, der zweite abhängige Anwendungen, die Ausführungsmuster bilden. Dabei erzielt der erste Mechanismus bei der Vorhersage der Zeitspanne zwischen zwei aufeinanderfolgenden Task-Instanzen einen maximalen\\ $sMAPE$-Wert von $4,33\,\%$ für sporadische und $0,002 \,\%$ für periodische Tasks. Darüber hinaus werden Tasks mit einem aperiodischen Ausführungsschema zuverlässig erkannt. Der zweite Mechanismus erreicht eine Genauigkeit von $77,6 \,\%$ für die Vorhersage der nächsten anstehenden Anwendung und deren Startzeit.
• Einführung einer Umsetzung eines hierarchischen Organic Computing Frameworks mit dem Anwendungsgebiet Task-Scheduling. Dieses Framework enthält u.a. ein modifiziertes XCS, für dessen Design und Implementierung ein neuartiger Reward-Mechanismus entwickelt wird. Der Mechanismus bedient sich dabei eines speziell für diesen Zweck entwickelten Simulators zur Berechnung von Task-Ausführungskosten. Das XCS bildet Beschreibungen des Systemzustands auf Gewichte zur Balancierung der Optimierungsziele des Systems ab. Diese Gewichte werden in einer Bewertungsfunktion für List Scheduling-Algorithmen verwendet. Damit wird in einem Evaluationsszenario, welches aus einem fünfmal wiederholten Muster aus Anwendungen besteht, eine Reduzierung der Gesamtlaufzeit um $10,4\,\%$ bzw. $26,7\,s$, des Energieverbrauchs um $4,7\,\%$ bzw. $2061,1\,J$ und der maximalen Temperatur der GPU um $3,6\,\%$ bzw. $2,7 K$ erzielt. Lediglich die maximale Temperatur über alle CPU-Kerne erhöht sich um $6\,\%$ bzw. $2,3\,K$.
• Entwicklung von zwei Erweiterungen zur Verbesserung des dynamischen Task-Schedulings für einzelne und mehrere Prozesse, z.B. mehrere Laufzeitsysteminstanzen. Der erste Mechanismus, ein Ageing-Algorithmus, betrachtet nicht sicherheitskritische Systeme, welche Task-Prioritäten verwenden, um die unterschiedliche Bedeutung von Anwendungen darzustellen. Da es in solchen Anwendungsszenarien in Kombination mit hoher Systemauslastung zu Starvation kommen kann, passt der Mechanismus die Task-Prioritäten dynamisch an die aktuelle Auslastung und die Task-Wartezeiten an. Insgesamt erreicht dieser Mechanismus in zwei Bewertungsszenarien eine durchschnittliche Laufzeitverbesserung von $3,75\,\%$ und $3,16\,\%$ bei gleichzeitiger Reduzierung der Durchlaufzeit von Tasks mit niedrigerer Priorität um bis zu $25,67\,\%$. Der zweite Mechanismus ermöglicht die Optimierung von Schedules mehrerer Laufzeitsysteminstanzen, die parallel auf demselben Rechenknoten ausgeführt werden. Dieser Co-Scheduling-Ansatz verwendet Shared Memory zum Austausch von Informationen zwischen den Prozessen und Simulated Annealing zur Berechnung neuer Task-Schedules. In zwei Evaluierungsszenarien erzielt der Mechanismus durchschnittliche Laufzeitverbesserungen von $19,74\,\%$ und $20,91\,\%$ bzw. etwa $2,7\,s$ und $3\,s$.
Modern computing systems offer a high degree of parallelism and heterogeneity to users and application developers. However, efficiently utilizing these systems requires deep knowledge, e.g., of the underlying hardware platform and different programming models, and extensive work from a developer. In this thesis, efficient usage is related to application makespan, the system's energy consumption, the maximum temperature of processing units, and system reliability. Next to multiple optimization goals, an application developer has to consider the system's specific constraints like application deadlines or safety guarantees that come with certain fields of application. ... mehrThis complexity of heterogeneous systems makes it impossible to predict all potential system states and environmental effects that could occur at runtime. Therefore, the system and application developers are not able to determine at design time how the system and applications should react in all potential situations. For this reason, systems have to be dynamically adapted at runtime to optimize their behavior according to the current situation. E.g., in embedded systems with limited cooling capacities, load balancing, frequency reduction, or switching off processing units to reduce heat is necessary when a certain temperature threshold is reached.
But just reacting to a disadvantageous system state is usually not enough.
The objective should be to proactively avoid disadvantageous or faulty system states altogether to lessen the necessity to call emergency functionality and improve the user experience. For example instead of reducing heat by rebalancing tasks, proactive mechanisms could avoid critical temperatures beforehand by delaying certain uncritical tasks or reducing their accuracy or quality of service (QoS). Thereby, the system load gets reduced before a critical point is reached.
Solutions offered by the literature like uniform programming languages or runtime systems address some of the aforementioned challenges, however no approach exists that is able to dynamically and, in particular, proactively balance multiple contradicting optimization goals. A concept that unburdens the developer from this complexity and provides a way to dynamically and proactively adapt to changes is self-organization. However, self-organization is defined as a process without external control or guidance.
In the context of system optimization this can easily lead to undesired results. An approach that combines self-organization with a control mechanism that aims for robustness and resilience against outside disturbances is organic computing.
The defining characteristic of organic computing is an observer/controller architecture. The concept of this architecture is monitoring the current state of the system and the environment, analyzing this data, and making decisions about the future system behavior based on this analysis.
I.e., organic computing enables to proactively select and trigger mechanisms that optimize the system and avoid undesired states based on past and current states.
To transfer the benefits of organic computing to modern heterogeneous systems, I combine the organic computing approach with a runtime system.
Runtime systems are a promising candidate to implement the organic computing approach as they already monitor and control the execution of applications. In particular, I work on the following research topics in this thesis by combining the concepts of organic computing and runtime systems:
• Capturing the current system state by monitoring sensors and performance counters
• Predicting future system states by analyzing past behavior
• Utilizing state information to proactively adapt the system
I provide extensions to the topic of system state capturing in two ways.
First, I introduce a novel heuristic metric for a processing unit's reliability based on symptom-based fault detection. Symptom based fault detection is a light-weight method to dynamically detect soft hardware errors by monitoring execution behavior with performance counters. Dynamically detecting faults then allows to compute a heuristic fault rate for a processing unit in a specific time window. The fault rate is employed to compute the number of required executions of a task to guarantee a given result reliability. An important aspect of system state capturing is minimizing the emerging overhead. I reduce the number of necessary profiling runs for OpenMP tasks via thread interpolation and scaling checks. Additionally, I study predicting OpenCL task execution times without executing them. The prediction models are trained with different machine learning algorithms. Profiles of the kernels created by static code analysis are thereby used as input.
To forecast future system states, I focus on predicting upcoming tasks/applications that will arrive in the system in the near future. Combined with the monitoring database, this enables to estimate the upcoming costs that the system has to handle. This thesis creates two task prediction mechanisms, one targeting independent tasks that repeatedly create new task instances and one targeting dependent applications that form execution patterns. Both mechanisms deploy a prediction table based on Markov predictors and pattern matching.
In this thesis, the knowledge that is acquired through system monitoring and task prediction is used to proactively balance the system's optimization goals. This is done through a set of rules that maps a system state description, consisting of the current state, predictions, and system constraints, onto a set of weights. To learn these rules, an extended classifier system XCS is employed. The XCS is embedded in a hierarchical architecture designed by organic computing principles. Hereby, an important design decision is outsourcing the creation of new rules to an offline algorithm that utilizes simulation and runs in parallel to the normal tasks of the system. So, no untested rules whose effects are not yet known are added to the live system. The resulting weights are then used to build an evaluation function for list scheduling algorithms.
This thesis adds to the research field task scheduling algorithms by providing two extensions to dynamic scheduling algorithms. The first extension focuses on non-safety-critical systems that utilize priorities to express differing application importance. As static priorities may lead to starvation in highly utilized systems, I created a dynamic aging mechanism that is able to adapt task priorities according to the current utilization and task waiting times. Thereby, the mechanism reduces the total makespan over all tasks and the waiting time for lower priority tasks.
As of yet, a great number of applications is not ready to capitalize on the high degree of parallelism offered by modern computing systems. A concept that tries to solve this problem by scheduling several different processes on the same computing node is co-scheduling. In this thesis, I introduce a novel co-scheduling mechanism that is able to optimize the task schedules of several runtime system instances executing on the same computing node.
To share the necessary information between the runtime system instances, the mechanism stores the data in shared memory. When a runtime system inserts new tasks into the system, the mechanism checks if computing a new schedule is sensible. If the decision to create a new schedule is made, the mechanism employs simulated annealing to schedule all tasks which have not yet started their execution.
To summarize, this thesis offers novel mechanisms and algorithms, and extensions to several research fields in order to implement a proactive self-organizing system that is able to adapt to new and unknown situations.
Thereby, complexity for users and application developers is reduced by outsourcing decision making into the system itself.
Simultaneously, this approach maintains the efficient usage of the system's resources.
In total, this thesis makes the following contributions:
• Introducing a novel heuristic metric to measure reliability of processing units. The metric is based on the light-weight fault detection method symptom-based fault detection. Symptom-based fault detection is able to reliably detect several injected fault classes and interferences simulating soft hardware errors on both a CPU and a GPU. Furthermore, it confirms these results statistically in Welch's t-test.
• Proposing an OpenCL kernel execution time prediction model based on static code analysis. The model is able to select the fastest processing unit out of a set of processing units with an accuracy of $69\,\%$ in the worst case compared to a baseline accuracy of $25\,\%$ that always predicts the processor that dominates the highest amount of kernels. In the best case, the model achieves an accuracy of up to $83\,\%$. Providing two prediction mechanisms for upcoming tasks, one targeting independent tasks that constantly create new task instances and one targeting dependent applications that form execution patterns. The first mechanism obtains an maximum $sMAPE$ value of $4.33\,\%$ for sporadic and $0.002 \,\%$ for periodic tasks while predicting the time period between two consecutive task instances. Additionally, it reliably detects tasks that posses an aperiodic execution scheme. The second predictor achieves an accuracy of $77.6\,\%$ forecasting the next upcoming task and its starting time.
• Introducing an implementation of a hierarchical organic computing framework including a modified XCS in the context of task scheduling. To implement the framework, a novel reward mechanism utilizing a specifically implemented task execution cost simulator is proposed. The XCS maps system state descriptions onto weights to balance the system's optimization objectives. Integrated as an evaluation function for a list scheduling algorithm, this concepts on average decreases the makespan by $10.4\,\%$ or $26.7\,s$, the energy consumption by $4.7\,\%$ or $2061.1\,J$, and the maximum temperature of the GPU by $3.6\,\%$ or $2.7 K$ while only increasing the maximum CPU core temperature by $6\,\%$ or $2.3\,K$ in an evaluation scenario consisting of an application pattern that is repeated five times.
• Proposing two extensions that improve dynamic task scheduling for a single and multiple processes, e.g., multiple runtime system instances. The first mechanism, an aging algorithm, targets non-safety critical systems that utilize task priorities to represent differing application importance. To avoid starvation in such scenarios, it dynamically adapts task priorities according to the current utilization and task waiting times. Overall, this mechanism achieves an average speed up of $3.75\,\%$ and $3.16\,\%$ in two evaluation scenarios while reducing the flow time of lower priority tasks by up to $25,67\,\%$. The second mechanism enables the schedule optimization of several runtime system instances executing on the same computing node in parallel. This co-scheduling approach employs shared memory to share information between the processes and simulated annealing to compute new schedules. In two evaluation scenarios the mechanism achieves average speed ups of $19.74\,\%$ and $20.91\,\%$ or about $2.7\,s$ and $3\,s$, respectively.
