分叉會合模型
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/f/f1/Fork_join.svg/400px-Fork_join.svg.png)
在平行計算中,分叉會合模型是設定和執行並列程式的一種方式,使得程式在指定一點上「分叉」(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]。
參見
參照
- ^ 1.0 1.1 1.2 1.3 1.4 1.5 Michael McCool; James Reinders; Arch Robison. Structured Parallel Programming: Patterns for Efficient Computation (PDF). Elsevier. 2013 [2019-12-03]. (原始內容存檔 (PDF)於2018-11-23).
- ^ Melvin E. Conway. A multiprocessor system design. Fall Join Computer Conference: 139–146. 1963. doi:10.1145/1463822.1463838.
- ^ Nyman, Linus; Laakso, Mikael. Notes on the History of Fork and Join (PDF). IEEE Annals of the History of Computing (IEEE Computer Society). 2016, 38 (3): 84–87 [2019-12-03]. doi:10.1109/MAHC.2016.34. (原始內容存檔 (PDF)於2019-08-28).
- ^ 4.0 4.1 4.2 4.3 Doug Lea. A Java fork/join framework (PDF). ACM Conference on Java. 2000 [2019-12-03]. (原始內容存檔 (PDF)於2019-10-24).
- ^ Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms 3rd. MIT Press and McGraw-Hill. 2009 [1990]. ISBN 0-262-03384-4.
- ^ Blaise Barney. OpenMP. Lawrence Livermore National Laboratory. 12 June 2013 [5 April 2014]. (原始內容存檔於2019-12-18).
- ^ Fork/Join. The Java Tutorials. [5 April 2014]. (原始內容存檔於2019-11-02).
- ^ Daan Leijen; Wolfram Schulte; Sebastian Burckhardt. The design of a Task Parallel Library. OOPSLA. 2009.
外部連結
|
|