repetir - sentencias repetitivas en java

Paralelizar un bucle for

Question

Tengo un bucle for donde el cálculo en la iteración i no depende de los cálculos realizados en las iteraciones previas.

Quiero paralelizar el bucle for (mi código está en java) para que el cálculo de múltiples iteraciones se pueda ejecutar simultáneamente en múltiples procesadores. ¿Debo crear un hilo para el cálculo de cada iteración, es decir, el número de hilos que se crearán es igual al número de iteraciones (el número de iteraciones es grande en el ciclo for)? ¿Como hacer esto?

Answer 1

Aquí hay un pequeño ejemplo que puede ser útil para comenzar con la paralelización. Se supone que:

1. Usted crea un objeto de Input que contiene la entrada para cada iteración de su cálculo.
2. Usted crea un objeto de Output que contiene el resultado de calcular la entrada de cada iteración.
3. Desea pasar una lista de entradas y obtener una lista de resultados de una vez.
4. Su aportación es una tarea razonable que hacer, por lo que la sobrecarga no es demasiado alta.

Si su cálculo es realmente simple, entonces probablemente quiera considerar procesarlos en lotes. Usted puede hacer eso poniendo decir 100 en cada entrada. Utiliza tantos hilos como procesadores hay en su sistema. Si está trabajando con tareas puramente intensivas en la CPU, probablemente sea el número que desee. Te gustaría ir más alto si están bloqueados esperando algo más (disco, red, base de datos, etc.)

public List<Output> processInputs(List<Input> inputs)
        throws InterruptedException, ExecutionException {

    int threads = Runtime.getRuntime().availableProcessors();
    ExecutorService service = Executors.newFixedThreadPool(threads);

    List<Future<Output>> futures = new ArrayList<Future<Output>>();
    for (final Input input : inputs) {
        Callable<Output> callable = new Callable<Output>() {
            public Output call() throws Exception {
                Output output = new Output();
                // process your input here and compute the output
                return output;
            }
        };
        futures.add(service.submit(callable));
    }

    service.shutdown();

    List<Output> outputs = new ArrayList<Output>();
    for (Future<Output> future : futures) {
        outputs.add(future.get());
    }
    return outputs;
}

Answer 2

No crees los hilos tú mismo. Recomiendo que use el marco fork / join (jsr166y) y cree tareas que iteren sobre un rango determinado de elementos. Se ocupará de la gestión de subprocesos por usted, utilizando tantos subprocesos como sea compatible con el hardware.

La granularidad de la tarea es el problema principal aquí. Si cada iteración tiene un cálculo relativamente bajo (digamos, menos de 100 operaciones), el hecho de que cada iteración se ejecute como una tarea separada introducirá una gran cantidad de sobrecarga en la programación de tareas. Es mejor que cada tarea acepte una Lista de argumentos para calcular y devolver el resultado como una lista. De esta forma, puede hacer que cada tarea calcule 1, 10 o miles de elementos para mantener la granularidad de la tarea a un nivel razonable que equilibre mantener disponible el trabajo y reducir la sobrecarga de administración de tareas.

También hay una clase ParallelArray en jsr166z, que permite cálculos repetidos en una matriz. Eso puede funcionar para usted, si los valores que está computando son tipos primitivos.

Answer 3

No debe hacer el manejo de subprocesos manualmente. En lugar:

• cree un servicio de ejecutor de grupo de subprocesos de tamaño razonable (si sus cálculos no hacen IO, use tantos subprocesos como núcleos tenga).
• Ejecute un ciclo que envíe cada cálculo individual al servicio del ejecutor y conserve los objetos Future resultantes. Tenga en cuenta que si cada cómputo consiste de solo una pequeña cantidad de trabajo, esto generará una gran sobrecarga y posiblemente incluso sea más lento que un programa de subproceso único. En ese caso, envíe trabajos que realicen paquetes de computación como lo sugiere mdma.
• Ejecute un segundo ciclo que recoja los resultados de todos los Future s (esperará implícitamente hasta que todos los cálculos hayan finalizado)
• cerrar el servicio ejecutor

Answer 4

No, no deberías crear un hilo para cada iteración. La cantidad óptima de subprocesos está relacionada con la cantidad de procesadores disponibles: demasiados subprocesos, y pierde demasiada conmutación de contexto de tiempo para que no se obtenga un rendimiento adicional.

Si no está totalmente apegado a Java, es posible que desee probar un sistema C paralelo de alto rendimiento como OpenMPI. OpenMPI es adecuado para este tipo de problema.