分叉会合模型

并行计算中,分叉会合模型是设置和执行并行程序的一种方式,使得程序在指定一点上“分叉”(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. 

外部链接