© best_vector/Shutterstock.com
Teil 2: Möglichkeiten der Parallelprogrammierung mit .NET

Parallel in der Praxis


Nachdem wir im ersten Teil die systemtheoretischen Grundlagen der Parallelprogrammierung umfassend behandelt haben, geht es jetzt um die Programmierpraxis. Als Sprache greifen wir auf C# zurück und stellen Möglichkeiten für Apps und für klassische Applikationen vor. Zuvor zeigen wir jedoch einen Ansatz der Parallelisierung beispielhaft anhand eines Sortierverfahrens. Die daraus resultierenden Erkenntnisse lassen sich in ähnlicher Art und Weise auf eigene Algorithmen übertragen.

Im ersten Teil unserer zweiteiligen Serie zur Parallelverarbeitung haben wir die grundsätzlichen Ebenen der Parallelprogrammierung erörtert. Nachfolgend ein kleiner Rückblick.

Systemtechnische Ebene: Hierbei geht es um die parallele Verarbeitung auf Ebene des Betriebssystems. Die parallele Verarbeitung basiert auf der Arbeit mit Prozessen und Threads.

Anwendungseben: Hier geht es darum, wie auf Ebene des Algorithmus eine bestmögliche Parallelverarbeitung umgesetzt werden kann. Zentrale Frage ist: Welche Teile des Programms sind einer gleichzeitigen Bearbeitung zugänglich?

Programmiertechnische Ebene: Zu guter Letzt geht es um die konkrete Implementierung. Welche Unterstützung kann das Framework bzw. die Programmiersprache bieten?

Punkt eins haben wir ausführlich im ersten Teil behandelt. Damit haben wir die Voraussetzungen für die konkrete Umsetzung geschaffen. Auf Ebene der Anwendung zeigen wir die Möglichkeiten der parallelen Verarbeitung anhand eines Sortieralgorithmus. Datensätze und das Sortieren von Informationen sind im Zeitalter von Big Data und einem permanenten Datenüberfluss eine Hauptaufgabe. Moderne Bibliotheken bieten mehr oder weniger gute Routinen für das Sortieren von Daten an. Im Hintergrund wird dabei auf Standardverfahren wie zum Beispiel den mehrfach in der Praxis bewährten Quicksort-Algorithmus zurückgegriffen. Dieses Standardvorgehen ist in vielen Fällen ausreichend und man muss darüber nicht weiter nachdenken. Bei sehr großen Datenmengen oder wenn es insbesondere auf die Verarbeitungsgeschwindigkeit ankommt, kann man mit paralleler Verarbeitung mehr erreichen. In diesen Fällen ist es in der Regel unerlässlich, dass man das Prinzip des parallelen Sortierens verstanden hat. Der Entwurf eines solchen Algorithmus gestaltet sich dann im Detail gar nicht so schwer. Vielleicht hat man im Endeffekt Glück und es gibt für die Implementierung eine einsatzfähige Bibliothek. Hier sind wir schon am letzten Punkt angelangt, der Ebene der Implementierung. Wir schauen auf die Optionen im .NET Framework und geben einen Überblick über die in den neueren Versionen des Frameworks doch recht zahlreichen Ansatzpunkte zur parallelen Verarbeitung.

Paralleles Sortieren

Sortieralgorithmen sind nur ein Beispiel für eine mögliche parallele Verarbeitung. Ausgangspunkt ist der Algorithmus in seiner Ursprungsform, d. h. für eine sequenzielle Bearbeitung für einen Prozessorkern. In der Betrachtung starten wir stets die nicht parallele Verarbeitung. Den sequenziellen Algorithmus muss man vollständig verstanden haben, um dann die Ansatzpunkte für eine simultane Bearbeitung von Aufgaben zu finden. Wir zeigen das Vorgehen beispielhaft anhand eines Sortierverfahrens. Sortieren ist eine wichtige Aufgabe bei der Bearbeitung von Massendaten. Auf den ersten Blick scheint es tatsächlich gute Ansätze für eine parallele Verarbeitung zu geben, schließlich kann man in der Praxis einen Stapel von Dokumenten auch durch mehrere Personen gleichzeitig sortieren lassen. Man benötigt jedoch eine abgestimmte Strategie und am Ende eine Vorgabe für das sinnvolle Zusammenfügen der Teilergebnisse. Bei der Parallelverarbeitung am Computer ist es nicht anders. Beginnen wir mit dem sequentiellen Quicksort-Algorithmus. Als Regular Sampling wird eine Möglichkeit der Parallelisierung bezeichnet, diesen Ansatz beschreiben wir im Anschluss.

Quicksort

Quicksort ist einer der am häufigsten angewandten Sortieralgorithmen, der im Jahr 1962 von C. A. R. Hoare entwickelt wurde. Wir haben eine Folge von Daten und wissen nicht, wie wir sie sortieren sollen. Wir nehmen an, dass jeder Schlüssel nur einmal auftritt. Ist das nicht der Fall, müssen wir das Verfahren leicht modifizieren, aber das Prinzip bleibt gleich. Erläutert wird das Vorgehen mithilfe von Abbildung 1. Zunächst wählen wir einen beliebigen Schlüssel aus der Folge aus und bezeichnen ihn als Pivot-Element. Hilfsweise haben wir den letzten Wert (hier das Element mit dem Wert 7) als Pivot gewählt. Danach erfolgt die Aufteilung der Daten in zwei Teile: Ein Teil mit Schlüsseln, die kleiner als das Pivot-Element sind, und einen zweiten Teil mit Schlüsseln, die größer als das Pivot-Element sind. Auf die beiden entstehenden Teilfolgen wenden wir das gleiche Vorgehen wiederholend (rekursiv) an. Im letzten Schritt werden die Teilfolgen aneinandergefügt. Listing 1 zeigt den dazugehörigen Quellcode [1].

krypczyk_parallele_1.tif_fmt1.jpgAbb. 1: Ablauf des Quicksort-Algorithmus [1]

Listing 1: Der Quicksort-Algorithmus [1]

Quicksort (int array[], int l, int r { if (l<r) { int pivot = partition (array, l, r, r); if (pivot-l<r-pivot) { quicksort(array, l, pivot...

Neugierig geworden? Wir haben diese Angebote für dich:

Angebote für Gewinner-Teams

Wir bieten Lizenz-Lösungen für Teams jeder Größe: Finden Sie heraus, welche Lösung am besten zu Ihnen passt.

Das Library-Modell:
IP-Zugang

Das Company-Modell:
Domain-Zugang