在平行計算中，分叉會合模型是設置和執行並列程式的一種方式，使得程式在指定一點上「分叉」（fork）而開始並列執行，在隨後的一點上「會合」（join）並恢復順序執行。並列區段可以遞歸的fork，直到達到特定的任務粒度（granularity）。Fork–join可以被視為是一種並列設計模式[1]:209 ff.，它最早由馬爾文·康威公式化於1963年[2][3]。
概述
通過遞歸的巢狀fork–join計算，可以獲得並列版本的分治範式，表達為如下一般性偽代碼[4]：
解决(问题):
if 问题足够小:
直接解决问题 (顺序算法)
else:
for 部份 in 细分(问题)
fork 子任务来解决(部份)
join 在前面的循环中生成的所有子任务
return 合并的结果
例子
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之後只有一個線程繼續工作[1]:88。
在上述偽碼中第二個遞歸呼叫不是分叉的；這是故意為之的，因為分叉任務是要付出代價的。如果把二個遞歸呼叫都設置為子任務，主任務在被阻塞在join之前將沒有任何額外的工作可以進行[1]。
實現
在fork–join模型的實現中，fork的典型的是任務、纖程即輕量級線程，而非作業系統級別的「重量級」線程或行程，並使用線程池來執行這些任務：fork原語（primitive）允許編程者指定「潛在的」並列，由實現機制接着把它們對映（map）到實際的並列執行之上[1]。這麼設計的原因是建立新線程趨於導致很大的開銷[4]。
在fork–join編程中用到的輕量級線程，典型的有它們自己的排程器，排程器典型的採用工作搶斷策略，並將這些線程對映到底層的線程池。這種排程器比全特徵的搶佔式作業系統排程器要簡單的: 通用的線程排程器必須處理針對鎖的阻塞，而在fork–join範式中，線程只阻塞在join點上[4]。
在OpenMP框架中，Fork–join是主要的並列執行模型，儘管OpenMP實現可以支援也可以不支援並列段落的巢狀[6]。支援它的還有：Java concurrency框架[7]、微軟.NET的任務並列庫[8]和Intel的線程建造塊（TBB）[1]。Cilk程式語言有對fork和join的語言級別支援，其形式為spawn和sync關鍵字[4]或Cilk Plus中的cilk_spawn和cilk_sync[1]。
參見
- 並列編程模型
- Fork (系統呼叫)
- 共用主記憶體並列的矩陣乘法演算法
- 工作搶斷
參照
外部連結
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
