El paralelismo en Java y el framework Fork/Join

0
25878

El paralelismo en Java y el framework Fork/Join

En este tutorial veremos qué es el paralelismo y cómo podemos implantarlo en nuestras aplicaciones Java.

0. Índice de contenidos

1. Introducción

A la hora de desarrollar un programa con un coste computacional elevado, programar de una forma óptima y eficiente no es suficiente. Los ordenadores que utilizamos actualmente, incluso muchos de los sistemas móviles, disponen de privilegiados recursos hardware que en muy pocas ocasiones son aprovechados como se merecen.

Java proporciona soporte para la implementación y la ejecución de tareas en paralelo, pero por defecto las aplicaciones desarrolladas en este lenguaje serán ejecutadas de forma secuencial. En este tutorial aprenderemos alguna de las técnicas que el lenguaje pone a nuestra disposición para el desarrollo de aplicaciones con tareas concurrentes o en paralelo. También diferenciaremos dos conceptos distintos, paralelismo y concurrencia, basados ambos en la programación multitarea.

Por último paralelizaremos una tarea sencilla, tomando como ejemplo para este tutorial el algoritmo de ordenación MergeSort. Tomaremos tiempos de ejecución antes y después de la paralelización, comparándolos y sacando finalmente algunas conclusiones.

2. Entorno

Este tutorial está escrito desde una máquina con las siguientes características:

  • Hardware: MacBook Pro 15' (2,5 GHz Intel Core i7, 8 GB DDR3)
  • Sistema Operativo: Mac OS Yosemite 10.10.2
  • Entorno de desarrollo: Eclipse Luna 4.4.0
  • JDK 1.8

3. Qué es el paralelismo

Paralelismo es la ejecución simultánea de dos o más tareas. Se considera una propiedad del hardware, ya que requiere recursos físicos para ejecutar cada tarea simultáneamente, y su objetivo se basa en realizar una tarea en el menor tiempo posible.

El paralelismo acelera la ejecución de una tarea dividiéndola en computaciones independientes y ejecutándola sobre hardware capaz de realizar computaciones simultáneas, como por ejemplo un procesador con varios núcleos. Pero cuando ejecutamos una tarea paralelizada en múltiples ordenadores, en vez de en los múltiples cores de un solo ordenador, decimos que la computación paralela es distribuída. Por ejemplo, cada búsqueda en Google se ejecuta simultáneamente en cientos de ordenadores, cada uno de los cuales busca al mismo tiempo en un subconjunto del índice del web.

Paralelismo NO es concurrencia

El término paralelismo suele confundirse en numerosas ocasiones con el concepto de concurrencia. Ambos se basan en la programación multitarea, pero no son lo mismo.

Mientras que el paralelismo es la ejecución simultánea de dos o más tareas, la concurrencia es la ejecución de dos o más tareas en periodos de tiempo solapados, pero no necesariamente simultáneos. La concurrencia, por tanto, es una propiedad del programa. Su computación debe dividirse en tareas independientes, cuya ejecución puede o no solaparse. Puede existir sin soporte hardware multitarea, por ejemplo, los sistemas operativos multitarea ejecutados en máquinas con un procesador de un solo núcleo asignan breves intervalos de tiempo a cada tarea, dando la ilusión de ejecución simultánea.

Frente a la computación paralela, la programación concurrente enfatiza más la interacción entre tareas, centrándose en coordinar el acceso a recursos mutables compartidos mediante algoritmos que evitan la interferencia entre tareas y la inconsistencia de los recursos.

4. El framework Fork/Join

El framework Fork/Join está disponible en la versión 7 de Java. Fue diseñado para la ejecución de tareas que pueden dividirse en otras subtareas más pequeñas, ejecutándose estas en paralelo y combinando posteriormente sus resultados para obtener el resultado de la tarea única. Las subtareas deberán ser independientes unas de otras, y no contendrán estado.

Este framework realiza la paralelización de tareas de forma recursiva, aplicando el principio Divide y Vencerás. Existirá un umbral bajo el cual una tarea será indivisible, definido por el tamaño de la misma. Una vez el tamaño de las subtareas llegue al umbral, el rendimiento de las mismas disminuirá en caso de seguir dividiéndolas.

A continuación podemos ver el pseudocódigo:

Result solve (Problem problem) {
    if problem.size < SEQUENTIAL_THRESHOLD
        return solveSequentially(problem);
    else {
        Result left, right;
        INVOKE-IN-PARALLEL {
            left = solve(extractLeftHalf(problem));
            right = solve(extractRightHalf(problem));
        }
        return combine(left, right);
    }
}

Fork/Join se encuentra en la librería java.util.concurrent. Esta librería contiene una serie de interfaces y clases con las que poder implantar concurrencia o paralelismo en nuestros desarrollos. Entre otros mecanismos, encontramos los semáforos, los tipos atómicos, las barreras o los cerrojos.

La implementación de Fork/Join toma forma a través de las clases ForkJoinTask y ForkJoinPool. La clase ForkJoinPool invoca a una tarea de tipo ForkJoinTask pero, para poder invocar múltiples subtareas en paralelo de forma recursiva, invocará a una tarea de tipo RecursiveAction, que extiende de ForkJoinTask.

La clase RecursiveAction contiene el método compute(), que será el encargado de ejecutar nuestra tarea paralelizable. Para paralelizar una tarea secuencial, por tanto, crearemos una clase que extienda de RecursiveAction, y sobrecargaremos el método compute() con dicha tarea. Además, existe una diferencia entre el código de la tarea secuencial y el código que contenga el método compute(); mientras la tarea secuencial consiste en un método que se llame a sí mismo de forma recursiva, el método compute() creará de forma recursiva nuevas instancias de su misma clase, correspondiendo cada nueva instancia a una subtarea distinta.

En la siguiente sección veremos un ejemplo de paralelización, haciendo uso de este framework.

5. Paralelizando tareas: MergeSort como ejemplo

Un buen ejemplo de tarea divisible en subtareas a través de la estrategia Divide y Vencerás es la ordenación de una lista de números enteros, en concreto la ordenación mediante el algoritmo MergeSort. En este algoritmo la ordenación de una lista no depende del resto, lo cual es un requisito fundamental para poder paralelizar cualquier tarea mediante el framework Fork/Join.

A continuación tenemos el pseudocódigo del algoritmo. Como podremos ver, se ordena cada sublista recursivamente aplicando el ordenamiento por mezcla (function mergesort), y posteriormente se mezclan las dos sublistas en una sola lista ordenada (function merge).

function mergesort(a)
    var left as array = a[0] ... a[n/2]
    var right as array = a[n/2+1] ... a[n]
    left = mergesort(left)
    right = mergesort(right)
    return merge(left, right)
end function

function merge(left,right)
    var result as array
    while length(left) > 0 and length(right) > 0 
        if first(left) ≤ first(right)
            append first(left) to result
            left = rest(left)
        else
            append first(right) to result
            right = rest(right)
    if length(left) > 0 
        append rest(left) to result
    if length(right) > 0 
        append rest(right) to result
    return result
end function

Al paralelizar cualquier operación sobre una colección de elementos debemos tener en cuenta tanto el tamaño de la misma como el coste de la operación, ya que si la lista es demasiado pequeña o el coste computacional es bajo la paralelización perjudicará en el rendimiento, sobrepasando el tiempo de gestión de los recursos del sistema junto con la ejecución de la tarea en cada hilo al tiempo secuencial.

En Java la comparación de dos números es bastante rápida, por lo que para obtener mejoras en la paralelización de MergeSort podemos aplicar el algoritmo en una lista considerablemente grande o añadir cierto coste computacional a la operación de la comparación. Como solución, vamos a añadir un pequeño retardo de 100 ms. a la operación de comparación.

Vamos a ver un ejemplo de cómo se paralelizaría la implementación secuencial del algoritmo mediante el framework Fork/Join, enfrentando después los tiempos de ejecución en serie y en paralelo.

5.1. De implementación serie a paralela

Nuestra implementación del algoritmo MergeSort consta de tres partes:

  • El método mergesort(), que ordena cada sublista recursivamente aplicando el ordenamiento por mezcla.
  • El método merge(), que mezcla dos sublistas ordenadas en una lista, ordenada también.
  • El método sort(), que invoca una sola vez al método mergesort(), creando previamente un array auxiliar del mismo tamaño que la lista a ordenar.

Esta implementación, cuya ejecución se realiza de manera secuencial, se muestra a continuación:

public class MergeSort {
    public void sort(Integer[] a) {
        Integer[] helper = new Integer[a.length];
        mergesort(a, helper, 0, a.length - 1);
    }

    private void mergesort(Integer[] a, Integer[] helper, int lo, int hi) {
        if (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            mergesort(a, helper, lo, mid);
            mergesort(a, helper, mid + 1, hi);
            merge(a, helper, lo, mid, hi);
        } else {
            return;
        }
    }

    private void merge(Integer[] a, Integer[] helper, int lo, int mid, int hi) {
        /* code */
    }
}

El código del método merge() será el mismo para la implementación en serie que para la implementación en paralelo, y su lógica se encuentra en el pseudocódigo del algoritmo. Es en este método donde podemos introducir el retardo de 100 ms.

Fork/Join está pensado para la ejecución de tareas que pueden dividirse en otras subtareas más pequeñas. Por esta razón, la tarea que vamos a paralelizar es el método mergesort(). Vamos a crear una clase que extienda de RecursiveAction, llamándola por ejemplo MergeSortTask, y en cuyo método compute() se implemente el código de nuestro antiguo método mergesort(). Además, en vez de realizar dos llamadas recursivas al método mergesort(), se crearán dos nuevas instancias de la clase MergeSortTask de manera recursiva, invocándolas posteriormente.

Para finalizar nuestra paralelización, en el método sort() declarado fuera de la clase MergeSortTask crearemos un objeto de la clase ForkJoinPool, el cual invocará una instancia de la clase MergeSortTask. Por defecto, ForkJoinPool se instancia con el número de procesadores libres en el sistema, pero podemos indicar en el constructor el nivel de paralelismo deseado. A continuación se muestra el código de MergeSort paralelizado.

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

public class MergeSortForkJoin {
    public void sort(Integer[] a) {
        Integer[] helper = new Integer[a.length];
        ForkJoinPool forkJoinPool = new ForkJoinPool();
        forkJoinPool.invoke(new MergeSortTask (a, helper, 0, a.length-1));
    }

    private class MergeSortTask extends RecursiveAction{
        private static final long serialVersionUID = -749935388568367268L;
        private final Integer[] a;
        private final Integer[] helper;
        private final int lo;
        private final int hi;

        public MergeSortTask(Integer[] a, Integer[] helper, int lo, int hi){
            this.a = a;
            this.helper = helper;
            this.lo = lo;
            this.hi = hi;
        }

        @Override
        protected void compute() {
            if (lo < hi) {
                int mid = lo + (hi-lo)/2;
                MergeSortTask left = new MergeSortTask (a, helper, lo, mid);
                MergeSortTask right = new MergeSortTask (a, helper, mid+1, hi);
                invokeAll(left, right);
                merge(this.a, this.helper, this.lo, mid, this.hi);
            } else {
                return;
            }
        }

        private void merge(Integer[] a, Integer[] helper, int lo, int mid, int hi) {
            /* code */
        }
    }
}

5.2. Pruebas y rendimiento

Para comparar ambas implementaciones y verificar que el tiempo de ejecución de una tarea disminuye cuando ésta se ha paralelizado, hemos realizado distintas pruebas tomando en cada una de ellas tanto el tiempo de ejecución como el número de hilos activos. Estas pruebas han consistido en la ordenación de colecciones de distintos tamaños, siendo las colecciones una generación de números enteros aleatorios entre -100.000 y 100.000, y ordenándose cada colección siempre primero en secuencial y después en paralelo.

Hemos clasificado las pruebas realizadas en dos grupos: colecciones grandes y colecciones pequeñas. El objetivo de nuestras pruebas será comprobar que la paralelización disminuye el tiempo de ejecución en la ordenación de colecciones grandes o en la resolución de problemas con alto coste computacional, pero que perjudica en la ordenación de listas pequeñas o en la resolución de problemas con bajo coste.

Colecciones grandes

Para las pruebas de colecciones grandes se han fijado cuatro tamaños para las colecciones a ordenar: 50, 100, 250 y 500 elementos. Para cada tamaño se han generado tres listas, ordenando cada una mediante MergeSort secuencial y posteriormente ordenando cada una a través de MergeSort paralelizado.

Estos tamaños, en condiciones normales, pueden considerarse pequeños, pero añadiendo un retardo de 100 ms. a cada comparación de números enteros el coste computacional se eleva considerablemente. Tras cada ordenación, se ha tomado el tiempo de ejecución y se ha calculado el rendimiento del algoritmo mediante la aceleración y la eficiencia. Los resultados obtenidos han sido los siguientes:

50 elementos:

Lista 1 Lista 2 Lista 3
Tiempo serie (ms) 29870 29859 29865
Tiempo paralelo (ms) 11370 11388 11388
Hilos activos 9 9 9
Aceleración 2,6271 2,6219 2,6225
Eficiencia (%) 29,19 29,13 29,14

100 elementos:

Lista 1 Lista 2 Lista 3
Tiempo serie (ms) 70200 70184 70179
Tiempo paralelo (ms) 24762 25076 24762
Hilos activos 9 9 9
Aceleración 2,8349 2,7988 2,8341
Eficiencia (%) 31,49 31,09 31,49

250 elementos:

Lista 1 Lista 2 Lista 3
Tiempo serie (ms) 208286 208268 208230
Tiempo paralelo (ms) 68139 67881 67857
Hilos activos 9 9 9
Aceleración 3,0568 3,0681 3,0687
Eficiencia (%) 33,96 34,09 34,10

500 elementos:

Lista 1 Lista 2 Lista 3
Tiempo serie (ms) 468772 466874 465133
Tiempo paralelo (ms) 147800 140998 138694
Hilos activos 9 9 9
Aceleración 3,1717 3,3112 3,3537
Eficiencia (%) 35,24 36,79 37,26

Efectivamente, podemos comprobar que el tiempo de ejecución disminuye al paralelizar el algoritmo. Y no solo eso, también observamos que cuanto mayor sea la lista, mayor es el rendimiento.

Colecciones pequeñas

Para este tipo de pruebas se han generado colecciones de los siguientes tamaños: 10, 5, 3 y 2 elementos. El número de pruebas ha sido el mismo, siguiéndose la misma dinámica que para las pruebas de colecciones grandes. Vamos a ver los resultados obtenidos en cuanto a tiempo y rendimiento:

10 elementos:

Lista 1 Lista 2 Lista 3
Tiempo serie (ms) 3548 3548 3543
Tiempo paralelo (ms) 2088 2089 2089
Hilos activos 9 9 9
Aceleración 1,6992 1,6984 1,6960

5 elementos:

Lista 1 Lista 2 Lista 3
Tiempo serie (ms) 1253 1254 1251
Tiempo paralelo (ms) 1043 1044 1045
Hilos activos 8 5 8
Aceleración 1,2013 1,2011 1,1971

3 elementos:

Lista 1 Lista 2 Lista 3
Tiempo serie (ms) 512 517 518
Tiempo paralelo (ms) 528 529 522
Hilos activos 5 5 5
Aceleración 0,9697 0,9773 0,9923

2 elementos:

Lista 1 Lista 2 Lista 3
Tiempo serie (ms) 206 204 202
Tiempo paralelo (ms) 214 216 212
Hilos activos 3 3 3
Aceleración 0,9626 0,9444 0,9528

Existe cierta aceleración en el caso de las listas de tamaño 10 y 5, aunque si tenemos en cuenta el número de hilos activos la aceleración es insignificante. Para las colecciones de tamaños 3 y 2 el tiempo de ejecución paralelo pasa a ser mayor que el tiempo de ejecución secuencial, por lo que aquí descubrimos que a partir de cierto umbral la paralelización perjudica en el rendimiento.

6. Referencias

7. Conclusiones

Como hemos podido comprobar, la paralelización de una tarea es una buena solución para reducir su tiempo de ejecución, siempre y cuando ésta sea divisible en subtareas independientes y nuestro sistema hardware nos lo permita. Gracias al framework Fork/Join podremos paralelizar de forma sencilla cualquier tarea, siempre y cuando se cumplan las condiciones necesarias, aunque no siempre mejoraremos el tiempo de ejecución serie. Aplicar el paralelismo sobre una tarea que trabaje con colecciones pequeñas o ejecute cualquier operación con un coste computacional mínimo puede perjudicar en el rendimiento, como hemos aprendido en este turorial.

Espero que este tutorial os haya ayudado. Un saludo.

Natalia

nroales@autentia.com

DEJA UNA RESPUESTA

Por favor ingrese su comentario!

He leído y acepto la política de privacidad

Por favor ingrese su nombre aquí

Información básica acerca de la protección de datos

  • Responsable:
  • Finalidad:
  • Legitimación:
  • Destinatarios:
  • Derechos:
  • Más información: Puedes ampliar información acerca de la protección de datos en el siguiente enlace:política de privacidad