Dynamic Resource Management and Job Scheduling for High Performance Computing

Prabhakaran, Suraj (2016)
Dynamic Resource Management and Job Scheduling for High Performance Computing.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

Preview

Other (PDF)
dissertation.pdf - Published Version
Copyright Information: CC BY-NC-ND 4.0 International - Creative Commons, Attribution NonCommercial, NoDerivs.
Download (2MB) | Preview

Item Type:

Ph.D. Thesis

Type of entry:

Primary publication

Title:

Dynamic Resource Management and Job Scheduling for High Performance Computing

Language:

English

Referees:

Wolf, Prof. Dr. Felix ; Brinkmann, Prof. Dr. André

Date:

30 August 2016

Place of Publication:

Darmstadt

Date of oral examination:

14 October 2016

Abstract:

Job scheduling and resource management plays an essential role in high-performance computing. Supercomputing resources are usually managed by a batch system, which is responsible for the effective mapping of jobs onto resources (i.e., compute nodes). From the system perspective, a batch system must ensure high system utilization and throughput, while from the user perspective it must ensure fast response times and fairness when allocating resources across jobs.

Parallel jobs can be divided into four categories - rigid, moldable, malleable, and evolving. While rigid jobs have fixed resource requirements over their entire life cycle, moldable jobs allow batch systems to deviate from the requested number of resources before job start. In contrast, malleable and evolving jobs can adapt to changing resource allocations at runtime. While batch systems can expand or shrink a malleable job's resource allocation at any point of time, expanding and shrinking an evolving job occurs only in response to a request made by the application itself.

Traditional batch systems support only rigid and moldable jobs, that is, they perform static resource management. However, this is not sufficient as supercomputing enters a new era. Scientific applications are becoming much more complex and now often exhibit unpredictably changing resource requirements. Programming models are also becoming more adaptive in nature to support malleability for energy efficiency and fault tolerance. Therefore, scheduling evolving and malleable jobs (i.e., dynamic resource management) will be indispensable, especially on future large-scale systems. This dissertation therefore proposes novel dynamic resource management and scheduling techniques for cluster systems, making multiple contributions in the areas of dynamic resource (de)allocation mechanisms, efficient adaptive job scheduling, and resiliency.

As the first contribution, this thesis presents dynamic scheduling methods for evolving jobs. A fairness scheme is proposed to ensure the fair allocation of resources between static and dynamic resource requests. The evaluation with a workload containing both rigid and evolving jobs shows that high resource utilization and throughput can be achieved, while maintaining the fair dynamic assignment of resources. It is also demonstrated how these methods can be beneficially employed in heterogeneous architectures with network-attached accelerators.

The second contribution presents a unique scheduling technique for malleable jobs and an algorithm for the combined scheduling of all four types of jobs in a cluster environment. We introduce the Dependency-based Expand/Shrink (DBES) algorithm, which rests on a two-phase malleable job expand/shrink strategy. The batch system is evaluated with a mixed workload and our strategy achieves consistently superior performance in comparison to state-of-the-art malleable job scheduling strategies.

Finally, as the last contribution, we present a scheduling algorithm for dynamic node replacement, which improves the resiliency of cluster systems. The algorithm uses the unique features of the four job types and can provide replacement nodes instantly to jobs affected by node failures. Among current fault tolerance mechanisms, our technique causes the smallest loss of throughput.

Alternative Abstract:

Alternative Abstract

Language

Job Scheduling und Ressourcen-Management spielen eine wesentliche Rolle im Bereich High-Performance Computing. Die Ressourcen von Hochleistungsrechnern werden für gewöhnlich von einem Batch System verwaltet, welches für die effektive Abbildung von Jobs auf Rechenknoten verantwortlich ist. Aus der Systemperspektive betrachtet, muss das Batch System für hohe Systemauslastung und Durchsatzleistung sorgen. Aus der Sicht des Nutzers sollte es eine gerechte Verteilung der Ressourcen und schnelle Antwortzeiten sicherstellen.

Es ist üblich, parallele Jobs in vier Klassen zu unterteilen - Rigid, Moldable, Malleable und Evolving. Während Jobs der Klasse Rigid festgelegte Vorgaben zur Auftragserteilung haben, erlauben Jobs der Klasse Moldable dem Batch System, die Zahl der Ressourcen vor der Ausführung zu verändern. Demgegenüber können sich Jobs der Klassen Malleable und Evolving auch zur Laufzeit an eine wechselnde Ressourcenzuteilung anpassen. Batch Systeme können die zugeteilten Ressourcen eines Jobs der Klasse Malleable zu jeder Zeit ausweiten oder verkleinern. Bei einem Job der Klasse Evolving kann dies jedoch nur auf ausdrückliche Anfrage der Anwendung selbst erfolgen.

Traditionelle Batch Systeme unterstützen nur Jobs der Klassen Rigid und Moldable (statische Ressourcenverwaltung). Dies ist allerdings angesichts der aktuellen Entwicklung nicht mehr ausreichend. Wissenschaftliche Anwendungen sind sehr viel komplexer geworden und weisen nun häufig unvorhersehbare Veränderungen ihres Ressourcenbedarfs auf. Zusätzlich werden Programmiermodelle anpassungsfähiger und unterstützen Malleability zur Verbesserung der Energieeffizienz und Fehlertoleranz in kommenden Exascale-Systemen. Daher wird auch das Scheduling von Jobs der Klassen Evolving und Malleable unverzichtbar werden. Aus diesem Grund präsentiert diese Dissertation neue Techniken zur dynamischen Ressourcenverwaltung und zum Scheduling auf Cluster Systemen und leistet dadurch Beiträge in den Bereichen dynamische Ressourcen(de)allokation, effizientes adaptives Jobscheduling und Resilienz.

Zunächst wird ein dynamisches Schedulingverfahren für Jobs der Klasse Evolving vorgestellt. Ein Fairness Konzept sorgt für die gerechte Verteilung von Ressourcen zwischen statischen und dynamischen Anfragen. Die Auswertung unter einer Last bestehend aus Jobs der Klassen Rigid und Evolving zeigt, dass unter der Wahrung einer fairen Ressourcenzuordnung eine hohe Systemauslastung und Durchsatzleistung erreicht werden kann. Es wird zudem gezeigt, wie diese Funktion in unkonventionellen, heterogenen Architekturen verwendet werden kann.

Der zweite Beitrag der Arbeit umfasst ein neuartiges Verfahren für Jobs der Klasse Malleable sowie einen Algorithmus für die gemeinsame Planung aller vier der oben genannten Jobklassen auf einem Clustersystem. Vorgestellt wird der DBES Algorithmus, welcher zwei Phasen zur Ausweitung und Verkleinerung von Malleable Jobs vorsieht. Das Batch System wird mit einer gemischten Last untersucht. Die Ergebnisse zeigen eine überlegene Leistung im Vergleich zu anderen modernen Schedulingverfahren.

Der dritte Beitrag ist schließlich ein Algorithmus zum dynamischen Austausch von Knoten, der geeignet ist, die Fehlertoleranz von Clustersystemen zu erhöhen. Der Algorithmus nutzt die spezifischen Eigenschaften aller vier Jobtypen und ist dadurch imstande, ausgefallene Knoten zu ersetzen. Unter den aktuellen Fehlertoleranz-Mechanismen bietet der vorgeschlagene Algorithmus den geringsten Durchsatzverlust.

German

Uncontrolled Keywords:

resource management, job scheduling, adaptive scheduling, dynamic scheduling, high performance computing, batch systems

URN:

urn:nbn:de:tuda-tuprints-57204

Classification DDC:

000 Generalities, computers, information > 004 Computer science

Divisions:

20 Department of Computer Science
20 Department of Computer Science > Parallel Programming

Date Deposited:

31 Oct 2016 11:12

Last Modified: