I am running following code on a node of a virtual wall. The node has 32 Intel Xeon E7/E5 cores and 128GB of RAM. Monitoring CPU usage shows that the node is far from operating at full strength. This problem differs from most fork-join problems because of the node size. At times the node has 20%+ CPU load on multiple cores, showing signs of parallelism, yet I can't seem to make it use more resources.
To give some context; The problem is a maximisation problem within a graph of 111 nodes (Parcs/parken). A number of eggs are hidden within each park and. That number drops exponentially with every second that passes. The goal is to get as many eggs as possible before the time expires. 'opl' is a solution I found using a greedy algorithm, so to narrow our recursion-tree, I only allow recursions when we've found at most 5 eggs less than our greedy algorithm would've found at the same time.
I'm familiar with (multi-)threading, yet far from an expert. I haven't used many ForkJoinPools before. I have also tried manipulating the ForkJoinPool parameter to 16/32, but without succes.
Main:
Algoritmes.AlgoritmeRecursive.run(new AlgoritmeRecursive(parken, tabel, opl, 22, 1000, 0, 0)));
Class:
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;
}
}
I'm not very familiar with this myself, but could it be that the call to ar.join() will make your RecursiveTask wait until the subtask is done? If this is the case, your other tasks won't start before the previous one finished running.
You could try to store your running tasks in a list, and then join them afterwards. That will hopefully make sure all your subtasks starts running before you wait for them.
Something like this (modifying your second loop in 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;