檢視分叉仔會合模型的原始碼

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

==概述==

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

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

==例==

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

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

[[分類: 待校正]]