在并行计算 中，分叉会合 模型是设置和执行并行程序的一种方式，使得程序在指定一点上“分叉”（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编程中用到的轻量级线程，典型的有它们自己的调度器，调度器典型的采用工作抢断 抢占式 操作系统调度器要简单的: 通用的线程调度器 必须处理针对锁 的阻塞，而在fork–join范型中，线程只阻塞在join点上[4]
在OpenMP 框架中，Fork–join是主要的并行执行模型，尽管OpenMP实现可以支持也可以不支持并行段落的嵌套[6] Java concurrency [7] 任务并行库 [8] 线程建造块 [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.
外部链接 A Primer on Scheduling Fork–Join Parallelism with Work Stealing（页面存档备份，存于互联网档案馆 ）
分叉会合模型, 在并行计算中, 是设置和执行并行程序的一种方式, 使得程序在指定一点上, 分叉, fork, 而开始并行执行, 在随后的一点上, 会合, join, 并恢复顺序执行, 并行区段可以递归的fork, 直到达到特定的任务粒度, granularity, fork, join可以被视为是一种并行设计模式, 它最早由马尔文, 康威公式化于1963年, fork, join范型的示意图, 其中程序的三个区段允许各种颜色的块并行执行, 顺序执行显示在顶部, 等价的fork, join执行在底部, 目录, 概述,. 在并行计算中 分叉会合模型是设置和执行并行程序的一种方式 使得程序在指定一点上 分叉 fork 而开始并行执行 在随后的一点上 会合 join 并恢复顺序执行 并行区段可以递归的fork 直到达到特定的任务粒度 granularity Fork join可以被视为是一种并行设计模式 1 209 ff 它最早由马尔文 康威公式化于1963年 2 3 fork join范型的示意图 其中程序的三个区段允许各种颜色的块并行执行 顺序执行显示在顶部 等价的fork join执行在底部 目录 1 概述 2 例子 3 实现 4 参见 5 引用 6 外部链接概述 编辑通过递归的嵌套fork join计算 可以获得并行版本的分治范型 表达为如下一般性伪码 4 解决 问题 if 问题足够小 直接解决问题 顺序算法 else for 部份 in 细分 问题 fork 子任务来解决 部份 join 在前面的循环中生成的所有子任务 return 合并的结果例子 编辑简单的并行归并排序是一种fork join算法 5 mergesort A lo hi if lo lt 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的语言级别支持 其形式为spawn和sync关键字 4 或Cilk Plus中的cilk spawn和cilk sync 1 参见 编辑 电脑程式设计主题 并行编程模型 Fork 系统调用 共享内存并行的矩阵乘法算法 英语 Matrix multiplication algorithm Shared memory parallelism 工作抢断 英语 Work stealing 引用 编辑 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 英语 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 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 外部链接 编辑A Primer on Scheduling Fork Join Parallelism with Work Stealing 页面存档备份 存于互联网档案馆 取自 https zh wikipedia org w index php title 分叉会合模型 amp oldid 69921794, 维基百科，wiki ，书籍，书籍，图书馆，
文章 ，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。