分叉會合模型

在並行計算中，分叉會合模型是設置和執行並行程序的一種方式，使得程序在指定一點上「分叉」（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（頁面存檔備份，存於網際網路檔案館）