Dissertation
Load Balancing, Fault Tolerance, and Resource Elasticity for Asynchronous Many-Task Systems
Abstract
High-Performance Computing (HPC) ermöglicht die Lösung komplexer Probleme aus verschiedenen wissenschaftlichen Bereichen, einschließlich gesellschaftlicher Probleme wie z.B. COVID-19. In letzter Zeit gibt es neben traditionellen Simulationen immer mehr irreguläre Anwendungen, welche die Vorhersagbarkeit der Berechnungen einschränken. Die Anwendungen werden auf HPC-Maschinen ausgeführt, die aus immer mehr Hardwarekomponenten bestehen und von mehreren Benutzern gleichzeitig verwendet werden. Um eine effiziente und produktive Programmierung heutiger und zukünftiger HPC-Maschinen zu ermöglichen, muss eine Reihe von Problemen bewältigt werden, u.a.: Lastenausgleich (gleichmäßiges Auslasten der Ressourcen), Fehlertoleranz (Bewältigen von Hardwareausfällen) und Ressourcenelastizität Hinzufügen/Entfernen von Ressourcen).
In dieser Dissertation adressieren wir die Probleme im Kontext der Asynchronous Many-Task (AMT) Programmierung. Bei AMT teilen Programmierer eine Berechnung in viele feingranulare Ausführungseinheiten (engl. Tasks) auf, die von einem Laufzeitsystem dynamisch an Recheneinheiten (z.B. Threads) zugewiesen werden. Während sich AMT für Einzelrechner immer mehr etabliert, konzentrieren wir uns auf Cluster-AMTs, bei denen es sich derzeit lediglich um Prototypen mit eingeschränktem Funktionsumfang handelt.
Hinsichtlich Lastenausgleich schlagen wir eine Work-Stealing-Technik vor, die Tasks transparent Ressourcen zuweist und so die Last über alle Recheneinheiten balanciert. In diesem Kontext führen wir mehrere Tasking-Konstrukte ein. Experimente zeigen eine gute Skalierbarkeit, und eine Produktivitäts-Evaluierung zeigt eine intuitive Handhabung.
Hinsichtlich Fehlertoleranz schlagen wir vier Techniken für den transparenten Schutz von Programmen vor. Nach einem Fehler wird die Ausführung eines Programms mit weniger Ressourcen fortgeführt. Drei Techniken schreiben unkoordinierte Sicherheitskopien in einen resilienten Speicher: Eine speichert alle offenen Task-Deskriptoren, die zweite speichert nur einen Teil davon, und die dritte protokolliert Stealing-Ereignisse um die Anzahl der Sicherheitskopien zu reduzieren. Die vierte Technik schreibt keine Sicherheitskopien, sondern nutzt Duplikationen während des Work-Stealings. Experimente zeigen keinen eindeutigen Sieger, z.B. hat die erste Technik bei schwacher Skalierung einen Mehraufwand ohne Fehler von unter 1% und für Wiederherstellungen von unter 0,5 Sekunden. Simulationen einer Menge von Jobs zeigen eine Reduzierung der Ausführungszeit um bis zu 97%.
Hinsichtlich Ressourcenelastizität schlagen wir eine Technik zum Hinzufügen und Entfernen von Rechenknoten vor, die Tasks entsprechend transparent verlagert. Experimente zeigen Kosten für das Hinzufügen/Entfernen unter 0,5 Sekunden. Simulationen einer Menge von Jobs zeigen eine Reduzierung der Ausführungszeit um bis zu 20%.
In dieser Dissertation adressieren wir die Probleme im Kontext der Asynchronous Many-Task (AMT) Programmierung. Bei AMT teilen Programmierer eine Berechnung in viele feingranulare Ausführungseinheiten (engl. Tasks) auf, die von einem Laufzeitsystem dynamisch an Recheneinheiten (z.B. Threads) zugewiesen werden. Während sich AMT für Einzelrechner immer mehr etabliert, konzentrieren wir uns auf Cluster-AMTs, bei denen es sich derzeit lediglich um Prototypen mit eingeschränktem Funktionsumfang handelt.
Hinsichtlich Lastenausgleich schlagen wir eine Work-Stealing-Technik vor, die Tasks transparent Ressourcen zuweist und so die Last über alle Recheneinheiten balanciert. In diesem Kontext führen wir mehrere Tasking-Konstrukte ein. Experimente zeigen eine gute Skalierbarkeit, und eine Produktivitäts-Evaluierung zeigt eine intuitive Handhabung.
Hinsichtlich Fehlertoleranz schlagen wir vier Techniken für den transparenten Schutz von Programmen vor. Nach einem Fehler wird die Ausführung eines Programms mit weniger Ressourcen fortgeführt. Drei Techniken schreiben unkoordinierte Sicherheitskopien in einen resilienten Speicher: Eine speichert alle offenen Task-Deskriptoren, die zweite speichert nur einen Teil davon, und die dritte protokolliert Stealing-Ereignisse um die Anzahl der Sicherheitskopien zu reduzieren. Die vierte Technik schreibt keine Sicherheitskopien, sondern nutzt Duplikationen während des Work-Stealings. Experimente zeigen keinen eindeutigen Sieger, z.B. hat die erste Technik bei schwacher Skalierung einen Mehraufwand ohne Fehler von unter 1% und für Wiederherstellungen von unter 0,5 Sekunden. Simulationen einer Menge von Jobs zeigen eine Reduzierung der Ausführungszeit um bis zu 97%.
Hinsichtlich Ressourcenelastizität schlagen wir eine Technik zum Hinzufügen und Entfernen von Rechenknoten vor, die Tasks entsprechend transparent verlagert. Experimente zeigen Kosten für das Hinzufügen/Entfernen unter 0,5 Sekunden. Simulationen einer Menge von Jobs zeigen eine Reduzierung der Ausführungszeit um bis zu 20%.
High-Performance Computing (HPC) enables solving complex problems from various scientific fields including key societal problems such as COVID-19. Recently, traditional simulations have been joined by more diverse workloads, including irregular ones limiting the predictability of the computations. Workloads are run on HPC machines that comprise an increasing number of hardware components, and serve multiple users simultaneously.
To enable efficient and productive programming of today’s HPC machines and beyond, it is essential to address a variety of issues, including: load balancing (i.e., utilizing all resources equally), fault tolerance (i.e., coping with hardware failures), and resource elasticity (i.e., allowing the addition/release of resources).
In this thesis, we address these issues in the context of Asynchronous Many-Task (AMT) programming. In AMT, programmers split a computation into many fine-grained execution units (called tasks), which are dynamically mapped to processing units (e.g., threads) by a runtime system. While AMT is becoming established for single computers, we are focusing on cluster AMTs, which are currently merely prototypes with limited functionalities.
Regarding load balancing, we propose a work stealing technique that transparently schedules tasks to resources of the overall system, balancing the workload over all processing units. In this context, we introduce several tasking constructs. Experiments show good scalability, and a productivity evaluation shows intuitive use.
Regarding fault tolerance, we propose four techniques to protect programs transparently. All perform localized recovery and continue the program execution with fewer resources. Three techniques write uncoordinated checkpoints in a resilient store: One saves descriptors of all open tasks; the second saves only part of them; and the third logs stealing events to reduce the number of checkpoints. The fourth technique does not write checkpoints at all, but exploits natural task duplication of work stealing. Experiments show no clear winner between the techniques. For instance, the first one has a failure-free running time overhead below 1% and a recovery overhead below 0.5 seconds, both for smooth weak caling. Simulations of job set executions show that the completion time can be reduced by up to 97%.
Regarding resource elasticity, we propose a technique to enable the addition and release of nodes at runtime by transparently relocating tasks accordingly. Experiments show costs for adding and releasing nodes below 0.5 seconds. Additionally, simulations of job set executions show that the completion time can be reduced by up to 20%.
To enable efficient and productive programming of today’s HPC machines and beyond, it is essential to address a variety of issues, including: load balancing (i.e., utilizing all resources equally), fault tolerance (i.e., coping with hardware failures), and resource elasticity (i.e., allowing the addition/release of resources).
In this thesis, we address these issues in the context of Asynchronous Many-Task (AMT) programming. In AMT, programmers split a computation into many fine-grained execution units (called tasks), which are dynamically mapped to processing units (e.g., threads) by a runtime system. While AMT is becoming established for single computers, we are focusing on cluster AMTs, which are currently merely prototypes with limited functionalities.
Regarding load balancing, we propose a work stealing technique that transparently schedules tasks to resources of the overall system, balancing the workload over all processing units. In this context, we introduce several tasking constructs. Experiments show good scalability, and a productivity evaluation shows intuitive use.
Regarding fault tolerance, we propose four techniques to protect programs transparently. All perform localized recovery and continue the program execution with fewer resources. Three techniques write uncoordinated checkpoints in a resilient store: One saves descriptors of all open tasks; the second saves only part of them; and the third logs stealing events to reduce the number of checkpoints. The fourth technique does not write checkpoints at all, but exploits natural task duplication of work stealing. Experiments show no clear winner between the techniques. For instance, the first one has a failure-free running time overhead below 1% and a recovery overhead below 0.5 seconds, both for smooth weak caling. Simulations of job set executions show that the completion time can be reduced by up to 97%.
Regarding resource elasticity, we propose a technique to enable the addition and release of nodes at runtime by transparently relocating tasks accordingly. Experiments show costs for adding and releasing nodes below 0.5 seconds. Additionally, simulations of job set executions show that the completion time can be reduced by up to 20%.
Citation
@phdthesis{doi:10.17170/kobra-202207286542,
author={Posner, Jonas},
title={Load Balancing, Fault Tolerance, and Resource Elasticity for Asynchronous Many-Task Systems},
school={Kassel, Universität Kassel, Fachbereich Elektrotechnik / Informatiik},
month={12},
year={2021}
}
0500 Oax
0501 Text $btxt$2rdacontent
0502 Computermedien $bc$2rdacarrier
1100 2021$n2021
1500 1/eng
2050 ##0##http://hdl.handle.net/123456789/14032
3000 Posner, Jonas
4000 Load Balancing, Fault Tolerance, and Resource Elasticity for Asynchronous Many-Task Systems / Posner, Jonas
4030
4060 Online-Ressource
4085 ##0##=u http://nbn-resolving.de/http://hdl.handle.net/123456789/14032=x R
4204 \$dDissertation
4170
5550 {{Hochleistungsrechnen}}
5550 {{Programmieren}}
5550 {{Supercomputer}}
5550 {{Elastizität}}
5550 {{Fehlertoleranz}}
7136 ##0##http://hdl.handle.net/123456789/14032
<resource xsi:schemaLocation="http://datacite.org/schema/kernel-2.2 http://schema.datacite.org/meta/kernel-2.2/metadata.xsd"> 2022-08-05T05:33:55Z 2022-08-05T05:33:55Z 2021-12-21 doi:10.17170/kobra-202207286542 http://hdl.handle.net/123456789/14032 eng Urheberrechtlich geschützt https://rightsstatements.org/page/InC/1.0/ 004 Load Balancing, Fault Tolerance, and Resource Elasticity for Asynchronous Many-Task Systems Dissertation High-Performance Computing (HPC) ermöglicht die Lösung komplexer Probleme aus verschiedenen wissenschaftlichen Bereichen, einschließlich gesellschaftlicher Probleme wie z.B. COVID-19. In letzter Zeit gibt es neben traditionellen Simulationen immer mehr irreguläre Anwendungen, welche die Vorhersagbarkeit der Berechnungen einschränken. Die Anwendungen werden auf HPC-Maschinen ausgeführt, die aus immer mehr Hardwarekomponenten bestehen und von mehreren Benutzern gleichzeitig verwendet werden. Um eine effiziente und produktive Programmierung heutiger und zukünftiger HPC-Maschinen zu ermöglichen, muss eine Reihe von Problemen bewältigt werden, u.a.: Lastenausgleich (gleichmäßiges Auslasten der Ressourcen), Fehlertoleranz (Bewältigen von Hardwareausfällen) und Ressourcenelastizität Hinzufügen/Entfernen von Ressourcen). In dieser Dissertation adressieren wir die Probleme im Kontext der Asynchronous Many-Task (AMT) Programmierung. Bei AMT teilen Programmierer eine Berechnung in viele feingranulare Ausführungseinheiten (engl. Tasks) auf, die von einem Laufzeitsystem dynamisch an Recheneinheiten (z.B. Threads) zugewiesen werden. Während sich AMT für Einzelrechner immer mehr etabliert, konzentrieren wir uns auf Cluster-AMTs, bei denen es sich derzeit lediglich um Prototypen mit eingeschränktem Funktionsumfang handelt. Hinsichtlich Lastenausgleich schlagen wir eine Work-Stealing-Technik vor, die Tasks transparent Ressourcen zuweist und so die Last über alle Recheneinheiten balanciert. In diesem Kontext führen wir mehrere Tasking-Konstrukte ein. Experimente zeigen eine gute Skalierbarkeit, und eine Produktivitäts-Evaluierung zeigt eine intuitive Handhabung. Hinsichtlich Fehlertoleranz schlagen wir vier Techniken für den transparenten Schutz von Programmen vor. Nach einem Fehler wird die Ausführung eines Programms mit weniger Ressourcen fortgeführt. Drei Techniken schreiben unkoordinierte Sicherheitskopien in einen resilienten Speicher: Eine speichert alle offenen Task-Deskriptoren, die zweite speichert nur einen Teil davon, und die dritte protokolliert Stealing-Ereignisse um die Anzahl der Sicherheitskopien zu reduzieren. Die vierte Technik schreibt keine Sicherheitskopien, sondern nutzt Duplikationen während des Work-Stealings. Experimente zeigen keinen eindeutigen Sieger, z.B. hat die erste Technik bei schwacher Skalierung einen Mehraufwand ohne Fehler von unter 1% und für Wiederherstellungen von unter 0,5 Sekunden. Simulationen einer Menge von Jobs zeigen eine Reduzierung der Ausführungszeit um bis zu 97%. Hinsichtlich Ressourcenelastizität schlagen wir eine Technik zum Hinzufügen und Entfernen von Rechenknoten vor, die Tasks entsprechend transparent verlagert. Experimente zeigen Kosten für das Hinzufügen/Entfernen unter 0,5 Sekunden. Simulationen einer Menge von Jobs zeigen eine Reduzierung der Ausführungszeit um bis zu 20%. High-Performance Computing (HPC) enables solving complex problems from various scientific fields including key societal problems such as COVID-19. Recently, traditional simulations have been joined by more diverse workloads, including irregular ones limiting the predictability of the computations. Workloads are run on HPC machines that comprise an increasing number of hardware components, and serve multiple users simultaneously. To enable efficient and productive programming of today’s HPC machines and beyond, it is essential to address a variety of issues, including: load balancing (i.e., utilizing all resources equally), fault tolerance (i.e., coping with hardware failures), and resource elasticity (i.e., allowing the addition/release of resources). In this thesis, we address these issues in the context of Asynchronous Many-Task (AMT) programming. In AMT, programmers split a computation into many fine-grained execution units (called tasks), which are dynamically mapped to processing units (e.g., threads) by a runtime system. While AMT is becoming established for single computers, we are focusing on cluster AMTs, which are currently merely prototypes with limited functionalities. Regarding load balancing, we propose a work stealing technique that transparently schedules tasks to resources of the overall system, balancing the workload over all processing units. In this context, we introduce several tasking constructs. Experiments show good scalability, and a productivity evaluation shows intuitive use. Regarding fault tolerance, we propose four techniques to protect programs transparently. All perform localized recovery and continue the program execution with fewer resources. Three techniques write uncoordinated checkpoints in a resilient store: One saves descriptors of all open tasks; the second saves only part of them; and the third logs stealing events to reduce the number of checkpoints. The fourth technique does not write checkpoints at all, but exploits natural task duplication of work stealing. Experiments show no clear winner between the techniques. For instance, the first one has a failure-free running time overhead below 1% and a recovery overhead below 0.5 seconds, both for smooth weak caling. Simulations of job set executions show that the completion time can be reduced by up to 97%. Regarding resource elasticity, we propose a technique to enable the addition and release of nodes at runtime by transparently relocating tasks accordingly. Experiments show costs for adding and releasing nodes below 0.5 seconds. Additionally, simulations of job set executions show that the completion time can be reduced by up to 20%. open access Posner, Jonas 2022-07-12 xxi, 194 Seiten Kassel, Universität Kassel, Fachbereich Elektrotechnik / Informatiik Fohry, Claudia (Prof. Dr.) Schulz, Martin (Prof. Dr.) Hochleistungsrechnen Programmieren Supercomputer Elastizität Fehlertoleranz publishedVersion false true </resource>
The following license files are associated with this item:
:Urheberrechtlich geschützt