Paralléliser une boucle for

Question

J'ai une boucle for où le calcul à l'itération i ne dépend pas des calculs effectués dans les itérations précédentes.

Je veux paralléliser la boucle for (mon code est en java) afin que le calcul de plusieurs itérations puisse être exécuté simultanément sur plusieurs processeurs. Dois-je créer un thread pour le calcul de chaque itération, c'est-à-dire que le nombre de threads à créer est égal au nombre d'itérations (le nombre d'itérations est grand dans la boucle for)? Comment faire ça?

Answer 1

Vous ne devez pas effectuer la gestion des threads manuellement. Au lieu de cela:

• créer un reasonably-sized thread pool executor service (si vos calculs ne pas IO, utiliser autant de threads que vous avez des noyaux).
• Exécutez une boucle qui soumet chaque calcul individuel au service d'exécution et conserve les objets Future résultants. Notez que si chaque calcul consiste seulement en une petite quantité de travail, cela va créer beaucoup de surcharge et peut-être même être plus lent qu'un programme mono-thread. Dans ce cas, soumettez des travaux qui font des paquets de calcul comme le suggère mdma.
• Exécuter une deuxième boucle qui collecte les résultats de tous les Future s (il implicitement attendre jusqu'à ce que tous les calculs ont terminé)
• fermé le service exécuteur

Answer 2

Non, vous ne devez pas créer un thread chaque itération. Le nombre optimal de threads est lié au nombre de processeurs disponibles - trop de threads, et vous perdez trop de temps à changer de contexte sans aucune amélioration des performances.

Si vous n'êtes pas totalement attaché à Java, vous pouvez essayer un système C parallèle hautes performances comme OpenMPI. OpenMPI est adapté à ce genre de problème.

Answer 3

Ne créez pas les unités vous-même. Je vous recommande d'utiliser le framework fork/join (jsr166y) et de créer des tâches qui parcourent une gamme donnée d'éléments. Il prendra soin de la gestion des threads pour vous, en utilisant autant de threads que les supports matériels.

La granularité de la tâche est le problème principal ici. Si chaque itération est un calcul relativement faible (disons moins de 100 opérations), alors l'exécution de chaque itération comme une tâche distincte introduira beaucoup de temps supplémentaires dans l'ordonnancement des tâches. Il est préférable que chaque tâche accepte une liste d'arguments à calculer et renvoie le résultat sous forme de liste. De cette façon, vous pouvez faire en sorte que chaque tâche calcule 1, 10 ou des milliers d'éléments, pour maintenir le volume de tâches à un niveau raisonnable qui équilibre la disponibilité du travail et réduire les frais généraux de gestion des tâches.

Il existe également une classe ParallelArray dans jsr166z, qui permet des calculs répétés sur un tableau. Cela peut fonctionner pour vous, si les valeurs que vous calculez sont des types primitifs.

Answer 4

Voici un petit exemple que vous pourriez trouver utile pour commencer la parallélisation. Il suppose que:

1. Vous créez un objet Input qui contient l'entrée pour chaque itération de votre calcul.
2. Vous créez un objet Output qui contient la sortie du calcul de l'entrée de chaque itération.
3. Vous souhaitez transmettre une liste d'entrées et récupérer une liste de sorties en une fois.
4. Votre entrée est un morceau de travail raisonnable à faire, de sorte que les frais généraux ne sont pas trop élevés.

Si votre calcul est vraiment simple, vous voudrez probablement envisager de les traiter par lots. Vous pourriez le faire en mettant dis 100 dans chaque entrée. Il utilise autant de threads que de processeurs dans votre système. Si vous avez affaire à des tâches intensives purement CPU, c'est probablement le nombre que vous voulez. Vous voudriez aller plus haut s'ils sont bloqués en attente de quelque chose d'autre (disque, réseau, base de données, 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; 
}