Fault Tolerance and Elasticity for Global Task Pools
Final Report Abstract
Eine typische Vorgehensweise bei der parallelen Programmierung ist die Zerlegung des zu lösenden Problems in eine große Zahl von Teilaufgaben (Tasks). Die Tasks werden zur Laufzeit erzeugt und an die verfügbaren Rechenressourcen zugewiesen. Dies konnen beispielsweise Knoten eines Rechenclusters oder einzelne Prozessorkerne sein. Die Ressourcen werden durch Worker repräsentiert, die Tasks bearbeiten und dabei neue Tasks erzeugen konnen. Häufig verwaltet jeder Worker eine Liste noch nicht bearbeiteter Tasks, und Worker ohne Tasks “stehlen” Arbeit von anderen. Diese Vorgehensweise wird als Taskpool-Pattern bezeichnet. Taskpools erreichen auf allgemeingültige Weise eine Lastenbalancierung und werden deshalb immer häufiger eingesetzt. Traditionell verwenden sie eine feste Ressourcenmenge. Dies ist jedoch immer weniger gerechtfertigt, da mit zunehmender Maschinengröße die Zahl der Hardwarefehler steigt (Fehlertoleranz). Außerdem lässt sich die Gesamtauslastung der Rechner verbessern, wenn Anwendungen auf Ressourcenänderungen flexibel reagieren können (Ressourcen-Elastizität). Taskbasierte Parallelprogrammierung verspricht, auch mit diesen neuen Anforderungen umgehen zu konnen, da feingranulare Tasks geeignete Einheiten fur eine Migration auf andere Worker bilden. Dieses Potential des Taskpool-Patterns wurde bisher kaum untersucht. Entsprechend bestand das Projektziel in der Erarbeitung von Taskpool-Schemen, die mit Ausfallen und Ressourcenänderungen umgehen können. Im Projekt wurden mehrere solcher Algorithmen für verschiedene Taskpool-Varianten entwickelt. Allen ist gemeinsam, dass jeder Worker in regelmäßigen Zeitabständen mehr oder weniger umfangreiche Sicherungskopien seiner lokalen Taskliste erstellt und die Kopien bei Stehlvorgangen konsistent hält. So sind die Algorithmen in der Lage, mehrere, auch ungünstig korrelierte Ausfälle zu tolerieren. Die Integration neuer Ressourcen funktioniert auch, wenn es zwischenzeitlich zu Ausfällen kommt. Unsere Taskpool-Schemen berechnen stets das korrekte Ergebnis, oder brechen, in sehr wenigen Ausnahmefällen, die Berechnung ab. Die Algorithmen wurden teils in der parallelen Programmiersprache X10, überwiegend jedoch in der verwandten APGAS-Bibliothek für Java implementiert. Letztere bot durch ihre Anbindung an Java diverse Vorteile gegenüber dem im Antrag vorgesehenen X10. Unter anderem konnte eine fehlertolerante verteilte Datenstruktur benutzt werden, was die Verwaltung der Sicherungskopien erheblich vereinfachte und eine Steuerung ihrer Anzahl ermöglichte. Sowohl X10 als auch die APGAS-Bibliothek beziehen sich auf das Programmiermodell des “Partitioned Global Address Space” (PGAS). Es repräsentiert unterschiedliche Architekturen wie Cluster und Mehrkernprozessoren in einer einheitlichen Form. Im Projekt haben wir ein Taskpool-Schema entwickelt, das Lastenbalancierung innerhalb der Clusterknoten mit der zwischen den Knoten verbindet. Wir haben es im Laufzeitsystem der APGAS-Bibliothek implementiert und die Bibliothek um ein Konstrukt zum Start nicht-ortsgebundener Tasks erweitert. Das Konstrukt ist leicht benutzbar und wurde im Projekt erstmals effizient realisiert. Zu den Herausforderungen des Projekts gehörte der Umgang mit komplexen nebenläufigen Abläufen, die aus dem gleichzeitigen Verfolgen diverser Stehl-, Sicherungs- und Wiederherstellungsvorgänge resultieren. Im Unterschied zu anderen Fehlertoleranztechniken sind bei uns nur wenige Worker in Wiederherstellungsvorgänge involviert, während die übrigen ihre Arbeit ungestört fortsetzen. Die Qualität der entwickelten Schemen wurde durch Laufzeitmessungen bewertet. Der Overhead im fehlerfreien Fall lag am Projektende, je nach Benchmark, bei ca. 5% bis 8%. Wichtigster Effizienzfaktor waren die Kommunikationskosten. Sie hingen, entgegen unseren Erwartungen, fast ausschließlich von der Anzahl der Nachrichten statt von ihrem Volumen ab, was sich auf den Design unserer Fehlertoleranzschemen auswirkte.
Publications
- A malleable and fault-tolerant task pool framework for X10. In: Proc. IEEE Int. Conf. on Cluster Computing (IEEE Cluster), Workshop on Fault Tolerant Systems (FTS). pp. 749–757. Springer LNCS 3514 (2017)
Bungart, M., Fohry, C.
(See online at https://doi.org/10.1109/CLUSTER.2017.27) - Fault tolerance for lifeline-based global balancing. Journal of Software Engineering and Applications 10(13), 925–958 (2017)
Fohry, C., Bungart, M., Plock, P.
(See online at https://doi.org/10.4236/jsea.2017.1013053) - A Java task pool framework providing fault tolerant global load balancing. Int. Journal of Networking and Computing 8(1), 2–31 (2018)
Posner, J., Fohry, C.
(See online at https://doi.org/10.15803/ijnc.8.1_2) - Hybrid work stealing of locality-flexible and cancelable tasks for the APGAS library. The Journal of Supercomputing 47(4), 1435–1448 (2018)
Posner, J., Fohry, C.
(See online at https://doi.org/10.1007/s11227-018-2234-8)
