Java ForkJoinPool n'utilise pas tous les cœurs de processeur

Question

Je cours le code suivant sur un nœud d'un mur virtuel. Le nœud dispose de 32 cœurs Intel Xeon E7/E5 et de 128 Go de RAM. La surveillance de l'utilisation du processeur montre que le noeud est loin de fonctionner à pleine puissance. Ce problème diffère de la plupart des problèmes de jointure à la fourche en raison de la taille du nœud. Parfois, le nœud a une charge de processeur de plus de 20% sur plusieurs cœurs, montrant des signes de parallélisme, mais je n'arrive pas à le faire utiliser plus de ressources.

Pour donner du contexte; Le problème est un problème de maximisation dans un graphe de 111 nœuds (Parcs/parken). Un certain nombre d'oeufs sont cachés dans chaque parc et. Ce nombre chute de façon exponentielle à chaque seconde qui passe. L'objectif est d'obtenir autant d'œufs que possible avant l'expiration du délai. 'opl' est une solution que j'ai trouvée en utilisant un algorithme glouton, donc pour restreindre notre récursion-tree, j'autorise seulement les récursions quand on a trouvé au plus 5 oeufs de moins que notre algorithme glouton aurait trouvé en même temps. Je connais le (multi-) threading, mais loin d'être un expert. Je n'ai pas utilisé beaucoup de ForkJoinPools auparavant. J'ai également essayé de manipuler le paramètre ForkJoinPool à 16/32, mais sans succès.

Example of current core-load

principal:

Algoritmes.AlgoritmeRecursive.run(new AlgoritmeRecursive(parken, tabel, opl, 22, 1000, 0, 0))); 

Classe:

public static class AlgoritmeRecursive extends RecursiveTask<Double> { 
    private ArrayList<Park> parken = new ArrayList<Park>(); 
    private double[][] afstandenTabel; 
    private double[][] oplossing; 
    private int startpark; 
    private double duur; 
    private double eieren; 
    private int time; 

    AlgoritmeRecursive(ArrayList<Park> parken, double[][] afstandenTabel, double[][] oplossing, int startpark, double duur, double eieren, int time) { 
     for (Park p : parken) { 
      this.parken.add(new Park(p)); 
     } 
     this.afstandenTabel = afstandenTabel; 
     this.oplossing = oplossing; 
     this.startpark = startpark; 
     this.duur = duur; 
     this.eieren = eieren; 
     this.time = time; 
    } 

    public static double run(AlgoritmeRecursive ar) { 
     ForkJoinPool pool= new ForkJoinPool(); 
     return pool.invoke(ar); 
    } 

    protected Double compute() { 
     if (duur < 1.0) return eieren; 

     double gevonden = 0; 

     /* startpark zoeken adhv gegeven naam */ 
     for (Park p : parken) { 
      if (p.getId() == startpark) { 
       gevonden = p.verwachtAantalEieren(40, 0); 
       p.updateEggs(p.getEggs() * exp((-1.0/10800.0) * ((p.getStartEggs()/20.0) + 40.0))); 
      } 
      else { 
       p.updateEggs(p.getEggs() * exp((-1.0/10800.0) * (p.getStartEggs()/20.0))); 
      } 
     } 
     double score = eieren; 
     for (Park p : parken) { 
      if (p.getId() == startpark && eieren >= (oplossing[1000-(int)duur][1] - 5)) { 
       AlgoritmeRecursive ar = new AlgoritmeRecursive(parken, afstandenTabel, oplossing, startpark, duur-1, eieren + gevonden, time+1); 
       ar.fork(); 
       double res = ar.join(); 
       if(res > score) score = res; 
      } 
      else if (duur-afstandenTabel[startpark][p.getId()] > 60.0 && time > 120.0 && eieren >= oplossing[1000-(int)duur][1] && gevonden < p.verwachtAantalEieren(40,afstandenTabel[startpark][p.getId()])){ 
       AlgoritmeRecursive ar = new AlgoritmeRecursive(parken, afstandenTabel, oplossing, p.getId(), duur-afstandenTabel[startpark][p.getId()], eieren, 0); 
       for (Park p2 : ar.parken) { 
        p2.updateEggs(p2.getEggs() * exp((-1.0/10800.0) * (p2.getStartEggs()/20.0) * (afstandenTabel[startpark][p.getId()]-1))); 
       } 
       ar.fork(); 
       double res = ar.join(); 
       if(res > score) score = res; 
      } 
     } 
     return score; 
    } 
    public double exp(double x) { 
      x = 1d + x/256d; 
      x *= x; x *= x; x *= x; x *= x; 
      x *= x; x *= x; x *= x; x *= x; 
      return x; 
    } 
} 

Answer 1

Je ne suis pas très familier avec moi-même, mais pourrait-il que l'appel à ar.join() fera votre RecursiveTask attendre jusqu'à ce que la sous-tâche soit terminée? Si c'est le cas, vos autres tâches ne démarreront pas avant la fin de la précédente.

Vous pouvez essayer de stocker vos tâches en cours dans une liste, puis de les joindre ultérieurement. Nous espérons que toutes vos sous-tâches commenceront à être exécutées avant que vous les attendiez.

Quelque chose comme ceci (modifier votre deuxième boucle compute):

List<AlgoritmeRecursive> tasks = new ArrayList<>(); 

for (Park p : parken) { 
    if (p.getId() == startpark && eieren >= (oplossing[1000-(int)duur][1] - 5)) { 

     AlgoritmeRecursive ar = new AlgoritmeRecursive(parken, afstandenTabel, oplossing, startpark, duur-1, eieren + gevonden, time+1); 
     ar.fork(); 
     tasks.add(ar); // Adding the running task to the list. 

    } else if (duur-afstandenTabel[startpark][p.getId()] > 60.0 && time > 120.0 && eieren >= oplossing[1000-(int)duur][1] && gevonden < p.verwachtAantalEieren(40,afstandenTabel[startpark][p.getId()])){ 

     AlgoritmeRecursive ar = new AlgoritmeRecursive(parken, afstandenTabel, oplossing, p.getId(), duur-afstandenTabel[startpark][p.getId()], eieren, 0); 
     for (Park p2 : ar.parken) { 
      p2.updateEggs(p2.getEggs() * exp((-1.0/10800.0) * (p2.getStartEggs()/20.0) * (afstandenTabel[startpark][p.getId()]-1))); 
     } 
     ar.fork(); 
     tasks.add(ar); // Adding the running task to the list. 

    } 
} 

double score = eieren; 
for(AlgoritmeRecursive task : tasks) { 
    double res = ar.join(); 
    if(res > score) score = res; 
} 

return score; 

Answer 2

Je pense que le problème est que la partie récursive de votre algorithme est comme ceci:

for (...) { 
     // ar <- create sub-problem 
     ar.fork(); 
     double res = ar.join(); 
     // Use result 
    } 

Le problème est-ce que lorsque vous vous cassez puis que vous vous joignez immédiatement, il n'y a pas de possibilité pour deux ou plusieurs sous-problèmes de fonctionner en parallèle. Il est le même que si vous l'avez fait avec des fils classiques:

Thread t = new Thread(someRunnable); 
    t.start(); 
    t.join(); 

qui démarre un nouveau thread, et bloque immédiatement le thread courant jusqu'à ce que le nouveau se termine; c'est-à-dire effectivement à un seul thread. Il est plus efficace de le faire:

someRunnable.run(); 

Essayez de faire la bifurcation dans une boucle, et la jonction dans l'autre.