tutorial - fork join java docs

¿Cómo es mejor el marco fork/join que un grupo de subprocesos?

Question

¿Cuáles son los beneficios de utilizar el nuevo marco fork / join sobre simplemente dividir la gran tarea en N subtareas al principio, enviándolas a un grupo de subprocesos en caché (de los Executors ) y esperando a que se complete cada tarea? No veo cómo el uso de la abstracción fork / join simplifica el problema o hace que la solución sea más eficiente de lo que hemos tenido durante años.

Por ejemplo, el algoritmo de borrosidad paralelizado en el ejemplo tutorial podría implementarse así:

public class Blur implements Runnable {
    private int[] mSource;
    private int mStart;
    private int mLength;
    private int[] mDestination;

    private int mBlurWidth = 15; // Processing window size, should be odd.

    public ForkBlur(int[] src, int start, int length, int[] dst) {
        mSource = src;
        mStart = start;
        mLength = length;
        mDestination = dst;
    }

    public void run() {
        computeDirectly();
    }

    protected void computeDirectly() {
        // As in the example, omitted for brevity
    }
}

Dividir al principio y enviar tareas a un grupo de subprocesos:

// source image pixels are in src
// destination image pixels are in dst
// threadPool is a (cached) thread pool

int maxSize = 100000; // analogous to F-J''s "sThreshold"
List<Future> futures = new ArrayList<Future>();

// Send stuff to thread pool:
for (int i = 0; i < src.length; i+= maxSize) {
    int size = Math.min(maxSize, src.length - i);
    ForkBlur task = new ForkBlur(src, i, size, dst);
    Future f = threadPool.submit(task);
    futures.add(f);
}

// Wait for all sent tasks to complete:
for (Future future : futures) {
    future.get();
}

// Done!

Las tareas van a la cola del grupo de subprocesos, desde donde se ejecutan a medida que los subprocesos de trabajo están disponibles. Siempre que la división sea lo suficientemente granular (para evitar tener que esperar en particular la última tarea) y el grupo de subprocesos tenga suficientes subprocesos (al menos N de procesadores), todos los procesadores están trabajando a toda velocidad hasta que se complete el cálculo.

¿Me estoy perdiendo de algo? ¿Cuál es el valor agregado de usar el armazón fork / join?

Answer 1

Creo que el malentendido básico es que los ejemplos de Fork / Join NO muestran el robo de trabajo sino solo algún tipo de división estándar y conquista.

El robo de trabajo sería así: el trabajador B ha terminado su trabajo. Él es amable, por lo que mira a su alrededor y ve al Trabajador A todavía trabajando muy duro. Él se acerca y pregunta: "Oye muchacho, podría echarte una mano". A respuestas "Genial, tengo esta tarea de 1000 unidades. Hasta ahora he terminado 345 dejando 655. Podrías por favor trabajar en el número 673 a 1000, haré el 346 a 672". B dice "OK, comencemos para que podamos ir al pub más temprano".

Usted ve - los trabajadores deben comunicarse entre sí, incluso cuando comenzaron el trabajo real. Esta es la parte que falta en los ejemplos.

Los ejemplos, por otro lado, muestran algo así como "usar subcontratistas":

Trabajador A: "Dang, tengo 1000 unidades de trabajo. Demasiado para mí. Haré 500 yo mismo y subcontrataré 500 a alguien más". Esto continúa hasta que la gran tarea se divide en pequeños paquetes de 10 unidades cada uno. Estos serán ejecutados por los trabajadores disponibles. Pero si un paquete es una especie de píldora venenosa y tarda mucho más que otros paquetes, mala suerte, la fase de división ha terminado.

La única diferencia restante entre Fork / Join y la división de la tarea por adelantado es la siguiente: cuando se divide por adelantado, tiene la cola de trabajo completa desde el inicio. Ejemplo: 1000 unidades, el umbral es 10, por lo que la cola tiene 100 entradas. Estos paquetes se distribuyen a los miembros del grupo de hilos.

Fork / Join es más complejo e intenta mantener más pequeña la cantidad de paquetes en la cola:

• Paso 1: Ponga un paquete que contenga (1 ... 1000) en cola
• Paso 2: Un trabajador saca el paquete (1 ... 1000) y lo reemplaza con dos paquetes: (1 ... 500) y (501 ... 1000).
• Paso 3: Un trabajador saca el paquete (500 ... 1000) y empuja (500 ... 750) y (751 ... 1000).
• Paso n: La pila contiene estos paquetes: (1..500), (500 ... 750), (750 ... 875) ... (991..1000)
• Paso n + 1: Packet (991..1000) aparece y se ejecuta
• Paso n + 2: el paquete (981..990) aparece y se ejecuta
• Paso n + 3: El paquete (961..980) aparece y se divide en (961 ... 970) y (971..980). ....

Verá: en Fork / Join, la cola es más pequeña (6 en el ejemplo) y las fases "split" y "work" están intercaladas.

Cuando varios trabajadores están apareciendo y presionando simultáneamente, las interacciones no son tan claras por supuesto.

Answer 2

El objetivo final de los grupos de subprocesos y Fork / Join es similar: ambos desean utilizar la potencia de CPU disponible lo mejor que puedan para lograr el máximo rendimiento. El rendimiento máximo significa que se deben completar tantas tareas como sea posible en un largo período de tiempo. ¿Qué se necesita para hacer eso? (Para lo siguiente, supondremos que no hay escasez de tareas de cálculo: siempre hay suficiente para el 100% de utilización de la CPU. Además, uso "CPU" de manera equivalente para núcleos o núcleos virtuales en caso de hiper-threading).

1. Al menos debe haber tantos hilos ejecutándose como CPUs disponibles, ya que al ejecutar menos hilos dejará un núcleo sin usar.
2. Como máximo, debe haber tantos subprocesos ejecutándose como CPUs disponibles, ya que la ejecución de más subprocesos creará una carga adicional para el Programador que asigna CPU a los diferentes subprocesos, lo que hace que parte del tiempo de CPU vaya al planificador en lugar de a nuestra tarea computacional.

Por lo tanto, descubrimos que para un rendimiento máximo necesitamos tener la misma cantidad exacta de hilos que las CPU. En el ejemplo de borrosidad de Oracle, ambos pueden tomar un grupo de subprocesos de tamaño fijo con el número de subprocesos igual al número de CPU disponibles o utilizar un grupo de subprocesos. No hará la diferencia, ¡tienes razón!

Entonces, ¿cuándo te meterás en problemas con un grupo de hilos? Eso es si un hilo bloquea , porque su hilo está esperando que se complete otra tarea. Supongamos el siguiente ejemplo:

class AbcAlgorithm implements Runnable {
    public void run() {
        Future<StepAResult> aFuture = threadPool.submit(new ATask());
        StepBResult bResult = stepB();
        StepAResult aResult = aFuture.get();
        stepC(aResult, bResult);
    }
}

Lo que vemos aquí es un algoritmo que consta de tres pasos A, B y C. A y B se pueden realizar independientemente el uno del otro, pero el paso C necesita el resultado del paso A y B. Lo que este algoritmo hace es enviar la tarea A a el grupo de subprocesos y realizar la tarea b directamente. Después de eso, el hilo esperará a que la tarea A se realice también y continúe con el paso C. Si A y B se completan al mismo tiempo, entonces todo está bien. ¿Pero qué pasa si A lleva más tiempo que B? Esto puede deberse a que la naturaleza de la tarea A lo dicta, pero también puede ser el caso porque no hay ningún hilo para la tarea A disponible al comienzo y la tarea A debe esperar. (Si solo hay una única CPU disponible y, por lo tanto, su subproceso tiene solo un subproceso, esto incluso provocará un interbloqueo, pero por ahora eso es además del punto). El punto es que el hilo que acaba de ejecutar la tarea B bloquea todo el hilo . Como tenemos la misma cantidad de hilos que las CPU y un hilo está bloqueado, eso significa que una CPU está inactiva .

Fork / Join resuelve este problema: en el marco tenedor / unión escribirías el mismo algoritmo de la siguiente manera:

class AbcAlgorithm implements Runnable {
    public void run() {
        ATask aTask = new ATask());
        aTask.fork();
        StepBResult bResult = stepB();
        StepAResult aResult = aTask.join();
        stepC(aResult, bResult);
    }
}

Se ve igual, ¿no? Sin embargo, la clave es que aTask.join no bloqueará . En cambio, aquí es donde entra en juego el robo de trabajo : el hilo buscará otras tareas que hayan sido bifurcadas en el pasado y continuará con ellas. Primero, verifica si las tareas que se ha bifurcado han comenzado a procesarse. Entonces, si A no ha sido iniciado por otro subproceso, lo hará A siguiente, de lo contrario, comprobará la cola de otros hilos y robará su trabajo. Una vez que esta otra tarea de otro hilo haya finalizado, comprobará si A se completa ahora. Si es el algoritmo anterior, puede llamar a stepC . De lo contrario, buscará otra tarea más para robar. Por lo tanto, las agrupaciones fork / join pueden alcanzar el 100% de utilización de la CPU, incluso frente a acciones de bloqueo .

Sin embargo, hay una trampa: el robo de trabajo solo es posible para la llamada de ForkJoinTask de ForkJoinTask s. No se puede hacer para acciones de bloqueo externas como esperar otro hilo o esperar una acción de E / S. Entonces, ¿qué hay de eso, esperar a que I / O complete es una tarea común? En este caso, si pudiéramos agregar un hilo adicional al conjunto Fork / Join que se detendrá nuevamente tan pronto como se complete la acción de bloqueo, será la segunda mejor opción. Y el ForkJoinPool realmente puede hacer eso si estamos usando ManagedBlocker .

Fibonacci

En JavaDoc for RecursiveTask, se encuentra un ejemplo para calcular números de Fibonacci utilizando Fork / Join. Para una solución recursiva clásica ver:

public static int fib(int n) {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

Como se explica en los JavaDocs, esta es una forma bastante aproximada de calcular los números de Fibonacci, ya que este algoritmo tiene complejidad O (2 ^ n), mientras que formas más simples son posibles. Sin embargo, este algoritmo es muy simple y fácil de entender, así que seguimos con él. Supongamos que queremos acelerar esto con Fork / Join. Una implementación ingenua se vería así:

class Fibonacci extends RecursiveTask<Long> {
    private final long n;

    Fibonacci(long n) {
        this.n = n;
    }

    public Long compute() {
        if (n <= 1) {
            return n;
        }
        Fibonacci f1 = new Fibonacci(n - 1);
        f1.fork();
        Fibonacci f2 = new Fibonacci(n - 2);
        return f2.compute() + f1.join();
   }
}

Los pasos en los que se divide esta Tarea son demasiado cortos y, por lo tanto, funcionarán de forma horrible, pero se puede ver cómo el marco generalmente funciona muy bien: los dos sumandos se pueden calcular de forma independiente, pero luego los necesitamos para construir el final resultado. Entonces la mitad está hecha en otro hilo. Diviértete haciendo lo mismo con grupos de hilos sin tener un punto muerto (posible, pero no tan simple).

Solo para completar: si realmente desea calcular los números de Fibonacci utilizando este enfoque recursivo, aquí hay una versión optimizada:

class FibonacciBigSubtasks extends RecursiveTask<Long> {
    private final long n;

    FibonacciBigSubtasks(long n) {
        this.n = n;
    }

    public Long compute() {
        return fib(n);
    }

    private long fib(long n) {
        if (n <= 1) {
            return 1;
        }
        if (n > 10 && getSurplusQueuedTaskCount() < 2) {
            final FibonacciBigSubtasks f1 = new FibonacciBigSubtasks(n - 1);
            final FibonacciBigSubtasks f2 = new FibonacciBigSubtasks(n - 2);
            f1.fork();
            return f2.compute() + f1.join();
        } else {
            return fib(n - 1) + fib(n - 2);
        }
    }
}

Esto mantiene las subtareas mucho más pequeñas porque solo se dividen cuando n > 10 && getSurplusQueuedTaskCount() < 2 es verdadero, lo que significa que hay significativamente más de 100 llamadas a métodos por hacer ( n > 10 ) y ya no hay muchas tareas manuales esperando ( getSurplusQueuedTaskCount() < 2 ).

En mi computadora (4 núcleos (8 al contar Hyper-Threading), Intel (R) Core (TM) CPU i7-2720QM a 2.20GHz) la fib(50) tarda 64 segundos con el enfoque clásico y solo 18 segundos con el Fork / Unir enfoque, que es una ganancia bastante notable, aunque no tanto como teóricamente posible.

Resumen

• Sí, en su ejemplo Fork / Join no tiene ninguna ventaja sobre los clásicos grupos de hilos.
• Fork / Join puede mejorar drásticamente el rendimiento cuando se trata de bloquear
• Fork / Join evita algunos problemas de interbloqueo

Answer 3

En este ejemplo, Fork / Join no agrega ningún valor porque no se necesita bifurcación y la carga de trabajo se divide de manera uniforme en los subprocesos de trabajo. Fork / Join solo agrega sobrecarga.

Aquí hay un h-online.com/developer/features/… sobre el tema. Citar:

En general, podemos decir que el ThreadPoolExecutor es preferible donde la carga de trabajo se divide de manera pareja entre los hilos de trabajo. Para poder garantizar esto, necesita saber exactamente a qué se parecen los datos de entrada. Por el contrario, ForkJoinPool proporciona un buen rendimiento independientemente de los datos de entrada y, por lo tanto, es una solución significativamente más robusta.

Answer 4

F / J también tiene una clara ventaja cuando tiene costosas operaciones de fusión. Debido a que se divide en una estructura de árbol, solo log2 (n) se fusiona en oposición a n se fusiona con la división de hilos lineal. (Esto supone la suposición teórica de que tiene tantos procesadores como hilos, pero sigue siendo una ventaja). Para una tarea de tarea tuvimos que fusionar varios miles de matrices en 2D (todas las mismas dimensiones) al sumar los valores en cada índice. Con fork join y procesadores P, el tiempo se aproxima a log2 (n) cuando P se acerca al infinito.

1 2 3 .. 7 3 1 .... 8 5 4
4 5 6 + 2 4 3 => 6 9 9
7 8 9 .. 1 1 0 .... 8 9 9

Answer 5

Otra diferencia importante parece ser que con FJ, puede realizar múltiples fases complejas de "unión". Considere el tipo de fusión de http://faculty.ycp.edu/~dhovemey/spring2011/cs365/lecture/lecture18.html , se necesitaría demasiada orquestación para dividir previamente este trabajo. Por ejemplo, debe hacer las siguientes cosas:

• ordenar el primer trimestre
• ordenar el segundo trimestre
• fusionar los primeros 2 trimestres
• ordenar el tercer trimestre
• ordenar el cuarto trimestre
• fusionar los últimos 2 trimestres
• fusionar las 2 mitades

¿Cómo se especifica que debe hacer los tipos antes de las fusiones que les concierne, etc.

He estado buscando la mejor manera de hacer una determinada cosa para cada una de una lista de artículos. Creo que voy a dividir previamente la lista y usar un ThreadPool estándar. FJ parece ser más útil cuando el trabajo no se puede dividir previamente en suficientes tareas independientes, pero se puede dividir recursivamente en tareas independientes entre sí (p. Ej. Ordenar las mitades es independiente, pero fusionar las 2 mitades ordenadas en un todo ordenado no lo es).

Answer 6

Se sorprenderá con el rendimiento de ForkJoin en aplicaciones como crawler. aquí está el mejor tutorial que aprenderías.

La lógica de Fork / Join es muy simple: (1) separar (fork) cada tarea grande en tareas más pequeñas; (2) procese cada tarea en un hilo separado (separándolas en tareas incluso más pequeñas si es necesario); (3) únete a los resultados

Answer 7

Si el problema es tal que tenemos que esperar a que se completen otros subprocesos (como en el caso de ordenar matriz o suma de matriz), se debe usar fork join, ya que Executor (Executors.newFixedThreadPool (2)) se ahogará debido a limitaciones Número de hilos. El conjunto forkjoin creará más hilos en este caso para cubrir el hilo bloqueado para mantener el mismo paralelismo

Fuente: http://www.oracle.com/technetwork/articles/java/fork-join-422606.html

El problema con los ejecutores para implementar algoritmos de división y conquista no está relacionado con la creación de subtareas, porque un Callable es libre de enviar una nueva subtarea a su ejecutor y esperar su resultado de forma síncrona o asíncrona. El problema es el del paralelismo: cuando un Callable espera el resultado de otro Callable, se pone en estado de espera, desperdiciando así la oportunidad de manejar otro Callable en cola para la ejecución.

El framework fork / join agregado al paquete java.util.concurrent en Java SE 7 a través de los esfuerzos de Doug Lea llena esa brecha

Fuente: https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ForkJoinPool.html

El conjunto intenta mantener suficientes hilos activos (o disponibles) al agregar, suspender o reanudar dinámicamente los hilos de trabajo internos, incluso si algunas tareas están estancadas esperando unirse a otros. Sin embargo, tales ajustes no están garantizados frente a IO bloqueados u otras sincronizaciones no administradas

public int getPoolSize () Devuelve la cantidad de subprocesos de trabajo que se han iniciado pero aún no se han terminado. El resultado devuelto por este método puede diferir de getParallelism () cuando se crean subprocesos para mantener el paralelismo cuando otros se bloquean de forma cooperativa.

Answer 8

Si tiene n hilos de trabajo activos trabajando al 100% independientemente, eso va a ser mejor que n hilos en un conjunto Fork-Join (FJ). Pero nunca funciona de esa manera.

Es posible que no pueda dividir con precisión el problema en n partes iguales. Incluso si lo hace, la programación de hilos está lejos de ser justa. Terminarás esperando el hilo más lento. Si tiene varias tareas, cada una de ellas puede ejecutarse con un paralelismo menor a n-way (generalmente más eficiente), pero puede subir a n-way cuando hayan terminado otras tareas.

Entonces, ¿por qué no dividimos el problema en pedazos de tamaño FJ y tenemos un grupo de subprocesos trabajando en eso? El uso típico de FJ corta el problema en pedazos pequeños. Hacer esto en orden aleatorio requiere mucha coordinación a nivel de hardware. Los gastos generales serían un asesino. En FJ, las tareas se colocan en una cola que el hilo lee en el orden Último en salir primero (LIFO / pila) y el robo de trabajo (en el trabajo principal, generalmente) se hace Primero en entrar primero en salir (FIFO / "cola"). El resultado es que el procesamiento de matriz larga se puede realizar en gran parte de forma secuencial, aunque se divide en pequeños fragmentos. (También es el caso de que no sea trivial dividir el problema en pequeños trozos de tamaño uniforme en un big bang. Digamos que se trata de una cierta forma de jerarquía sin equilibrar).

Conclusión: FJ permite un uso más eficiente de los hilos de hardware en situaciones desiguales, que será siempre si tiene más de un hilo.

Answer 9

Tenedor / unión es diferente de un grupo de subprocesos porque implementa robo de trabajo. Desde Fork / Join

Al igual que con cualquier ExecutorService, el marco fork / join distribuye tareas a los subprocesos de trabajo en un grupo de subprocesos. El marco fork / join es distinto porque usa un algoritmo de robo de trabajo. Los subprocesos de trabajo que se quedan sin cosas que hacer pueden robar tareas de otros subprocesos que todavía están ocupados.

Digamos que tiene dos hilos y 4 tareas a, b, c, d que toman 1, 1, 5 y 6 segundos respectivamente. Inicialmente, a y b se asignan al subproceso 1 yc y d al subproceso 2. En un grupo de subprocesos, esto llevaría 11 segundos. Con fork / join, el hilo 1 termina y puede robar el trabajo del hilo 2, por lo que la tarea d terminaría siendo ejecutada por el hilo 1. El hilo 1 ejecuta a, by d, el hilo 2 simplemente c. Tiempo total: 8 segundos, no 11.

EDITAR: Como señala Joonas, las tareas no necesariamente se asignan previamente a un hilo. La idea de fork / join es que un hilo puede elegir dividir una tarea en múltiples sub-piezas. Entonces, para reafirmar lo anterior:

Tenemos dos tareas (ab) y (cd) que toman 2 y 11 segundos respectivamente. El hilo 1 comienza a ejecutar ab y lo divide en dos subtareas a & b. De manera similar con el subproceso 2, se divide en dos subtareas cyd. Cuando el hilo 1 ha terminado con a & b, puede robar d del hilo 2.

Answer 10

Todos los de arriba dicen que los beneficios se obtienen mediante el robo de trabajo, pero que amplíen el motivo de esto.

El principal beneficio es la coordinación eficiente entre los hilos de trabajo. El trabajo debe dividirse y volver a armarse, lo que requiere coordinación. Como puede ver en la respuesta de AH, cada hilo tiene su propia lista de trabajo. Una propiedad importante de esta lista es que está ordenada (tareas grandes en la parte superior y tareas pequeñas en la parte inferior). Cada subproceso ejecuta las tareas en la parte inferior de su lista y roba las tareas desde la parte superior de otras listas de hilos.

El resultado de esto es:

• La cabecera y la cola de las listas de tareas se pueden sincronizar de forma independiente, reduciendo la contención en la lista.
• Los subárboles significativos del trabajo se dividen y vuelven a ensamblar por el mismo hilo, por lo que no se requiere coordinación entre hilos para estos subárboles.
• Cuando un hilo roba el trabajo, toma una pieza grande que luego subdivide en su propia lista
• El acero de trabajo significa que los hilos se utilizan casi por completo hasta el final del proceso.

La mayoría de los otros esquemas de división y conquista que utilizan grupos de hilos requieren más comunicación y coordinación entre hilos.