分叉/联接框架如何比线程池更好?

2022-08-31 07:44:09

与在开始时简单地将大任务拆分为N个子任务,将它们发送到缓存的线程池(来自执行器)并等待每个任务完成相比,使用新的fork/join框架有什么好处?我看不出使用fork/join抽象如何简化问题,或者使解决方案比我们多年来一直拥有的更有效。

例如,教程示例中的并行模糊算法可以按如下方式实现:

public class Blur implements Runnable {
    private int[] mSource;
    private int mStart;
    private int mLength;
    private int[] mDestination;

    private int mBlurWidth = 15; // Processing window size, should be odd.

    public ForkBlur(int[] src, int start, int length, int[] dst) {
        mSource = src;
        mStart = start;
        mLength = length;
        mDestination = dst;
    }

    public void run() {
        computeDirectly();
    }

    protected void computeDirectly() {
        // As in the example, omitted for brevity
    }
}

在开始时拆分并将任务发送到线程池:

// source image pixels are in src
// destination image pixels are in dst
// threadPool is a (cached) thread pool

int maxSize = 100000; // analogous to F-J's "sThreshold"
List<Future> futures = new ArrayList<Future>();

// Send stuff to thread pool:
for (int i = 0; i < src.length; i+= maxSize) {
    int size = Math.min(maxSize, src.length - i);
    ForkBlur task = new ForkBlur(src, i, size, dst);
    Future f = threadPool.submit(task);
    futures.add(f);
}

// Wait for all sent tasks to complete:
for (Future future : futures) {
    future.get();
}

// Done!

这些任务将转到线程池的队列,当工作线程变为可用时,将从该队列中执行这些任务。只要拆分足够精细(以避免特别等待最后一个任务),并且线程池具有足够(至少N个处理器)线程,所有处理器都在全速工作,直到整个计算完成。

我错过了什么吗?使用分叉/连接框架的附加价值是什么?


答案 1

我认为基本的误解是,Fork/Join的例子并没有显示工作偷窃,而只是某种标准的分而治之。

偷工是这样的:工人B已经完成了他的工作。他是一个善良的人,所以他环顾四周,看到工人A仍然非常努力地工作。他走过来问:“嘿,小伙子,我可以帮你一把。答:“很酷,我有1000个单位的任务。到目前为止,我已经完成了345个,剩下655个。你能不能在673到1000号上工作,我会做346到672。B说:“好吧,让我们开始吧,这样我们就可以早点去酒吧了。

你看 - 工人必须相互沟通,即使他们开始了真正的工作。这是示例中缺少的部分。

另一方面,示例仅显示类似“使用分包商”的内容:

工人A:“当,我有1000个单位的工作。对我来说太多了。我会自己做500个,把500个分包给别人。这种情况一直持续到大任务被分解成每个10个单元的小包。这些将由可用的工作人员执行。但是,如果一包是一种毒丸,并且比其他包花费更长的时间 - 运气不好,那么分裂阶段就结束了。

Fork/Join 和预先拆分任务之间唯一剩下的区别是:预先拆分时,工作队列从一开始就已满。示例:1000 个单位,阈值为 10,因此队列有 100 个条目。这些数据包将分发到线程池成员。

分叉/加入更复杂,并尝试将队列中的数据包数量保持在较小级别:

  • 步骤 1:将一个包含 (1...1000) 的数据包放入队列
  • 步骤 2:一个工作线程弹出数据包 (1...1000) 并将其替换为两个数据包:(1...500) 和 (501...1000)。
  • 步骤 3:一个工作线程弹出数据包 (500...1000) 并推送 (500...750) 和 (751...1000)。
  • 步骤 n:堆栈包含以下数据包:(1..500)、(500...750)、(750...875)...(991..1000)
  • 步骤 n+1:弹出并执行数据包 (991..1000)
  • 步骤 n+2:弹出并执行数据包 (981..990)
  • 步骤 n+3:弹出数据包 (961..980) 并将其拆分为 (961...970) 和 (971..980)。....

你可以看到:在Fork/Join中,队列更小(示例中为6),并且“拆分”和“工作”阶段是交错的。

当多个工人同时弹出和推动时,交互当然不是那么清晰。


答案 2

如果有 n 个繁忙的线程全部以 100% 独立方式工作,则这比分叉连接 (FJ) 池中的 n 个线程要好。但它永远不会以这种方式工作。

可能无法将问题精确地拆分为 n 个相等的片段。即使你这样做了,线程调度也离公平还有一段路要走。您最终会等待最慢的线程。如果您有多个任务,那么它们都可以以少于n路的并行度(通常更有效)运行,但是当其他任务完成时,它们可以上升到n路。

那么,我们为什么不把问题切成FJ大小的部分,并让一个线程池来处理这个问题。典型的FJ用法将问题切成小块。以随机顺序执行这些操作需要在硬件级别进行大量协调。开销将是一个杀手。在 FJ 中,任务被放入线程以“最后先出”顺序(LIFO/堆栈)读取的队列中,而工作窃取(通常在核心工作中)由“先进先出”(FIFO/“队列”)完成。结果是,长数组处理可以在很大程度上按顺序完成,即使它被分解成小块。(同样的情况是,在一次大爆炸中将问题分解成均匀大小的小块可能并非微不足道。假设处理某种形式的层次结构而不平衡。

结论:FJ允许在不均衡的情况下更有效地使用硬件线程,如果您有多个线程,这将始终如此。


推荐