Parallelisierung für alle

Mathematische Probleme durch Simulation lösen
Kommentare

Physikalische Prozesse legen der maximal erreichbaren Taktrate einzelner Prozessorkerne enge Grenzen auf: Trotz immer effizienteren Halbleiterschaltungen steigt die aus einer einkernigen CPU entnehmbare Leistung nur sehr langsam.

Halbleiterhersteller begegnen diesem Problem seit einiger Zeit durch das Anbieten von Multicore-Prozessoren. Dabei handelt es sich um CPUs, die mit bis zu einem Dutzend Rechenkernen ausgestattet sind. Effizient aufgeteilte Programme können auf derartiger Hardware beeindruckende Performancesteigerungen erfahren – beim Umstieg von einem auf zwei Kerne kommt es oft zu einer Verdoppelung der Geschwindigkeit.

Dazu ist ein hoher Grad an Erfahrung auf Seiten des Entwicklers notwendig. Der durchschnittliche Entwickler ist (noch) nicht in der Lage, komplexe parallelisierte Applikationen zu realisieren. Beim manuellen Erstellen von Threads, Semaphoren und anderen Datenstrukturen tut sich eine Vielzahl von Fallen auf, die für unerfahrene Entwickler auch mithilfe eines Debuggers nicht oder nur sehr schwer zu beseitigen sind.

Seit der vierten Version des .NET Frameworks versucht Microsoft dieses Problem durch die Task-Parallel-Bibliothek zu lösen. Diese bietet eine Vielzahl von vorgefertigten Codestrukturen an, die das Makeln zwischen den Threads für den Entwickler transparent erledigen.

Leider stößt diese Art der Parallelisierung bei großen Rechenaufgaben an ihre Grenzen. Das Betreiben von mehreren Prozessorchips in einer Workstation setzt teure Spezialmainboards voraus, ab einem Dutzend Prozessoren ist die Verteilung in einen Cluster notwendig.

An dieser Stelle steht der Entwickler wieder alleine da. Die TPL ist nämlich nicht auf die Verteilung von Aufgaben über Clusternodes vorbereitet – Microsoft beschränkt die eigene Bibliothek auf die Nutzung der lokal verfügbaren Systemressourcen.

Parallelisierung à la Rapperswil

Informatiker würden das Problem der Distribution von Tasks in zwei Teile aufsplitten: erstens die Erstellung eines generischen Frameworks für die Verteilung, zweitens das Zusammenbauen der eigentlichen Payload.

Der in der Schweiz lebende Professor Dr. Luc Bläser befasste sich im Rahmen seiner Arbeit mit der Lösung des ersten Teils der Fragestellung. Sein auf der Parallel 2013 vorgestelltes Framework pfropft sich auf die soeben beschriebene Architektur auf. Das bedeutet, dass Sie Ihr Programm wie gewohnt unter Verwendung der von Microsoft vorgegebenen Building Blocks aufbauen. Danach erweitern Sie Ihre Lösung um die von der Universität Rapperswil angebotene Bibliothek. Diese enthält eine Gruppe von Klassen, deren innere Architektur die Verteilung der an sie übergebenen Tasks für den Entwickler transparent erledigt (Abb. 1).

Abb. 1: Automatische Taskverteilung

Nach dem Anfordern einer parallelisierten Berechnung beginnt das Framework mit der Serialisierung aller für die Abarbeitung des Tasks erforderlichen Daten. Diese wandern sodann in Richtung des Zentralservers, der für die Verteilung der Aufgaben in Cluster zuständig ist. Ist die Abarbeitung der einzelnen Tasks erledigt, wandern die Ergebnisse wieder zurück auf den Client.

Auf Seiten des Entwicklers ist vergleichsweise wenig Eigenintelligenz erforderlich. Das liegt daran, dass das Framework als „Extraebene“ unter die von Microsoft vorgegebenen Parallelisierungsklassen wandert (Abb. 2).

Abb. 2: Clusteraktivierung durch Einbinden einer zusätzlichen Abstraktionsschicht

TPL im Blick

Bevor wir uns mit der Parallelisierung im Cluster beschäftigen können, brauchen wir eine aufzuteilende Aufgabe. Die von Prof. Luc Bläser implementierte Verifikation von Primzahlen durch Faktorisierung ist aufgrund der vergleichsweise primitiven dahinterstehenden Mathematik ein dankbares Beispiel, das wir an dieser Stelle aufgreifen wollen. Seine Referenzimplementierung sieht im „lokalen Betriebsmodus“ so aus:

public static void ParallelComputeTasks(long[] inputs) {   var taskList = new List>();   foreach (long number in inputs) {     var task = Task.Factory.StartNew(() => _Factorize(number));     taskList.Add(task);   }   foreach (var task in taskList) {     Console.WriteLine(task.Result);   } }  

Task.Factory erlaubt das Erstellen von neuen Tasks. Diese werden in einem von der Factory bereitgestellten Thread abgearbeitet – die Anzahl der generierten Threads wird normalerweise vom System bestimmt, lässt sich aber durch das Übergeben von Parametern adjustieren.

Der Zugriff auf Result dient als Synchronisator: Er gibt erst dann etwas zurück, wenn der jeweilige Task seine Arbeit abgeschlossen und einen Wert zurückgeworfen hat. Die Rechenintelligenz findet sich in einer eigenen Methode, die aus dem ParallelTask heraus aufgerufen wird. Sie prüft die Zahl auf ihre Faktorisierbarkeit, der zurückgegebene Wert wandert sodann in Result:

private static long _Factorize(long number) {   for (long k = 2; k <= Math.Sqrt(number); k++) {     if (number % k == 0) { return k; }   }   return number; // not factorizable }

Dieses Programm wird mit einer Liste von bekannten und sehr langen Primzahlen aufgerufen. Dadurch ist sichergestellt, dass jede zu bearbeitende Zahl für ausreichend Rechenlast sorgt. Die hier gezeigte Vorgehensweise würde beim aktiven Suchen nach Primzahlen aufgrund des Verwaltungsoverheads sehr langsam sein, da auch gerade (und somit sicher prime) Zahlen durch einen eigenen Task beackert werden müssten.

[ header = „For“-Schleife, automatisiert ]

„For“-Schleife, automatisiert

Aufgaben sind immer dann gut parallelisierbar, wenn ihre einzelnen Bestandteile nicht voneinander abhängig sind. Ein gutes Beispiel dafür ist das Produzieren eines Schinkenbrötchens: Da die Tomaten auf den Fleischbelag müssen, lässt sich die Zusammenstellung des Einzelbrötchens durch Parallelisierung nicht beschleunigen. Wenn es jedoch um die Fertigung mehrerer Stullen geht, sieht die Lage anders aus: Jedes Brötchen ist von seinen Genossen komplett unabhängig und mehrere Mitarbeiter führen zu einer schnelleren Bereitstellung der Nahrungsmittel.

Ahmdahls Gesetz: Die maximale durch Parallelisierung erreichbare Leistungssteigerung ist durch Ahmdahls Gesetz beschrieben. Es besagt, dass die minimale Laufzeit eines Programms durch die Laufzeit des nicht parallelisierbaren Teils des Codes festgelegt wird.

For-Schleifen sind oftmals geradezu ideale Kandidaten für die Parallelisierung. Die TPL unterstützt dies durch eine spezielle Schleifenart, die sich „selbst“ parallelisiert. Prof. Bläsers Beispiel sieht dann so aus:

#region Parallel Loops public static void ParallelComputeForLoop(long[] inputs) {   long[] outputs = new long[inputs.Length];   Parallel.For(0, inputs.Length, (i) => {       outputs[i] = _Factorize(inputs[i]);   }); }

Parallel.For verlangt zwei Parameter mit Informationen über den zu beackernden Bereich. Der Schritt ist immer mit „eins“ festgelegt – das in C# mögliche Variieren der Schrittweite ist hier nur über Umwege möglich. Die übergebene Payload wird sodann für jeden Zustand einmal aufgerufen.

Im Vergleich zur TaskFactory bestehen hier zwei Unterschiede. Erstens gibt die For()-Methode erst nach dem Abarbeiten des gesamten Zahlenbereichs Werte zurück, zweitens sind Sie für die Verwaltung der Daten zuständig. Dabei genügt es, eine einfache Regel im Hinterkopf zu behalten: Solange jede Schleife nur ihre eigenen Datenfelder berührt und nicht von den Ergebnissen des vorhergehenden Durchlaufs abhängig ist, ist eine Parallelisierung ohne Probleme möglich.

Parallelisierung 101

Nach diesen einführenden Überlegungen wollen wir unser kleines Faktorisierungsbeispiel in der Cloud realisieren. Dazu müssen Sie die Solution um die von der Universität Rapperswil angebotenen DLLs erweitern, die die weiter oben beschriebenen Funktionen realisieren.

Die im Rahmen dieser Bibliotheken ausgelieferte Distribution-Klasse ist von besonderer Bedeutung, da sie als Broker zwischen den Rechenklassen und dem zu verwendenden Cluster agiert. Die Erstellung der (idealerweise global gelagerten) Instanz erfolgt durch den folgenden Aufruf:

Distribution distribution = new Distribution("http://tasks.concurrency.ch", "authorizationtoken");

Hier sind zwei Parameter wichtig. Als Erstes übergeben Sie den URL des anzusprechenden Servers: Wenn Sie ParallelTask nicht selbst hosten, so ist der in den Beispielen vorgegebene Wert der Universität Rapperswil korrekt. Parameter Nummer Zwei enthält einen als Authorization Token bezeichneten Wert – dieser String informiert den Cluster darüber, „wer Einlass begehrt“.

Ab diesem Zeitpunkt können Sie Ihr Programm wie gewohnt aufbauen. Die von Prof. Bläser gerne als Beispiel verwendete Primfaktorzerlegung würde ohne die Aktivierung der Distribution-Klasse so aussehen:

static void MultiFactorize(long[] numberList)  {   . . .    var taskList = new List>();   foreach (var number in numberList)    {     var task = DistributedTask.New(() => Factorize(number));     taskList.Add(task);   }   distribution.Start(taskList);   foreach (var task in taskList)    {     Console.WriteLine(task.Result);   } }

Im Vergleich zum klassischen Aufbau mit AsyncTasks gibt es hier eigentlich nur eine Neuerung: Die auszuführenden Jobs sind in DistributedTask-Instanzen verpackt. Diese werden über die weiter oben besprochene Distribution-Klasse für die Ausführung am Cluster freigegeben – für die Kommunikation ist das Framework selbst verantwortlich.

Die in den Beispielen verwendete Factorize-Methode ist aus numerischer Sicht alles andere als optimal implementiert. Das liegt daran, dass Prof. Bläser aus didaktischen Gründen eine möglichst lange Laufzeit erreichen möchte – wenn diese zu kurz wäre, würden die weiter unten besprochenen Transferzeiten zu stark ins Gewicht fallen.

Eile mit Weile

Nach dem „Lostreten“ eines Tasks stellt sich die Frage, wie Sie als Entwickler über die Fertigstellung informiert werden. Die Await-Funktion verlangt als Parameter ein TaskSet. Nach dem Aufruf von await() wartet ihr Programm, bis alle Tasks erfolgreich durchgerechnet wurden:

distribution.Await(taskSet)

Die Funktion Invoke kombiniert die Ausführung mit einem klassischen Join-Befehl. Das bedeutet, dass das Programm nach dem Aufruf von Invoke die Abarbeitung des Tasks am Cluster abwartet und erst danach weiterläuft:

distribution.Invoke(taskSet)

Microsoft spezifiziert in den Parallelisierungsbibliotheken des .NET Frameworks eine parallelisierte For-Schleife. Diese ist in TaskParallel ebenfalls enthalten. Ihre Verwendung im parallelisierten Zustand wird in folgendem Snippet demonstriert:

public static long DistributedCountPrimes(Distribution distribution, long fromInclusive, long toExclusive) {   long fullRange = Math.Max(0, toExclusive - fromInclusive);   long nofPartitions = Math.Min(256, fullRange);   long partitionSize = (fullRange + nofPartitions - 1) / nofPartitions;   long count = 0;   distribution.ParallelFor(0, nofPartitions, (partition) => {     long innerLower = fromInclusive + partition * partitionSize;     long innerUpper = Math.Min(toExclusive, innerLower + partitionSize);     int innerCount = 0;      . . .     return count;   }

Die Unterschiede zu einer mit der normalen TPL parallelisierten Anwendung fallen hier, wie schon im vorigen Beispiel gesehen, minimal aus. Der wichtigste Unterschied liegt auch hier im Aufruf der ParallelFor-Methode des Distribution-Objekts. Zudem müssen die in der Schleife ausgeführten Tasks diesmal Informationen per Return an das Framework liefern, das diese dann zum Client weiterleitet.

[ header = Braver Task! ]

Braver Task!

Bei der Erstellung der Workloads für ParallelTask müssen Sie als Entwickler einige Beschränkungen auf sich nehmen. Das liegt an zwei Kriterien: Erstens ist es durchaus möglich, dass ein Cluster gleichzeitig die Tasks mehrerer Auftraggeber abarbeitet. Es wäre nicht wünschenswert, wenn sich die Tasks gegenseitig beeinflussen oder ihre Daten auslesen könnten. Zweitens ist das Framework die Arbeit eines Individuums und es ist unmöglich, alle .NET-Funktionen in Alleinarbeit neu zu implementieren.

Das wirkt sich im Besonderen auf die unterstützten Sprachfeatures aus. Polymorphismus durch Interfaces, Vererbungen oder Delegaten wird im Moment nicht unterstützt – wenn Sie diese Sprachelemente im Taskcode verwenden, treten Fehler bei der Taskverteilung auf. Im Bereich der Datenstrukturen müssen Sie auf „Nullables“ und Structs verzichten. Mehrdimensionale Arrays sind der Runtime ebenfalls nicht bekannt, lassen sich aber durch die Verwendung von Nested- oder Jagged-Arrays nachbilden. Das Fehlen von Ref- und Out-Parametern und die Nichtunterstützung von Exceptions fallen eher in die Rubrik „Kleinkram“.

Um Angriffe auf den Cluster zu verhindern, ist die Verwendung von DLLs, Bibliotheken und Inline Assemblys verboten. Das gilt auch für Zugriffe auf das Dateisystem: Ein bösartiger Nutzer könnte das Betriebssystem der Nodes auf diese Art und Weise attackieren.

Interessanterweise erlaubte TaskParallel in Tests des Autors den Zugriff auf das Internet. Sehr lange laufende Tasks könnten auf diese Art und Weise nach außen telefonieren, um Informationen über den Fortschrittsgrad mitzuteilen.

Zu guter Letzt ist es verboten, aus einem Task heraus neue Tasks zu erzeugen. Das bedeutet, dass Sie eine eventuelle Portionierung der Aufgaben am Client erledigen müssen. Ist dies aus irgendwelchen Gründen nicht möglich, können Sie den Berechnungsprozess auch in zwei Stufen aufteilen. Dabei benötigen Sie zwei voneinander unabhängige Transaktionen. Die erste davon hat die Aufgabe, das zu bearbeitende Beispiel in Einzelteile zu zerlegen und die „Trennlinien“ danach an den Client zurückzuliefern. Diese Daten dienen dann im zweiten Schritt der Aufteilung der eigentlichen Nutzlast.

Achtung, Sonderbedingung!

Beim „lokalen Parallelisieren“ gilt (meist), dass mehr Parallelisierung auch zu mehr Rechenleistung führt. Im Fall von TaskParallel ist das nicht unbedingt der Fall: Da die Nodes über eine im Vergleich zu Prozessorbussen immens langsame Netzwerkverbindung angebunden sind, dauert der Austausch von Daten einige Zeit. Im schlimmsten Fall dauert der Transfer der Tasks länger als ihre Abarbeitung auf einem lokalen System – die durch die parallele Ausführung gewonnenen Performancevorteile gehen dann verloren.

Wenn die an ihr Programm gestellten Aufgaben „klein“ sind, stehen zwei verschiedene Ansätze zum Einsatz bereit. Der erste besteht darin, die Tasks mit einer Liste von Jobs auszustatten und diese blockweise abzuarbeiten – auf diese Art erfolgt die Netzwerkkommunikation pro „Jobpaket“ nur einmal.

Als Königsweg erweist sich in vielen Fällen das Generieren der Nutzdaten „am Cluster“. Im Fall einer Primfaktorzerlegung oder eines Brute-Force-Angriffs wäre es sinnvoll, den Task um die Berechnungs-Engine für die Eingaben zu erweitern. Im Fall einer Passwortknackmaschine würde der Task beispielsweise die Aufgabe bekommen, alle Kombinationen von aaa bis ccc abzuarbeiten – dies lässt sich in nur einem (kleinen) Paket erledigen, da die Intelligenz für die Generation ja im Task liegt.

Bei ausreichend komplizierten Aufgaben erreicht der Cluster ein fast linear skalierendes Laufzeitverhalten. Das ist in Abbildungen 3 und 4 gezeigt – sie entstanden durch die Analyse eines Programms, das zehn bekannte Primzahlen durch Faktorisierung untersucht.

Abb. 3: Die Analyse von bekannten Primzahlen skaliert fast linear (Quelle: Prof. Dr. Luc Bläser)

Abb. 4: Dank der hohen Komplexität der Aufgabe ist der für die Koordination benötigte Zeitaufwand klein (Quelle: Prof. Dr. Luc Bläser)

Im Moment erfolgt die Kombination der zurückgelieferten Ergebnisse ausschließlich am Client. Dadurch kann ab einer gewissen Größe der Problemdomäne ein neues Bottleneck entstehen – in der Praxis ist dies bisher allerdings noch nie passiert.

Balanciere mich!

Rechencluster sind nur dann gewinnbringend, wenn sie im aktiven Einsatz stehen. Aus diesem Grund ist die möglichst effiziente Arbeitsverteilung von eminenter Bedeutung: Wäre eines der Pakete wesentlich größer, würde das zu einer asymmetrischen Auslastung führen. Primzahlen sind nicht einheitlich über den Zahlenraum verteilt. Aus diesem Grund kann es vorkommen, dass ein bestimmtes Paket weitaus mehr Primzahlen enthält und somit mehr Rechenleistung erfordert.

Im Moment erlaubt TaskParallel keine Kommunikation zwischen den verschiedenen Tasks. Einmal losgelassene Aufgaben lassen sich mit Bordmitteln auch nicht mehr abbrechen oder nach ihrem Komplettierungsgrad befragen: Die diversen in der Literatur zu findenden adaptiven Lastverteilungsalgorithmen sind hier nicht funktionsfähig.

Als Workaround empfiehlt sich das Aufbrechen der in den Cluster verteilten Arbeitspakete. Dabei soll die Anzahl der Pakete wesentlich größer sein als die Anzahl der an der Verarbeitung des Jobs beteiligten Rechnersysteme. Da die Nodes die anstehenden Pakete nacheinander abarbeiten, ist das Lastverteilungsverhalten in diesem Fall günstiger.

Das lässt sich anhand eines kleinen Gedankenspiels nachvollziehen. Gehen wir einmal davon aus, dass der Zahlenbereich von 0 bis 1 000 zwischen 200 und 300 einige besonders bösartige Aufgaben bereithält. Wenn der Cluster die Pakete in Hunderterschritten einteilt, zieht einer der Nodes den Zonk. Sind die Pakete hingegen nur zehn Zahlen groß, fallen die bösartigen Aufgaben nicht so ins Gewicht. Wenn einer der Cluster einen besonders schwierigen Job zieht, bekommt er bei der nächsten Verteilungsrunde eben nichts zugewiesen.

Die ideale „Kleinheit“ der Pakete ist von der zu bearbeitenden Problemdomäne abhängig. Normalerweise stellen Sie unebene Auslastungen eines Clusters vergleichsweise schnell fest. Ist dies der Fall, sollten Sie die Größe der Pakete reduzieren.

Teste selbst!

Wenn Sie TaskParallel selbst ausprobieren möchten, können Sie dies im kleinen Rahmen auf dem Cluster der Universität Rapperswil tun. Dazu müssen Sie sich im ersten Schritt unter [1] melden und um Zugangsdaten bitten.

Normalerweise reagiert Prof. Bläser sehr rasch auf eingehende Anfragen. Die kostenlos zur Verfügung gestellten Konten erlauben Ihnen die Nutzung von bis zu zwölf Kernen für Evaluationszwecke. Da sich die meisten der Schweizer Universitäten ihre Cluster selbst finanzieren müssen, sollte die kommerzielle Nutzung schon allein aus Anständigkeitsgründen ausgeschlossen sein.

In Vorträgen verweist die FH Rapperswil immer wieder auf Angebote, die neben der Software auch Rechenleistung auf diversen Clustern enthalten. Leider gibt es bisher keine Preislisten, die die Abschätzung des Angebots erlauben.

Fazit

Der TaskParallel-Client ermöglicht Entwicklern das Anzapfen von hochleistungsfähigen Rechenclustern. Dadurch können auch weniger spezialisierte Entwickler skalierbare Applikationen erstellen – die „Demokratisierung“ dieses einst für besondere Spezialisten vorbehaltenen Wissensbereichs ist auf jeden Fall begrüßenswert.

Obwohl das System momentan nur im Zusammenspiel mit einem Windows-Server-Backend funktioniert, ist seine Bedeutung klar erkennbar. Eine Ausweitung auf andere Systeme ist denkbar. Zudem wäre es auch vorstellbar, die in den meisten Unternehmen herumstehenden Workstations der diversen Mitarbeiter so besser auszulasten.

Leider hat die Universität Rapperswil rund ein Jahr nach der Vorstellung des (genialen) Produkts noch keinen konkreten Plan zur Kommerzialisierung präsentiert. Daraus ergibt sich ein nicht unerhebliches Risiko: Wenn die Eidgenossen nicht bald den Massenmarkt erschließen, könnte ein anderes Unternehmen ein ähnliches Produkt anbieten.

Unsere Redaktion empfiehlt:

Relevante Beiträge

Meinungen zu diesem Beitrag

X
- Gib Deinen Standort ein -
- or -