摘要
本文描述了一个支持并行编程风格的Java框架的设计、实现和性能，该框架通过(递归)将问题分解为并行解决的子任务，等待它们完成，然后组合结果。总体设计是Cilk提出的工作-窃取框架的一个变体。主要的实现技术围绕任务队列和工作线程的高效构造和管理。测试的性能表明，大多数程序都具有良好的并行速度，但同时也提出了可能的改进措施。
1. 介绍
Fork/join并行是获得良好并行性能的最简单、最有效的设计技术之一。Fork/join算法是我们熟悉的分而治之算法的并行版本，典型的形式如下：
Result solve(Problem problem) {
if (problem is small)
directly solve problem
else {
split problem into independent parts
fork new subtasks to solve each part
join all subtasks
compose result from subresults
}
}
fork操作启动一个新的并行的fork/join子任务。join操作会使得当前的任务不会继续处理直到forked的子任务完成。Fork/join算法，像其他分而治之算法一样，几乎总是递归的，重复拆分子任务，直到它们小到足以使用简单的、简短的串行方法来解决为止。
2. 设计
可以使用任何支持并行执行子任务的构造的框架以及等待它们完成的机制来运行fork/join程序。然而，java.lang.Thread类(也就是POSIX pthreds, Java线程通常基于的线程)不是最佳的支持fork/join程序的工具：
- fork/join任务具有简单和规律的同步和管理要求。比起需要通用线程，fork/join任务生成的计算图表允许更有效的调度策略。例如，fork/join任务永远不需要阻塞除了等待子任务。因此跟踪阻塞的通用线程所带来的开销和记录就是浪费的。
- 给定合理的基本任务粒度，构建和管理线程的成本可能大于任务本身的计算时间。虽然粒度可以并且应该在特定平台上运行程序时进行调整，但是超过线程开销所需的极粗粒度限制了利用并行性的机会。
简单的说就是，标准的线程框架对于支持fork/join程序来说太重量级了。但是，由于线程也构成了许多其他并发和并行编程风格的基础，为了支持这种风格，删除开销或调整线程本身的调度是不可能的（或者至少是不切实际的）。
虽然这些想法肯定有一个较长的heritage，第一个发表的框架，为这些问题提供系统的解决方案是Cilk。Cilk和其他轻量级可执行框架层，在操作系统的基本线程或进程机制之上，提供特殊用途的fork/join支持。本策略同样适用于Java，即使Java线程又反过来分层到更低级别的操作系统功能上。创建这种Java轻量级执行框架的主要优点是使fork/join程序能够以更便携的方式编写，并在支持JVM的各种系统上运行。
FJTask框架基于Cilk中使用的设计的一个变体。在Hood[4]、Filaments[[8]、stackthreads[[10]以及依赖轻量级可执行任务的相关系统中也可以看到其他变体。所有这些框架将任务映射到线程，其方式与操作系统将线程映射到CPU的方式相同，但是，在执行映射时，要利用fork/join程序的简单性、规律性和约束。虽然所有这些框架都可以（以不同的程度）容纳以不同样式编写的并行程序，但它们针对fork / join设计进行了优化：
- 建立了一个工作线程池。每个工作线程都是一个处理队列中的任务的标准("重量级")线程(这里是Thread子类FJTaskRunner的一个实例)。通常，工作线程与系统上的CPU一样多。在本地框架(如Cilk)中，它们被映射到内核线程或轻量级进程，然后依次映射到cpu。在Java中，JVM和操作系统必须被信任，才能将这些线程映射到CPU。但是，对于操作系统来说，这是一个非常简单的任务，因为这些线程是计算密集型的。任何合理的映射策略都会将这些线程映射到不同的CPU。
- 所有的fork/join任务都是轻量级可执行类的实例，而不是线程的实例。在Java中，独立执行任务必须实现Runnable接口，并且定义运行方法。在FJTask框架中，这些任务是FJTask的子类，而不是子类化Thread，两者都实现了Runnable。(在这两种情况下，类都可以实现Runnable，然后提供要在执行任务或线程中运行的实例。由于任务在FJTask方法支持的受限规则下运行，因此子类FJTask更方便，从而能够直接调用它们。)
- 一个特殊的队列和调度规则用于管理任务并通过工作线程执行它们。这些机制是由任务类中提供的几个方法触发的：主要是fork、join、isDone(一个完成状态指示符)，以及一些方便的方法，如coInvoke，fork接着join两个或多个任务。
- 一个简单的控制和管理工具（此处为FJTaskRunnerGroup）设置工作池，并在从正常线程（例如Java程序中执行main的线程）调用时启动给定fork/join任务的执行。
作为程序员如何看待这个框架的标准示例，这里有一个计算Fibonacci函数的类：
class Fib extends FJTask {
static final int threshold = 13;
volatile int number; // arg/result
Fib(int n) {
number = n;
}
int getAnswer() {
if (!isDone())
throw new IllegalStateException();
return number;
}
public void run() {
int n = number;
if (n <= threshold) // granularity ctl
number = seqFib(n);
else {
Fib f1 = new Fib(n - 1);
Fib f2 = new Fib(n - 2);
coInvoke(f1, f2);
number = f1.number + f2.number;
}
}
public static void main(String[] args) {
try {
int groupSize = 2; // for example
FJTaskRunnerGroup group =
new FJTaskRunnerGroup(groupSize);
Fib f = new Fib(35); // for example
group.invoke(f);
int result = f.getAnswer();
System.out.println("Answer: " +
result);
} catch (InterruptedException ex) {
}
}
int seqFib(int n) {
if (n <= 1) return n;
else return seqFib(n - 1) + seqFib(n - 2);
}
}
此版本的运行速度至少比同等程序快30倍，其中每个新任务在第4节中描述的平台上的新java.lang.Thread中运行。它在维护多线程Java程序的内在可移植性的同时做到了这一点。程序员通常只关注两个调整参数：
- 要构造的工作线程数，通常应该与平台上可用的CPU数量相对应（或更少，为了其他不相关的目的而保留处理，或者偶尔更多，以吸收非计算冗余）。
- 粒度参数，表示生成任务的开销超过潜在并行性优势的点。这个参数通常更依赖于算法，而不是平台。通常可以确定在单处理器上运行时获得良好结果的阈值，但是当它们存在时仍然利用多个CPU。作为一个附带好处，这种方法与JVM动态编译机制很好地融合，这些机制比单片程序更好地优化小方法。这与数据局部性优势一起，可以使fork/join算法甚至在单处理器上胜过其他类型的算法。
2.1 工作-窃取
fork/join框架的核心在于它的轻量级调度机制。FJTask采用Cilk工作窃取调度程序中开创的基本策略：
- 每个工作线程在其自己的调度队列中维护可运行的任务。
- 队列被维护为双端队列(即deques，通常发音为“decks”)，支持LIFO的push和pop操作，以及FIFO的take操作。
- 在由给定工作线程运行的任务中生成的子任务被推送到该工作者自己的deque上。
- 工作线程通过弹出任务以LIFO（最年轻的优先）顺序处理自己的deques。
- 当工作线程没有要运行的本地任务时，它会尝试使用FIFO（最早的优先）规则从另一个随机选择的工作者那里获取（“窃取”）任务。
- 当工作线程遇到join操作时，它会处理其他任务(如果可用的话)，直到目标任务被注意到已经完成为止(通过isDone)。否则，所有任务都在不阻塞的情况下运行到完成。
- 当工作者线程没有工作并且没有从其它线程中窃取任何工作时，它将回退(通过yield、sleep和/或优先级调整-参见第3节)，并且稍后再试，除非所有的工人都知道类似空闲，在这种情况下，它们都会阻塞，直到从顶层调用另一个任务为止。
正如[5]中更详细讨论的那样，每个线程使用LIFO规则处理自己的任务，但窃取其他任务的FIFO规则对于一大类递归的fork / join设计是最佳的。不太正式地说，该设计提供了两个基本优势：它通过让偷窃者作为所有者在双端队列的另一侧进行操作来减少争用。它还利用了递归分治算法的特性，即早期生成“大”任务。因此，较旧的被盗任务可能提供更大的工作单元，导致窃取线程进一步递归分解。
作为这些规则的一个结果，对于基本操作使用相对较小的任务粒度的程序往往比那些只使用粗粒度分区或不使用递归分解的程序运行得更快。尽管在大多数fork/join程序中相对较少的任务被盗，但创建许多细粒度的任务意味着只要工作线程准备好运行它就可以使用任务。
3. 实现
该框架已经在大约800行纯Java代码中实现，主要是在java.lang.Thread的子类FJTaskRunner中实现的。FJTasks只维护布尔完成状态，并通过委托当前工作线程执行所有其他操作。FJTaskRunnerGroup类用于构造工作线程，维护一些共享状态(例如，偷窃操作所需的所有工作线程的标识)，并帮助协调启动和关闭。更详细的实现文档可以在util.并发包中获得。本节只讨论在实现此框架时遇到的两组问题和解决方案：支持高效的deque操作(Push、POP和Take)，以及管理线程获得新工作的窃取协议。
3.1 双端队列
为了实现高效且可扩展的执行，必须尽可能快地完成任务管理。 创建，推送和稍后弹出（或者更不频繁地）执行任务是顺序程序中过程调用开销的类比。 较低的开销使程序员能够采用较小的任务粒度，从而更好地利用并行性。
任务分配本身是JVM的责任。Java垃圾收集使我们无需创建一个特殊用途的内存分配程序来维护任务。与其他语言中类似的框架相比，这大大降低了实现FJTask所需的代码的复杂性和代码行。
deque的基本结构采用了每个deque使用单个（尽管可调整大小）数组的通用方案，以及两个索引：top索引就像基于数组的堆栈指针一样，在push和pop时改变。 基本索引仅通过take修改。 由于FJTaskRunner操作都与deque的具体细节密切相关（例如，fork只是调用push），因此该数据结构直接嵌入到类中，而不是被定义为单独的组件。
由于deque数组由多个线程访问，有时没有完全同步(见下文)，但是不能将单个Java数组元素声明为易失性，因此每个数组元素实际上是对维护单个易失性引用的小转发对象的固定引用。这一决定最初是为了确保符合Java内存规则，但结果却是为了提高测试平台上的性能而需要的间接级别，这大概是通过减少由于对附近元素的访问而引起的缓存争用，这些元素由于间接性而在内存中分布得更多。
deque实现中的主要挑战是围绕同步及avoidance。即使在具有优化的同步设备[2]的JVM上，也需要获得锁对于每次推送和弹出操作都成为瓶颈。然而，在Cilk[5]中采取的策略的改编提供了一种基于以下观察结果的解决方案：
- push和pop操作仅由所有者线程调用。
- 对取操作的访问可以很容易地通过“取”上的入口锁一次仅限于一个窃取线程。(此deque锁还用于在必要时禁用采取操作。)因此，将干扰控制简化为两方同步问题。
- 只有当deque即将变为空时，pop和take操作才能进行干预。否则，它们将保证对数组中不相交的元素进行操作。
将top索引和base索引定义为volatile可确保如果deque肯定具有多个元素，则pop和take可以在不锁定的情况下继续进行。like算法完成的，在该算法中，push预减top：
if (--top >= base) ...
take预增top:
if (++base < top) ...
在每种情况下，他们必须通过比较两个指数来检查这是否会导致双端队列变空。在潜在冲突时使用非对称规则：pop重新检查状态并尝试在获得deque锁定后继续（与take持有的相同），仅在deque确实为空时才退出。 take操作只是立即退出，通常然后试图从另一个受害者窃取。 这种不对称性与Cilk中使用的其他类似的THE协议的唯一显着不同。
使用易失性索引还可以使推送操作在不同步的情况下进行，除非deque数组即将溢出，在这种情况下，它必须首先获得deque锁才能调整数组的大小。否则，只需确保topis只在deque阵列插槽被填充后才更新，就可以抑制任何take的干扰。
在初始实现之后，发现几个JVM不符合Java内存模型[6]规则，要求在写入易失性字段对之后进行准确读取。 作为一种解决方法，如果看起来有两个或更少的元素，则调整弹出以在锁定下重试的标准，并且take操作添加了辅助锁以确保内存屏障。 只要所有者线程（在此处保存用于在读取易失性字段时保持正确的内存顺序的平台）最多丢失一个索引更改，这就足够了，并且仅导致性能的微小减速。
3.2 窃取和空闲
工作窃取框架中的工作线程对它们正在运行的程序的同步需求一无所知。他们只是generate，push，pop，take，管理状态和执行任务。当所有线程都有大量工作时，这种方案的简单性可以实现高效执行。However, this streamlining comes at the price of relying on heuristics when there is not enough work; i.e., during startup of a main task, upon its completion, and around global full-stop synchronization points employed in some fork/join algorithms.
这里的主要问题是当一个工作线程没有本地任务而且不能从任何其他线程窃取一个时该怎么办。 如果程序在专用的多处理器上运行，那么就可以依靠硬忙等待旋转循环来尝试窃取工作。 但是，即使在这里，尝试窃取也会增加争用，即使那些非空闲的线程也会减慢（由于3.1节中的锁定协议）。 此外，在此框架的更典型的使用上下文中，操作系统应该以某种方式确信尝试运行其他不相关的可运行进程或线程。
在Java中实现这一目标的工具很薄弱，没有任何保证(参见[6，7])，但在实践中通常似乎是可以接受的(类似于Hood[3]所描述的技术也是如此)。无法从任何其他线程获得工作的线程在尝试其他抢断之前会降低其优先级，在尝试之间执行Thread.yield，并在其FJTaskRunnerGroup中注册为非活动线程。如果所有其他人都变得不活跃，他们都会阻止等待额外的主要任务。否则，在给定数量的额外自旋之后，线程进入休眠阶段，在那里他们睡眠(长达100 ms)，而不是在盗取尝试之间屈服。这些强加的睡眠会导致程序的人为延迟，这些程序需要很长时间才能完成任务。但这似乎是最好的通用妥协。框架的未来版本可能会提供额外的控制方法，以便程序员在影响性能时可以覆盖默认值。
7. 参考
[1] Agesen, Ole, David Detlefs, and J. Eliot B. Moss. Garbage Collection and Local Variable Type-Precision and Liveness in Java Virtual Machines. In Proceedings of 1998 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 1998.
[2] Agesen, Ole, David Detlefs, Alex Garthwaite, Ross Knippel, Y.S. Ramakrishna, and Derek White. An Efficient Meta-lock for Implementing Ubiquitous Synchronization. In Proceedings of OOPSLA ’99, ACM, 1999.
[3] Arora, Nimar, Robert D. Blumofe, and C. Greg Plaxton. Thread Scheduling for Multiprogrammed Multiprocessors. In Proceedings of the Tenth Annual ACM Symposium on
Parallel Algorithms and Architectures (SPAA), Puerto Vallarta, Mexico, June 28 - July 2, 1998.
[4] Blumofe, Robert D. and Dionisios Papadopoulos. Hood: A User-Level Threads Library for Multiprogrammed Multiprocessors. Technical Report, University of Texas at
Austin, 1999.
[5] Frigo, Matteo, Charles Leiserson, and Keith Randall. The Implementation of the Cilk-5 Multithreaded Language. In Proceedings of 1998 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 1998.
[6] Gosling, James, Bill Joy, and Guy Steele. The Java Language Specification, Addison-Wesley, 1996.
[7] Lea, Doug. Concurrent Programming in Java, second edition, Addison-Wesley, 1999.
[8] Lowenthal, David K., Vincent W. Freeh, and Gregory R. Andrews. Efficient Fine-Grain Parallelism on Shared-Memory Machines. Concurrency-Practice and Experience,10,3:157-173, 1998.
[9] Simpson, David, and F. Warren Burton. Space efficient execution of deterministic parallel programs. IEEE Transactions on Software Engineering, December, 1999.
[10]Taura, Kenjiro, Kunio Tabata, and Akinori Yonezawa. "Stackthreads/MP: Integrating Futures into Calling Standards." In Proceedings of ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming (PPoPP), 1999.
