Paralelo de 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 anteriores.

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 varios 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

No debe realizar el manejo de subprocesos manualmente. En su lugar:

• crear un reasonably-sized thread pool executor service (si sus cálculos no hacen IO, utilizar tantos hilos como usted tiene núcleos).
• Ejecute un bucle 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.
• Ejecutar un segundo bucle que recoge los resultados de todos los Future s (se va a esperar de manera implícita hasta que todos los cálculos se han terminado)
• cerrar el servicio ejecutor

Answer 2

No, no debe crear un hilo de 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 conectado a Java, es posible que desee probar un sistema en paralelo paralelo de alto rendimiento como OpenMPI. OpenMPI es adecuado para este tipo de problema.

Answer 3

No cree los hilos usted 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 el cálculo repetido en una matriz. Eso puede funcionar para usted, si los valores que está computando son tipos primitivos.

Answer 4

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

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

Si su cálculo es realmente simple, entonces es probable que desee considerar el procesamiento 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. Lo que quiere ir más alto si están bloqueados a la espera de alguna otra cosa (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; 
}