2.8 Teile und herrsche mit Fork und Join *

2.8.1 Algorithmendesign per »teile und herrsche«

Eine effektive Problemlösungsstrategie ist es, zunächst das Problem in Teilprobleme zu zerlegen, dann die Teilprobleme zu lösen und anschließend zur Gesamtlösung zu kommen. Wer morgens im Bett liegt und Hunger verspürt, der wird erst dann satt sein, wenn gewisse Teilprobleme gelöst sind. Hierarchisch kann das etwa so aussehen:

Diese Problemlösungsstrategie wird Teile und herrsche (engl. divide and conquer, D&C) genannt. Zunächst wird die Aufgabe ist kleine Häppchen zerlegt und anschließend abgearbeitet.

Teile und herrsche ist nicht nur eine Lösung, wie wir eine große Pizza »verarbeiten«, sondern auch in der Informatik eine beliebte algorithmische Methode: Das Hauptproblem wird in Teilprobleme zerlegt, und dann werden die Teilprobleme gelöst und zur großen Lösung zusammengefügt. Zwei populäre Beispiele sind Sortierungen und die Multiplikation von großen Zahlen.

Sortieren über das Merge-Sort-Verfahren

Der von John von Neumann vorgestellte Algorithmus basiert auf der Idee, die zu sortierende Liste ein zwei Teillisten zu zerlegen, diese dann wiederum in zwei Teile zu zerlegen, diese wiederum usw., bis die Listen so klein sind, dass sie vielleicht nur noch aus zwei Zahlen bestehen, die trivial in eine Reihenfolge zu bringen sind. Ist eine Teilfolge dann sortiert, muss sie mit der sortieren Nachbarfolge zusammenfügt (engl. merge) werden. Während also das Zerlegen und Sortieren von oben nach unten erfolgt, läuft das Zusammenlegen der sortierten Teillisten zur neuen größeren sortierten Teillisten von unten nach oben, bis schließlich die Gesamtliste sortiert ist. Der Algorithmus lässt sich sehr gut rekursiv implementieren. Auch das bekannte Quicksort arbeitet ähnlich. (Hier geht es allerdings darum, ein sogenanntes Pivot-Element zu wählen, dann die Liste in zwei Teillisten aufzuspalten, wobei in die erste Liste (erst einmal unsortiert) die Elemente kleiner dem Pivot-Element verschoben werden und in die andere Liste die Elemente größer dem Pivot-Element. Die Auswahl eines neuen Pivot-Elements und das Kopieren in den richtigen Bereich wird rekursiv für die Unterbereiche wiederholt, was natürlich zu einer Sortierung führt. In der Regel kommt Quicksort mit weniger Speicher aus und ist in der Praxis schneller, da Merge-Sort in der einfachen Implementierung immer neue Teillisten aufbauen muss und Quicksort die Vertauschoperationen auf der originalen Datenstruktur (also in-place) ausführen kann.

Multiplikation von großen Ganzzahlen

In Java ist das Multiplizieren von Ganzahlen einfach. Sind die Zahlen klein genug, erledigt der *-Operator die Aufgabe, sind sie größer, helfen die Klasse BigInteger und die Methode multiply(). Das sind natürlich hübsche Abstraktionen, aber im Java-Bytecode gibt es für die Multiplikation von int und long lediglich imul und lmul,[11](http://java.sun.com/docs/books/jvms/second_edition/html/Mnemonics.doc.html) und alles andere, etwa die Multiplikation von großen Zahlen für RSA-Schlüssel, müssen wir anders lösen.

Das Produkt von großen Zahlen lässt sich einfach mit ein paar Additionen auf das Produkt von kleineren Zahlen abbilden. Anstatt Zahlen mit Hunderten von Stellen zu nehmen, nutzen wir ein einfacheres Beispiel, das das Prinzip zeigt. Nehmen wir dazu die Zahl A = 1234, die mit B = 5678 multipliziert werden soll. Dann ist AB = (12 · 10^2 + 34) · (56 · 10^2 + 78) = 12 · 56 · 10^4 + (12 · 78 + 34 · 56) · 10^2 + 34 · 78. Waren bei 1234 und 5678 die Zahlen noch vierstellig, sind sie bei der Umschreibung nur noch zweistellig. Zählen wir die Anzahl der Multiplikationen – und lassen wir die einfachen Multiplikation mit 10^4 bzw. 10^2 beiseite –, so kommen wir auf vier, denn wir müssen 12 · 56, 12 · 78, 34 · 56 und 34 · 78 ausführen. Bei einem rekursiven D&C-Algorithmus ist also das Problem zur Multiplikation von 1234 · 5678 auf die vier Multiplikationen und Additionen abgeschwächt worden. Das können wir dann auch weiter aufspalten, bis wir bei einstelligen Zahlen sind.

Stehen wir also vor der Aufgabe, beliebig große Zahlen mit n Stellen zur multiplizieren, können wir das auf eine Multiplikation von Zahlen der Größe n/2 und ein paar Additionen abbilden. Kommen wir noch zu einer kleinen Optimierung. Wenn Zahlen sehr groß werden und dann multipliziert werden müssen (etwa zu Schlüsselgenerierung) ist es wichtig, jede überflüssige Operation wegzulassen, da arithmetische Operationen dann bei großen Zahlen und häufiger Durchführung doch ihre Zeit brauchen. Interessanterweise kann durch geschickte Umstellung die Anzahl der Multiplikationen von 4 auf 3 gesenkt werden. Zwei der Multiplikationen aus 12 · 56 · 10^4 + (12 · 78 + 34 · 56) · 10^2 + 34 · 78 stammen aus dem Teil 12 · 78 + 34 · 56. Hier können wir etwas umschreiben, denn 12 · 78 + 34 · 56 = (12 + 34) · (56 + 78) – 12 · 56 – 34 · 78. Obwohl das auf den ersten Blick schlimmer aussieht (drei Multiplikationen statt zwei), fällt bei einem zweiten Blick auf, dass wir die beiden Produkte 12 · 56 und 34 · 78 schon im ersten Schritt berechnet haben. Also ergibt sich letztendlich 12 · 56 · 10^4 + ((12 + 34) · (56 + 78) – 12 · 56 – 34 · 78) · 10^2 + 34 · 78, und das macht insgesamt drei Multiplikationen für den Preis von ein paar zusätzlichen Subtraktionen, die im Allgemeinen billiger sind als die Multiplikationen, die bei dem D&C-Ansatz ja recht aufwändig sind.

Die Arbeitsweise von D&C-Algorithmen sieht im Pseudocode wie folgt aus:

löse Problem:
  ist Problem klein:
    löse Problem direkt
  andernfalls:
    zerlege das Problem in Teilprobleme
    löse die Teilprobleme
    setze Problemlösung aus den Teillösungen zusammen

Attraktiv sind D&C-Algorithmen dann, wenn die Teilprobleme unabhängig voneinander und parallel gelöst werden können.

Bei unserem Eingangsbeispiel mit dem Aufstehen und Essen gibt es eine Abhängigkeit, sodass zwei beide Teilprozesse zwar eine Teilaufgabe des Gesamtproblems lösen, man aber ohne aufzustehen nicht zum Kühlschrank kommt. Das Sortieren über Merge-Sort erfüllt dabei das Kriterium, dass wenn die Liste in zwei Unterlisten zerlegt wird, die beiden Unterlisten problemlos parallel sortiert werden können.

2.8.2 Paralleles Lösen von D&C-Algorithmen

Die Abarbeitung von Teilproblemen durch Threads ergibt immer dann Sinn, wenn

• durch die Kommunikation mit externen Subsystemen einzelne Threads den Prozessor immer wieder durch Wartezeiten nicht vollständig ausnutzen oder
• Threads effektiv parallel auf mehreren Prozessoren oder Cores laufen.

Kommen wir kurz zum Pseudo-Code vom D&C-Algorithmus zurück. Die Parallelisierung ist an einer Stelle:

löse Problem:
  ist Problem klein:
    löse Problem direkt
  andernfalls:
    zerlege das Problem in Teilprobleme
    löse die Teilprobleme parallel
    warte auf die Fertigstellung
    setze Problemlösung aus den Teillösungen zusammen

Die Teilprobleme könnten parallel gelöst werden, und es muss keine Rekursion stattfinden.

Mit den Standardmitteln von Java 1.0 könnten wir eine parallele D&C-Lösung prinzipiell implementieren. Wir bauen mit new Thread() einen Thread auf, geben die zu lösende Aufgabe als Runnable mit, starten mit start() den Thread und warten anschließend mit join() auf das Ende. Anschließend bringen wir die Ergebnisse zusammen.

Ein genauer Blick auf diese Lösung zeigt ein zentrales Problem auf: Es werden viele Threads benötigt. Nehmen wir eine Problemgröße von n an. Im ersten Schritt werden zwei Threads benötigt, die jeweils die Probleme der Größe n/2 und n/2 lösen. Für diese würden wieder Threads benötigt, diesmal 4, die dann die Problemgrößen n/4, n/4, n/4 und n/4 lösen. Da sich die Problemgröße immer halbiert, ergibt sich ein Binärbaum der Tiefe log2n. Die Anzahl der Threads ist 2 + 4 + 8 + 16 + ... + 2^log2ⁿ = n, also abhängig von der Problemgröße und in der Größenordnung O(n). Wir könnten nun argumentieren, dass Problem mit den Thread-Pool abzumildern, aber im Grunde werden immer noch zu viele Threads benötigt. Und wenn am Anfang durch die erste Teilung für die Problemgröße n/2 zwei Threads erzeugt werden, was machen sie? Zunächst nichts als warten. Sie warten auf die Berechnung der aufgespannten Threads, die die zwei n/4-Lösung liefern. Diese warten wiederum bis zum Boden, bis die Lösung wirklich so klein ist, dass sie direkt berechnet werden kann. Erst dann läuft das Ergebnis wieder nach oben, und Schritt für Schritt beendet das die oberen wartenden Threads.

Im Grunde warten die Threads mehr, als sie arbeiten. Daher bringt auch ein Thread-Pool keine unglaubliche Verbesserung, denn wartende Threads können vom Thread-Pool nicht für andere Aufgaben herangezogen werden, sondern der Thread-Pool muss neue Threads aufbauen. Wenn wir dann fordern, dass der Thread-Pool nur so groß ist wie die Anzahl an Prozessoren (etwa 2), dann ist klar, dass wir sofort in einer Sackgasse stecken würden. Traditionelle Thread-Pools helfen bei der Lösung von parallelen D&C-Ansätzen so einfach nicht.

2.8.3 Fork und Join

Gesucht ist ein Framework zum Lösen von parallelen D&C-Algorithmen, die berechnungsintensiv sind. Oracle hat in Java 7 das Framework Fork/Join integriert, was im Rahmen von jsr166y (http://gee.cs.oswego.edu/dl/concurrency-interest/) unter maßgeblicher Arbeit von Doug Lea entwickelt wurde. Die grundlegende Idee ist, neben Threads noch eine andere Arbeitseinheit einzuführen, die Tasks.

• Threads: Werden vom Betriebssystem verwaltet und laufen entweder pseudo-parallel auf einem Prozessor/Core oder echt parallel. Threads können sich mit anderen Threads koordinieren. Zu viele Threads, die sich im Weg stehen und aufeinander warten, führen zu keiner verbesserten Ausführungszeit gegenüber einer sequenziellen Lösung.
• Tasks: Werden von Threads bzw. einem Thread-Pool ausgeführt. Sie sind Arbeitseinheiten, die nicht auf andere Tasks warten.

Die Tasks sind kleine Arbeitspakete und werden in eine Task-Queue gelegt und dann von Threads abgearbeitet. Hat das System zwei Prozessoren und hat der Thread-Pool die Größe 2, so ist es wahrscheinlich, dass 2 Tasks parallel abgearbeitet werden. Gibt es 4 Prozessoren, können 4 Tasks vielleicht parallel laufen. Tasks lassen sich also grundsätzlich auf einer beliebige Anzahl von Threads und somit Prozessoren/Cores bringen, wobei im Gegensatz die Effektivität von Threads immer mit der physikalischen Anzahl von Prozessoren/Cores assoziiert ist.

Das Fork/Join-Framework aus dem java.util.concurrent-Paket löst die Probleme effektiv. Wie der Name schon andeutet, geht es bei Fork um das Erstellen eines neuen Tasks und bei Join um das Zusammenführen der Ergebnisse. Die Fork/Join-Bibliothek stellt dazu die Klasse ForkJoinPool als Koordinator zur Verfügung und als Task-Beschreibung den Typ ForkJoinTask. Von der abstrakten Basisklasse ForkJoinTask gibt es bisher zwei Unterklassen: RecursiveAction (Tasks ohne Ergebnisse) und RecursiveTask (Tasks mit Ergebnissen). Die zentralen Methoden sind fork() und join().

Zur Abarbeitung der Tasks stellt das Framework die Threads zur Verfügung, deren Anzahl wir zwar für die Lösung des Problems selbst bestimmen können, aber die Anzahl der Prozessoren/Cores ist eine gute Standardgröße.[12](Dass die Maximalanzahl von Threads beim ForkJoinPool zurzeit 32767 ist, dürfte für normale Nutzer keine Einschränkung sein.) Die Methode fork() erzeugt einen neuen Task, der an den Anfang (!) einer Queue gestellt wird. Dabei haben alle Threads eine Queue für ihre Arbeitsaufträge, und sollte einmal eine Queue leergelaufen sein, so nimmt sich der Thread einfach einen Task vom Ende (!) einer anderen nicht-leeren Queue. (Das nennt sich work-stealing und ist im wahren Leben ziemlich selten anzutreffen.) Dass neue Tasks an den Anfang gestellt werden, ist einfach zu erklären: Die Tasks werden ja immer kleiner, und somit stehen die kleinen, schnell lösbaren Aufgaben vorne. Erst später folgen die größeren Aufgaben, die auf die Ergebnisse der kleinen Aufgaben zurückgreifen, die dann logischerweise schon berechnet wurden.

Zur Theorie ein Beispiel: Es geht darum, mit Fork/Join ein Programm zu haben, das parallel das Maximum eines Arrays sucht. Der Start ist:

Listing 2.37: com/tutego/insel/thread/concurrent/ForkJoinPoolDemo,java, main()

int[] array = { 0, 9, 10, 111, 1, 12, 13, 14, 17 };
System.out.println( MaxElementInArrayFinder.findMax( array ) );

Die eigene Klasse MaxElementInArrayFinder bietet die Methode findMax(), die auf den ForkJoinPool zurückgreift, um mit invoke() den Haupt-Task abzusetzen.

Listing 2.38: com/tutego/insel/thread/concurrent/ForkJoinPoolDemo,java, MaxElementInArrayFinder

class MaxElementInArrayFinder
{
  private static final ForkJoinPool fjPool = new ForkJoinPool();
  ...
  public static int findMax( int[] array )
  {
    return fjPool.invoke( new MaxElemTask( array, 0, array.length –1 ) );
  }
}

Unsere Klasse MaxElemTask repräsentiert ein Arbeitspakt. Das Objekt referenziert jeweils das Array sowie die Anfangs-/Endeposition, ab der sie nach dem Maximum suchen sollen.

Listing 2.39: com/tutego/insel/thread/concurrent/ForkJoinPoolDemo,java, MaxElementInArrayFinder.MaxElemTask

private static class MaxElemTask extends RecursiveTask<Integer>
{
  private final int[] array;
  private final int start, end;

  MaxElemTask( int[] array, int start, int end )
  {
    assert array != null && start >= 0 && start <= end;

    this.array = array;
    this.start = start;
    this.end = end;
  }

  @Override protected Integer compute()
  {
    ...
  }
}

Unsere Klasse erweitert die Basisklasse RecursiveTask<Integer> und deutet durch den generischen Typ schon an, dass das Ergebnis des Tasks eine Ganzzahl sein wird, nämlich das Feldmaximum aus dem gewünschten Bereich. Der Konstruktor sichert die Werte, und compute() führt die eigentliche Arbeit aus: Es löst entweder das Problem direkt, wenn es klein genug ist, oder spannt Unter-Tasks auf und wartet anschließend auf deren Ergebnisse.

Listing 2.40: com/tutego/insel/thread/concurrent/ForkJoinPoolDemo,java, MaxElementInArrayFinder.MaxElemTask.compute()

@Override protected Integer compute()
{
  assert array != null && array.length > 0;

  System.out.printf( "max( start=%d, end=%d )%n", start, end );

  if ( end – start < 4 )
  {
    int max = array[start];
    for ( int i = start + 1; i <= end; i++ )
      if ( array[i] > max )
        max = array[i];

    return max;
  }

  int middle = (start + end) / 2;

  MaxElemTask leftTask = new MaxElemTask( array, start, middle );
  leftTask.fork();

  MaxElemTask rightTask = new MaxElemTask( array, middle + 1, end );

  int rightMax = rightTask.compute();
  int leftMax = leftTask.join();

  return Math.max( rightMax, leftMax );
}

Ihr Kommentar

Wie hat Ihnen das <openbook> gefallen? Wir freuen uns immer über Ihre freundlichen und kritischen Rückmeldungen.