分叉會合模型

並行計算中,分叉會合模型是設置和執行並行程序的一種方式,使得程序在指定一點上「分叉」(fork)而開始並行執行,在隨後的一點上「會合」(join)並恢復順序執行。並行區段可以遞歸的fork,直到達到特定的任務粒度(granularity)。Fork–join可以被視為是一種並行設計模式[1]:209 ff.,它最早由馬爾文·康威公式化於1963年[2][3]

fork–join范型的示意圖,其中程序的三個區段允許各種顏色的塊並行執行。順序執行顯示在頂部,等價的fork–join執行在底部。

概述

通過遞歸的嵌套fork–join計算,可以獲得並行版本的分治范型,表達為如下一般性偽代碼[4]

解决(问题):
    if 问题足够小:
        直接解决问题 (顺序算法)
    else:
        for 部份 in 细分(问题)
            fork 子任务来解决(部份)
        join 在前面的循环中生成的所有子任务
        return 合并的结果

例子

簡單的並行歸併排序是一種fork–join算法[5]

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編程中用到的輕量級線程,典型的有它們自己的調度器,調度器典型的採用工作搶斷英語Work stealing策略,並將這些線程映射到底層的線程池。這種調度器比全特徵的搶占式操作系統調度器要簡單的: 通用的線程調度器必須處理針對的阻塞,而在fork–join范型中,線程只阻塞在join點上[4]

OpenMP框架中,Fork–join是主要的並行執行模型,儘管OpenMP實現可以支持也可以不支持並行段落的嵌套[6]。支持它的還有:Java concurrency英語Java concurrency框架[7]、微軟.NET的任務並行庫英語Parallel Extensions[8]和Intel的線程建造塊英語Threading Building Blocks(TBB)[1]Cilk編程語言有對fork和join的語言級別支持,其形式為spawnsync關鍵字[4]Cilk Plus中的cilk_spawncilk_sync[1]

參見

引用

  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). 
  2. ^ Melvin E. Conway. A multiprocessor system design. Fall Join Computer Conference: 139–146. 1963. doi:10.1145/1463822.1463838. 
  3. ^ 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. ^ 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). 
  5. ^ Cormen, Thomas H. 英語Thomas H. Cormen; Leiserson, Charles E. 英語Charles E. Leiserson; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms 3rd. MIT Press and McGraw-Hill. 2009 [1990]. ISBN 0-262-03384-4. 
  6. ^ Blaise Barney. OpenMP. Lawrence Livermore National Laboratory. 12 June 2013 [5 April 2014]. (原始內容存檔於2019-12-18). 
  7. ^ Fork/Join. The Java Tutorials. [5 April 2014]. (原始內容存檔於2019-11-02). 
  8. ^ Daan Leijen; Wolfram Schulte; Sebastian Burckhardt. The design of a Task Parallel Library. OOPSLA. 2009. 

外部連結