pp.12.02-ForkJoinArrayReduce

Reduce als divide and conquer

  • Projekt: pp.11.02-ForkJoinArrayReduce
  • Bearbeitungszeit: 29 Minuten
  • Musterlösung: 19 Minuten
  • Kompatibilität: mindestens Java SE 9

 

  • Das Fork-Join Framework eignet sich besonders gut zur Implementierung von Array-Algorithmen.
  • Alle Werte eines Arrays aufaddieren.
  • Das Array soll halbiert werden, bis \(\le\) 4 Elemente übrig sind, wie in folgendem Schaubild:

Hettel und Tran (2016, 191)

Hettel und Tran (2016, 191)
  1. initialisieren (ARRAY_LEN Elemente)
  2. Array halbieren, bis \(\le\) SLICE_LEN Elem.
  3. summieren (Hälften oder \(\le\) SLICE_LEN Elem.)
  • Laufzeituntersuchung:
    • UV: SLICE_LEN, ARRAY_LEN
    • AV: Dauer in ms

Quellcode von pp.ReduceTask

public class ReduceTask {

    private static final int ARRAY_LEN = 16;
    private static final int SLICE_LEN = 4;

    public static void main(String... args) {
        var array = new ArrayList<Integer>();
        for (var i = 0; i < ARRAY_LEN; i++) {
            array.add(i + 1);
        }
        // initialen ReduceTask erzeugen
        // ReduceTask im *Common Thread Pool* starten
        // ReduceTask im *Common Thread Pool* starten
        // auf Ende warten und Summe ausgeben
    }
}

Aufgaben

  • Implementieren Sie die Summierungsfunktion in der Klasse ReduceTask.
  • Führen Sie Messungen der Laufzeit durch.
  • Visualisieren Sie die Ergebnisse und analysiseren Sie das Ergebnis.

Anregung (bei Interesse, Zeit und Gelegenheit)

  • Verallgemeinern Sie ReduceTask für allgemeine Aggregationsfunktionen und Typen (Typ-Parameter für Klasse und Aggregierungsfunktion über FunctionalInterface BiFunction übergeben).
  • Berechnen Sie die optimale Array-Größe für den Rekursionsanker: Da keine (blockierenden) Betriebssystemaufrufe oder synchronisierte Zugriffe auf gemeinsame Variablen erfolgen, die zu einer Blockierung von Threads führen könnte, ist Runtime.getRuntime().availableProcessors()-1 bzw. ForkJoinPool.commonPool().getParallelism() eine sinnvolle Schätzung für die anzustrebende Anzahl von Teilproblemen. SLICE_LEN darf also keine Konstante mehr sein, sondern muss in Abhängigkeit der Konstante `ARRAY_LEN berechnet werden.

Literatur

Hettel, Jörg und Manh Tien Tran. 2016. Nebenläufige Programmierung mit Java. Konzepte und Programmiermodelle für Multicore-Systeme. Heildelberg: dpunkt.verlag.