分叉会合模型

在并行计算中，分叉会合模型是设置和执行并行程序的一种方式，使得程序在指定一点上“分叉”（fork）而开始并行执行，在随后的一点上“会合”（join）并恢复顺序执行。并行区块可以递归的fork，直到达到特定的任务粒度（granularity）。Fork–join可以被视为是一种并行设计模式，它最早由马尔文·康威公式化于1963年。

fork–join范型的示意图，其中程序的三个区块允许各种颜色的块并行执行。顺序执行显示在顶部，等价的fork–join执行在底部。

概述

通过递归的嵌套fork–join计算，可以获得并行版本的分治范型，表达为如下一般性伪代码：

解决(问题):
    if 问题足够小:
        直接解决问题 (顺序算法)
    else:
        for 部份 in 细分(问题)
            fork 子任务来解决(部份)
        join 在前面的循环中生成的所有子任务
        return 合并的结果

例子

简单的并行归并排序是一种fork–join算法：

mergesort(A, lo, hi):
    if lo < hi:                     // 至少有一个输入元素
        mid = ⌊lo + (hi - lo) / 2⌋
        fork mergesort(A, lo, mid)  // 分叉出子任务处理第一个递归调用，它(潜在的) 并行于主任务
        mergesort(A, mid, hi)       // 主任务处理第二个递归调用
        join
        merge(A, lo, mid, hi)

第一个递归调用是“分叉出”的（forked off），这意味着它可以在单独的线程中的执行，从而并行于这个函数的后续部分，直到join导致所有线程同步化。尽管join看起来很像一个屏障（barrier），但二者并不相同，因为各个线程在一个屏障之后将继续工作，而在join之后只有一个线程继续工作。

在上述伪码中第二个递归调用不是分叉的；这是故意为之的，因为分叉任务是要付出代价的。如果把二个递归调用都设置为子任务，主任务在被阻塞在join之前将没有任何额外的工作可以进行。

实现

在fork–join模型的实现中，fork的典型的是任务、纤程即轻量级线程，而非操作系统级别的“重量级”线程或进程，并使用线程池来执行这些任务：fork原语（primitive）允许编程者指定“潜在的”并行，由实现机制接着把它们映射（map）到实际的并行执行之上。这么设计的原因是建立新线程趋于导致很大的开销。

在fork–join编程中用到的轻量级线程，典型的有它们自己的调度器，调度器典型的采用工作抢断策略，并将这些线程映射到底层的线程池。这种调度器比全特征的抢占式操作系统调度器要简单的: 通用的线程调度器必须处理针对锁的阻塞，而在fork–join范型中，线程只阻塞在join点上。

在OpenMP框架中，Fork–join是主要的并行执行模型，尽管OpenMP实现可以支持也可以不支持并行段落的嵌套。支持它的还有：Java concurrency框架、微软.NET的任务并行库和Intel的线程建造块（TBB）。Cilk编程语言有对fork和join的语言级别支持，其形式为spawn和sync关键字或Cilk Plus中的cilk_spawn和cilk_sync。

参见

• 并行编程模型
• Fork (系统调用)
• 共享内存并行的矩阵乘法算法
• 工作抢断

外部链接

• A Primer on Scheduling Fork–Join Parallelism with Work Stealing（页面存档备份，存于互联网档案馆）