5 RecursiveAction¶

Proyecto RecursiveAction¶

En este proyecto implementaremos una tarea recursiva que consiste en incrementar en un determinado valor todos los elementos de un array. Si el rango de elementos a incrementar tiene menos de 10 valores, se realizará el incremento de manera secuencial. Si el rango de elementos a incrementar tiene 10 valores o más seguiremos una de las siguientes dos estrategias:

Estrategia 1: Dividir el rango por la mitad y crear dos subtareas cada una de las cuales incremente un subrango aplicando recursivamente el mismo algoritmo anterior.
Estrategia 2: Dividir el rango por la mitad y hacer que el primer subrango sea incrementado secuencialmente y crear una subtarea para el segundo subrango aplicando recursivamente el mismo algoritmo anterior.

MainIncrementTask

import java.util.concurrent.ExecutionException;
import java.util.concurrent.ForkJoinPool;

class Main {

    public static void main(String[] args) throws InterruptedException, ExecutionException {
        new Main().start();
    }

    private void start() throws InterruptedException, ExecutionException {
        int size = 1000;
        int increment = 5;
        int[] values = createArray(size);
        incrementSecuentially(values, increment);
        incrementInParallel(values, increment);
    }

    private void incrementSecuentially(int[] values, int increment) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < values.length; i++) {
            values[i] = values[i] + increment;
        }
        System.out.printf("Secuential increment done in %d millis\n", System.currentTimeMillis() - start);
    }

    private void incrementInParallel(int[] values, int increment) throws InterruptedException, ExecutionException {
        long start = System.currentTimeMillis();
        IncrementTask incrementTask = new IncrementTask(values, 0, values.length, increment);
        ForkJoinPool forkJoinPool = new ForkJoinPool();
        forkJoinPool.execute(incrementTask);
        incrementTask.get();
        System.out.printf("Parallel increment done in %d millis\n", System.currentTimeMillis() - start);
        System.out.printf("Work steal count: %d\n", forkJoinPool.getStealCount());
        forkJoinPool.shutdown();
    }

    private int[] createArray(int size) {
        int[] values = new int[size];
        for (int i = 0; i < size; i++) {
            values[i] = 10;
        }
        return values;
    }

}

import java.time.LocalTime;
import java.time.format.DateTimeFormatter;
import java.util.concurrent.RecursiveAction;

public class IncrementTask extends RecursiveAction {

    private final DateTimeFormatter dateTimeFormatter =
            DateTimeFormatter.ofPattern("HH:mm:ss:SSS");

    private final int[] values;
    private final int from;
    private final int to;
    private final int increment;

    IncrementTask(int[] values, int from, int to,
                int increment) {
        this.values = values;
        this.from = from;
        this.to = to;
        this.increment = increment;
    }

    @Override
    protected void compute() {
        // If range is small enough update directly secuentially.
        if (to - from < 10) {
            incrementValues(values, from, to, increment);
        } else {
            applyStrategy1(values, from, to, increment);
//            applyStrategy2(values, from, to, increment);
        }
    }

    private void applyStrategy1(int[] values, int from, int to, int increment) {
        int pivot = (to + from) / 2;
        System.out.printf("%s - %s - [%d,%d) split in [%d,%d) y [%d,%d)\n",
                Thread.currentThread().getName(),
                dateTimeFormatter.format(LocalTime.now()),
                from, to, from, pivot, pivot, to);
        // Create two subtasks, one for each half.
        IncrementTask subTask1 = new IncrementTask(values, from, pivot, increment);
        IncrementTask subTask2 = new IncrementTask(values, pivot, to, increment);
        // Fork and join them.
        subTask1.fork();
        subTask2.fork();
        subTask1.join();
        subTask2.join();
        System.out.printf("%s - %s - [%d, %d) and [%d, %d) joined. [%d, %d] done\n",
                Thread.currentThread().getName(),
                dateTimeFormatter.format(LocalTime.now()),
                from, pivot, pivot, to, from, to);
    }

    @SuppressWarnings("unused")
    private void applyStrategy2(int[] values, int from, int to, int increment) {
        // Split range in two.
        int pivot = (to + from) / 2;
        System.out.printf("%s - %s - [%d,%d) split in [%d,%d) y [%d,%d)\n",
                Thread.currentThread().getName(),
                dateTimeFormatter.format(LocalTime.now()),
                from, to, from, pivot, pivot, to);
        IncrementTask subTask2 = new IncrementTask(values, pivot, to, increment);
        subTask2.fork();
        incrementValues(values, from, pivot, increment);
        subTask2.join();
        System.out.printf("%s - %s - [%d, %d) and [%d, %d) joined. [%d, %d] done\n",
                Thread.currentThread().getName(),
                dateTimeFormatter.format(LocalTime.now()),
                from, pivot, pivot, to, from, to);
    }

    private void incrementValues(int[] values, int from, int to, int increment) {
        for (int i = from; i < to; i++) {
            values[i] = values[i] * (1 + increment);
        }
        System.out.printf("%s - %s - [%d, %d) done secuentially\n",
                Thread.currentThread().getName(),
                dateTimeFormatter.format(LocalTime.now()),
                from, to);
    }

}