分叉仔會合模型

佇平行計算中，分叉會合模型是設定佮執行並列程式的一種方式，使得程式咧指定一點仔上「分叉」（fork）煞開始並列執行，綴尾仔一點上「會合」（join）並且恢復順序執行。並列區段會當遞迴的 fork，一直到達到特定的任務粒度（granularity）。 Fork–join 會當予人看做是一種並列設計模式，伊上早是由馬爾文 ・ 康威公式化佇一九六三年。

概述

通過交迴的岫狀 fork–join 計算，會當得著並列版本的分治範式，表達為了一般性虛擬碼：

` ` ` 解影響 ( 鋪排 ): if鋪排誠奢颺 : 直接刣枋枋 ( 鋪排算法 ) else: for部份in鋪分 ( 鋪排 ) fork子任石樵解影響 ( 部份 ) join佇頭前的循中生成的所有子任施 return合影響的穆果 ` ` `

例

簡單的並列合併排序是一種 fork–join 演算法：

` ` ` mergesort ( A , lo , hi ) : iflo < hi : / / 至少有一個擴入元素 mid=⌊lo + ( hi-lo ) / 二 ⌋ forkmergesort ( 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