分叉會合模型

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