1

我在虚拟墙的节点上运行以下代码。该节点有 32 个 Intel Xeon E7/E5 内核和 128GB RAM。监控 CPU 使用率表明该节点远未满负荷运行。由于节点大小，此问题与大多数分叉连接问题不同。有时，该节点在多个内核上具有 20% 以上的 CPU 负载，显示出并行性的迹象，但我似乎无法让它使用更多资源。

给出一些背景；该问题是 111 个节点（Parcs/parken）的图中的最大化问题。每个公园内都隐藏着许多鸡蛋。这个数字随着每一秒的过去而呈指数下降。目标是在时间到期之前获得尽可能多的鸡蛋。'opl' 是我使用贪心算法找到的解决方案，因此为了缩小递归树的范围，我只允许在我们发现最多比贪心算法同时发现的鸡蛋少 5 个鸡蛋时进行递归。

我熟悉（多）线程，但远非专家。我以前没有使用过很多 ForkJoinPools。我也尝试将 ForkJoinPool 参数操作为 16/32，但没有成功。

当前核心负载示例

主要的：

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

班级：

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;
    }
}
4

2 回答 2

0

我认为问题在于你的算法的递归部分是这样的：

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

问题是，当你 fork 然后立即加入时，两个或多个子问题没有并行运行的余地。就像您使用经典线程执行此操作一样：

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

这会启动一个新线程，并立即阻塞当前线程，直到新线程完成；即它实际上是单线程的。这样做更有效：

    someRunnable.run();

尝试在一个循环中进行分叉，并在另一个循环中加入。

于 2017-05-02T17:25:21.187 回答
0

我自己对此不是很熟悉，但是是否调用 toar.join()会让您RecursiveTask等到子任务完成？如果是这种情况，您的其他任务将不会在前一个任务完成运行之前开始。

您可以尝试将正在运行的任务存储在列表中，然后再加入它们。这有望确保您的所有子任务在您等待它们之前开始运行。

像这样的东西（修改你的第二个循环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;
于 2017-05-02T17:24:46.760 回答