Java Fork/Join 框架

Doug Lea
纽约州立大学奥斯威戈分校
Oswego, NY 13126
315-341-2688
dl@cs.oswego.edu

摘要

本文描述了一个支持并行编程风格的 Java 框架的设计、实现和性能表现。在这种编程风格中，问题通过（递归地）将其分解为子任务来解决，这些子任务并行执行、等待完成，然后组合结果。总体设计是 Cilk 中发明的工作窃取框架的变体。主要实现技术围绕任务队列和工作线程的高效构建和管理。实测性能显示，大多数程序都能获得良好的并行加速效果，同时也揭示了可能的改进方向。

1. 引言

分叉/连接并行性是获得良好并行性能最简单、最有效的设计技术之一。分叉/连接算法是常见分治算法的并行版本，通常采用以下形式：

Result solve(Problem problem) {
    if (problem is small)
    直接求解问题
    else {
    将问题分解为独立的部分
    分叉新的子任务来解决每个部分
    连接所有子任务
    从子结果组合最终结果
    }
}

分叉操作启动一个新的并行分叉/连接子任务。连接操作导致当前任务在分叉的子任务完成之前不会继续执行。分叉/连接算法与其他分治算法一样，几乎总是递归的，反复拆分子任务直到它们小到可以使用简单、简短的顺序方法来解决。

第 4.4 节讨论了一些相关的编程技术和示例。《Java 并发编程》第二版 [7] 中也有讨论。本文讨论了 FJTask 的设计（第 2 节）、实现（第 3 节）和性能（第 4 节），FJTask 是一个支持这种编程风格的 Java™ 框架。FJTask 可作为 util.concurrent 包的一部分从 http://gee.cs.oswego.edu 获取。

2. 设计

分叉/连接程序可以使用任何支持构建并行执行的子任务的框架来运行，并配有等待其完成的机制。然而，java.lang.Thread 类（以及 Java 线程通常基于的 POSIX pthreads）对于支持分叉/连接程序来说并非最优选择：

• 分叉/连接任务具有简单且规律性的同步和管理需求。分叉/连接任务产生的计算图允许比通用线程更高效的调度策略。例如，分叉/连接任务除了等待子任务外永远不需要阻塞。因此，跟踪阻塞通用线程所需的开销和记账工作被浪费了。
• 在合理的基任务粒度下，构造和管理线程的成本可能大于任务本身的计算时间。虽然粒度在特定平台上运行程序时可以并且应该进行调整，但抵消线程开销所需的极粗粒度限制了利用并行性的机会。

简而言之，标准线程框架对于支持大多数分叉/连接程序来说太重了。但由于线程也是许多其他并发和并行编程风格的基础，因此仅为了支持这种风格而移除开销或调整线程本身的调度是不切实际的。

虽然这些想法肯定有更长的历史，但第一个提供系统化解决方案的已发布框架是 Cilk[5]。Cilk 和其他轻量级可执行框架在操作系统的基本线程或进程机制之上构建了专门的 分叉/连接支持。这种策略同样适用于 Java，尽管 Java 线程本身也是构建在更低级的操作系统能力之上的。创建这样一个 Java 轻量级执行框架的主要优势在于使分叉/连接程序能够以更可移植的方式编写，并能在支持 JVM 的各种系统上运行。

FJTask 框架基于 Cilk 中使用的设计的变体。其他变体出现在 Hood[4]、Filaments[8]、stackthreads[10] 以及依赖轻量级可执行任务的相关系统中。所有这些框架将任务映射到线程的方式与操作系统将线程映射到 CPU 的方式大致相同，但在执行映射时利用了分叉/连接程序的简单性、规律性和约束性。虽然所有这些框架都可以在一定程度上适应以不同风格编写的并行程序，但它们针对分叉/连接设计进行了优化：

• 建立一个工作线程池。每个工作线程是一个标准（“重量级”）线程（这里是 Thread 子类 FJTaskRunner 的实例），处理队列中保存的任务。通常，工作线程的数量与系统上的 CPU 数量相同。在 Cilk 等原生框架中，这些被映射到内核线程或轻量级进程，再映射到 CPU。在 Java 中，必须信任 JVM 和 OS 将这些线程映射到 CPU。然而，这对操作系统来说是一个非常简单的任务，因为这些线程是计算密集型的。任何合理的映射策略都会将这些线程映射到不同的 CPU。
• 所有分叉/连接任务都是轻量级可执行类的实例，而不是线程的实例。在 Java 中，独立可执行任务必须实现 Runnable 接口并定义 run 方法。在 FJTask 框架中，这些任务继承 FJTask 而不是继承 Thread，两者都实现 Runnable。（在这两种情况下，一个类也可以实现 Runnable，然后将实例提供给正在执行的任务或线程来运行。因为任务在 FJTask 方法支持的限制规则下操作，继承 FJTask 会更方便，因此可以直接调用它们。）
• 使用专门的队列和调度规则来管理任务并通过工作线程执行它们（见第 2.1 节）。这些机制由任务类中提供的少数方法触发：主要是 fork、join、isDone（完成状态指示器）以及一些便捷方法如 coInvoke（分叉然后连接两个或多个任务）。
• 一个简单的控制和管理工具（这里是 FJTaskRunnerGroup）设置工作线程池，并在从普通线程调用时启动给定分叉/连接任务的执行（如 Java 程序中执行 main 的线程）。

作为该框架如何呈现给程序员的标准示例，下面是一个计算斐波那契函数的类：

class Fib extends FJTask {
    static final int threshold = 13;
    volatile int number; // 参数/结果

    Fib(int n) { number = n; }

    int getAnswer() {
        if (!isDone())
            throw new IllegalStateException();
        return number;
    }

    public void run() {
        int n = number;
        if (n <= threshold) // 粒度控制
            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; // 例如
            FJTaskRunnerGroup group = new FJTaskRunnerGroup(groupSize);
            Fib f = new Fib(35); // 例如
            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);
    }
}

与在每个新任务都在新的 java.lang.Thread 中运行的等效程序相比，该版本在第 4 节描述的平台上至少快三十倍。它在保持多线程 Java 程序固有可移植性的同时做到了这一点。程序员通常感兴趣的调优参数只有两个：

1. 要构造的工作线程数，通常应该对应于平台上可用的 CPU 数量（或更少，以保留处理能力用于其他不相关的目的，或偶尔更多，以吸收非计算空闲）。
2. 粒度参数，表示生成任务的开销超过潜在并行性收益的临界点。这个参数通常更依赖于算法而非平台。通常可以确定一个阈值，在单处理器上运行时能获得良好结果，但在存在多个 CPU 时仍能利用它们。作为附带好处，这种方法与 JVM 动态编译机制配合良好，后者对小方法的优化优于整体过程。再加上数据局部性优势，分叉/连接算法甚至可以在单处理器上胜过其他类型的算法。

2.1 工作窃取

分叉/连接框架的核心在于其轻量级调度机制。FJTask 采用 Cilk 工作窃取调度器开创的基本策略：

• 每个工作线程在自己的调度队列中维护可运行任务。
• 队列维护为双端队列（即 deque，通常读作"decks"），支持 LIFO 推入和弹出操作，以及 FIFO 获取操作。
• 由给定工作线程运行的任务生成的子任务被推入该工作线程自己的 deque。
• 工作线程以 LIFO（最新优先）顺序处理自己的 deque，通过弹出任务。
• 当工作线程没有本地任务可运行时，它尝试从另一个随机选择的工作线程获取（“窃取”）任务，使用 FIFO（最旧优先）规则。
• 当工作线程遇到连接操作时，它处理其他任务（如果有的话），直到目标任务被确认已完成（通过 isDone）。所有任务否则会运行完成而不阻塞。
• 当工作线程没有工作且无法从其他线程窃取时，它会退让（通过让步、睡眠和/或优先级调整——见第 3 节）并稍后重试，除非所有工作线程都被确认处于类似空闲状态，在这种情况下，它们都会阻塞，直到从顶层调用另一个任务。

正如 [5] 中更详细讨论的，对每个线程处理自己的任务使用 LIFO 规则，但对窃取其他任务使用 FIFO 规则，对于一大类递归分叉/连接设计是最优的。更非正式地说，该方案提供两个基本优势：

• 它通过让窃取者在 deque 的另一端操作来减少争用。它还利用了递归分治算法尽早生成"大"任务的特性。因此，被窃取的较旧任务可能提供更大的工作单元，导致窃取线程进行进一步的递归分解。
• 作为这些规则的结果之一，与仅使用粗粒度分区或不使用递归分解的程序相比，使用相对较小任务粒度进行基本操作的程序往往运行得更快。尽管大多数分叉/连接程序中窃取的任务相对较少，但创建许多细粒度任务意味着只要工作线程准备好运行它，任务就很可能是可用的。

3. 实现

该框架已用约 800 行纯 Java 代码实现，主要在类 FJTaskRunner 中，它是 java.lang.Thread 的子类。FJTask 本身只维护一个布尔完成状态，所有其他操作都通过委托给其当前工作线程来执行。FJTaskRunnerGroup 类用于构造工作线程，维护一些共享状态（例如所有工作线程的身份，用于窃取操作），并帮助协调启动和关闭。

util.concurrent 包中提供了更详细的实现文档。本节只讨论实现此框架时遇到的两组问题及解决方案：支持高效的 deque 操作（push、pop 和 take），以及管理线程获取新工作的窃取协议。

3.1 双端队列（Deque）

为了实现高效和可扩展的执行，任务管理必须尽可能快。创建、推入和后续弹出（或不太频繁的获取）任务类似于顺序程序中的过程调用开销。较低的开销使程序员能够采用更小的任务粒度，从而更好地利用并行性。

任务分配本身是 JVM 的责任。Java 垃圾回收使我们不需要创建专门的内存分配器来维护任务。与其他语言中的类似框架相比，这大大降低了实现 FJTask 的复杂性和代码行数。

deque 的基本结构采用通用方案：每个 deque 使用一个（虽然是可调整大小的）数组，加上两个索引。顶部索引的作用就像基于数组的栈指针，在 push 和 pop 时改变。底部索引仅由 take 修改。由于 FJTaskRunner 操作都与 deque 的具体细节紧密相关（例如，fork 只是调用 push），因此这个数据结构直接嵌入到类中，而不是定义为单独的组件。

因为 deque 数组被多个线程访问，有时没有完全同步（见下文），但单个 Java 数组元素不能声明为 volatile，所以每个数组元素实际上是一个指向维护单个 volatile 引用的小转发对象的固定引用。这个决定最初是为了确保符合 Java 内存规则，但它导致的间接层在测试平台上被证明提高了性能，可能是因为减少了对附近元素的访问造成的缓存争用，由于间接寻址，这些元素在内存中被分散了一些。

deque 实现中的主要挑战围绕同步及其避免。即使在具有优化同步设施的 JVM 上 [2]，每次 push 和 pop 操作都需要获取锁会成为瓶颈。然而，Cilk[5] 中采用的策略的改编提供了一个基于以下观察的解决方案：

• Push 和 pop 操作仅由拥有线程调用。
• 通过在 take 上的入口锁，可以轻松地将对 take 操作的访问限制为一次只允许一个窃取线程。（这个 deque 锁也用于在必要时禁用 take 操作。）因此，干扰控制减少为两方同步问题。
• Pop 和 take 操作只有在 deque 即将变空时才会相互干扰。否则，它们保证在数组的不同元素上操作。

将 top 和 base 索引定义为 volatile 确保 pop 和 take 如果确信 deque 有多个元素，则可以在不锁定的情况下继续。这是通过类似 Dekker 的算法完成的，其中 push 预减 top：

if (--top >= base) ...

take 预增 base：

if (++base < top) ...

在每种情况下，它们都必须检查这是否可能导致 deque 变空，通过比较两个索引。在潜在冲突时使用非对称规则：pop 重新检查状态并在获取 deque 锁后尝试继续（与 take 持有的是同一个锁），仅在 deque 确实为空时才退让。take 操作反而立即退让，通常然后尝试从不同的受害者窃取。这种不对称性代表了与 Cilk 中使用的类似 THE 协议的显著偏离。

volatile 索引的使用还使 push 操作可以在不同步的情况下进行，除非 deque 数组即将溢出，在这种情况下，它必须首先获取 deque 锁来调整数组大小。否则，只需确保在 deque 数组槽被填充后才更新 top，就可抑制任何 take 的干扰。

在初始实现之后，发现几个 JVM 不符合 Java 内存模型 [6] 规则，该规则要求对成对的 volatile 字段进行准确的写后读。作为变通方案，pop 在锁下重试的条件被调整为如果似乎有两个或更少的元素就触发，并且 take 操作添加了辅助锁以确保内存屏障。只要拥有线程最多错过一个索引更改（对于在读取 volatile 字段时保持正确内存顺序的平台来说这里成立），这就足够了，并且只会导致性能轻微下降。

3.2 窃取和空闲

工作窃取框架中的工作线程对正在运行的程序的同步需求一无所知。它们只是生成、推入、弹出、获取、管理状态和执行任务。当所有线程都有大量工作时，这种方案的简单性会带来高效执行。然而，这种简化是以在工作时间不足时依赖启发式方法为代价的；即，在主任务启动时、其完成时以及在某些分叉/连接算法中使用的全局完全停止同步点附近。

这里的主要问题是当工作线程没有本地任务且无法从任何其他线程窃取时该怎么办。如果程序在专用多处理器上运行，那么可以论证依赖硬忙轮询循环来尝试窃取工作。但是，即使在这里，尝试窃取也会增加争用，这可能会减慢那些非空闲线程的速度（由于第 3.1 节中的锁定协议）。此外，在这个框架的更典型使用场景中，应该以某种方式说服操作系统尝试运行其他不相关的可运行进程或线程。

在 Java 中实现这一点的工具很弱，没有保证（见 [6, 7]），但通常在实践中似乎是可接受的（与 Hood[3] 中描述的类似技术一样）。一个从任何其他线程获取工作失败的线程在尝试额外窃取之前会降低其优先级，执行 Thread.yield 在尝试之间，并将其注册为在其 FJTaskRunnerGroup 中不活动。如果所有其他线程都变为不活动，它们都会阻塞等待额外的顶层任务。否则，在给定数量的额外自旋之后，线程进入睡眠阶段，在那里它们睡眠（最多 100ms）而不是在窃取尝试之间让步。这些强加的睡眠可能导致任务分解需要很长时间的程序出现人为延迟。但看起来这是最好的通用折衷方案。框架的未来版本可能会提供额外的控制方法，以便程序员在影响性能时可以覆盖默认值。

4. 性能

在这些编译器和 JVM 几乎持续改进的时代，性能测量只有短暂的价值。然而，本节报告的指标揭示了框架的一些基本特性。

下表简要描述了七个分叉/连接测试程序。这些程序是 util.concurrent 包中作为演示可用的程序的改编。选择它们是为了展示可以在此框架中运行的问题类型的多样性，以及为一些常见的并行测试程序获取结果。

对于主要测试，程序在运行 Solaris 7 的 30-CPU Sun Enterprise 10000 上运行，JVM 为 Solaris Production 1.2（1.2.2_05 版本的早期版本）。JVM 使用选择"绑定线程"进行线程映射的环境参数运行，以及第 4.2 节中讨论的内存参数。以下报告的一些额外测量在 4-CPU Sun Enterprise 450 上运行。

程序使用非常大的输入参数运行，以最小化计时器粒度和 JVM 预热伪影。通过在启动计时器之前运行初始问题集来避免一些其他预热效果。大多数数据是三次运行的中位数，但一些（包括第 4.2-4.4 节中的大多数后续测量）仅反映单次运行，因此有些嘈杂。

4.1 加速比

可扩展性测量是通过使用 1…30 个工作线程组运行相同问题集获得的。没有办法知道 JVM 是否总是将每个线程映射到不同的 CPU（当可用时）。虽然对此没有证据，但将新线程映射到 CPU 的延迟可能随着线程数量增加和/或在不同的测试程序中有系统性的变化。

然而，总的来说，结果表明增加线程数量可靠地增加了使用的 CPU 数量。

加速比报告为 Time_n / Time_1。整体最佳加速比出现在积分程序中（30 个线程时加速比为 28.2）。最差的是 LU 分解程序（30 个线程时加速比为 15.35）。

另一种测量可扩展性的方法是按任务速率，即执行单个任务（可以是递归步骤或叶子步骤）所花费的平均时间。下图显示了一次插桩运行捕获的任务速率数据。理想情况下，每单位时间每线程处理的任务数应该是恒定的。它们通常随着线程数量增加而略有下降这一事实表明存在一些可扩展性限制。注意任务速率的相当大差异，反映了任务粒度的差异。Fib 中看到最小的任务大小，即使阈值设置为 13，在使用 30 个线程运行时也生成并执行了每秒 280 万个任务。

四个因素似乎解释了那些未线性扩展的程序中加速比的下降。其中三个是任何并行框架共有的，但让我们从 FJTask 独有的一个开始（与 Cilk 等相比），即 GC 影响。

4.2 垃圾回收

在许多方面，现代 GC 设施与分叉/连接框架完美匹配：这些程序可以生成大量任务，其中几乎所有任务在执行后很快变成垃圾。在任何给定时间，确定性分叉/连接程序只需要最多 p（其中 p 是线程数）倍的顺序版本所需的空间来保存记账信息 [10]。代际半空间复制收集器（包括本测量中使用的 JVM 中的收集器——见 [1]）很好地处理了这一点，因为它们只遍历和复制非垃圾单元。这样做避免了手动并行内存管理中最棘手的问题之一：追踪由一个线程分配但由另一个线程使用的内存。垃圾回收器对内存的来源不敏感，因此不需要处理此类问题。

作为代际复制收集总体优越性的简单指标，使用此处主要实验中使用的内存设置在 5.1 秒内执行的 Fib 的四线程运行，如果在禁用该 JVM 的代际复制阶段的情况下运行需要 9.1 秒（该 JVM 在此情况下完全依赖标记-清除）。

然而，当内存分配速率如此之高以至于线程必须几乎持续停止来执行垃圾回收时，这些 GC 机制会变成可扩展性问题。下图显示了三种内存设置下的加速比差异（该 JVM 支持可选参数来设置内存参数）：使用默认 4 兆字节半空间、使用 64 兆字节半空间，以及根据线程数量缩放的内存量（2 + 2p 兆字节）。使用较小的半空间时，停止线程和收集垃圾的开销开始影响扩展性，因为垃圾生成速率随着额外线程的增加而上升。

鉴于这些结果，所有其他测试运行都使用 64m 半空间。更好的策略是根据每个测试中的线程数量来缩放内存量。（如图所示，这会使所有加速比看起来略微更线性。）或者或另外，可以根据线程数量按比例增加特定程序的任务粒度阈值。

4.3 内存局部性和带宽

四个测试程序创建并操作非常大的共享数组或矩阵：对数字排序，乘法、分解或对矩阵执行松弛。其中，排序可能对在处理器之间移动数据的后果最敏感，因此对系统整体内存带宽最敏感。为了帮助确定这些影响的性质，Sort 程序被重新构建为四个版本，分别对字节、短整数、整数和长整数排序。每个版本只对 0…255 范围内的数据进行排序，以确保其他方面相同。数据元素越宽，内存流量越大。

结果显示，增加的内存流量导致更差的加速比，尽管它们没有提供确凿证据表明这是尾部下降的唯一原因。

元素宽度也影响绝对性能。例如，只使用一个线程，排序字节需要 122.5 秒，而排序长整数需要 242.4 秒。

4.4 任务同步

如第 3.2 节所述，工作窃取框架在处理频繁的全局任务同步时有时会遇到问题。工作线程继续轮询更多工作，尽管没有任何工作，从而产生争用，并且在 FJTask 中，有时甚至迫使线程进入空闲睡眠。

Jacobi 程序说明了其中一些问题。该程序执行 100 步，每一步中所有单元格都根据简单的最近邻平均公式进行更新。一个全局（基于树的）屏障分隔每一步。为了确定同步影响的程度，编写了该程序的版本，只在每 10 步后进行同步。扩展性差异显示了当前策略的影响，并表明需要在此框架的未来版本中包含额外的方法，以允许程序员覆盖默认参数和策略。（但请注意，此图可能略微夸大了纯同步影响，因为 10 步版本也可能保持更大的任务局部性。）

4.5 任务局部性

FJTask 与其他分叉/连接框架一样，针对工作线程在本地消费其创建的大部分任务的情况进行了优化。当这种情况不发生时，性能可能会受到影响，原因有两个：

• 窃取任务的开销比弹出任务的开销大得多。
• 在大多数任务对共享数据操作的情况下，运行你自己的细分任务可能保持更好的数据访问局部性。

如图所示，在大多数程序中，被窃取任务的相对数量最多只有几个百分点。然而，LU 和 MM 程序随着线程数量增加产生更大的工作负载不平衡（因此相对更多的窃取）。这些程序的某些算法调整可能会减少这种影响，从而带来更好的加速比。

4.6 与其他框架的比较

对跨语言和框架的程序进行明确的甚至有意义的比较是不可能的。然而，相对测量至少可以显示 FJTask 框架与用其他语言（这里是 C 和 C++）编写的类似框架相比的一些基本优势和局限性。下图比较了基于或类似于 Cilk、Hood、Stackthreads 和/或 Filaments 分发版提供的程序的性能。所有这些都在 4-CPU Enterprise 450 上使用 4 个线程运行。为了避免重新配置其他框架或其测试程序，所有测试都使用比上面更小的问题集运行。所有结果代表三次运行中的最佳者，使用似乎提供最快时间的编译器和运行时设置。Fib 在没有任何粒度阈值的情况下运行；即隐含阈值为 1。（Filaments Fib 中的"剪枝"设置设置为 1024，这使其行为更类似于其他版本。）

从一到四个线程的加速比在不同的框架和测试程序中非常相似（在 3.0 到 4.0 之间），因此随附图表关注绝对性能的差异。然而，因为所有这些框架的多线程方面都很快，大多数差异反映了来自不同编译器、优化开关和配置参数的应用程序特定代码质量差异。事实上，很可能比这里使用的不同选择可能在许多高性能应用程序中产生几乎任何相对性能排名。

FJTask（在 JVM 上）对主要对数组和矩阵进行浮点计算的程序通常表现更差。尽管 JVM 正在改进，但它们仍然不总是与 C 和 C++ 程序中使用的强大后端优化器竞争。虽然此图表未显示，但 FJTask 版本的所有程序在禁用优化编译时都比这些其他框架中的程序版本运行得更快，一些非正式测试表明大部分剩余差异是由于数组边界检查和相关运行时义务。当然，这些问题和挑战正吸引着 JVM 和编译器开发人员的极大关注和努力。对于计算密集型程序，代码质量方面观察到的差异可能会减少。

5. 结论

本文已证明在纯 Java 中支持可移植、高效、可扩展的并行处理是可能的，并且为能够利用该框架的程序员提供了便捷的 API，他们只需遵循一些简单的设计规则和设计模式（如 [7] 中提出和讨论的）。所测量的示例程序的性能特征既为框架用户提供了进一步指导，也揭示了框架本身的潜在改进领域。

尽管可扩展性结果仅针对单个 JVM 显示，但一些主要经验发现应该更普遍地成立：

• 虽然代际 GC 通常与并行性配合良好，但当垃圾生成速率迫使非常频繁的垃圾回收时，它可能会阻碍可扩展性。在这个 JVM 上，根本原因似乎是停止线程进行收集所需的时间大约与运行线程的数量成正比。因为更多运行中的线程每单位时间生成更多垃圾，开销可能随线程数量近似二次增长。即便如此，它仅在 GC 速率本来就相对较高时才对性能产生重大影响。然而，由此产生的问题需要进一步研究和开发并发和并行 GC 算法。此处呈现的结果还表明，在多处理器 JVM 上提供调优选项和自适应机制以将内存扩展到活动处理器数量的必要性。
• 大多数可扩展性问题仅在程序使用比大多数现成多处理器上甚至可用的更多 CPU 运行时才会显现出来。FJTask（以及其他分叉/连接框架）在常见的 2 路、4 路和 8 路 SMP 机器上为几乎任何分叉/连接程序提供近乎理想的加速比。本论文似乎是第一份报告在任何为现成多处理器设计的分叉/连接框架上在超过 16 个 CPU 上运行时的系统结果的论文。需要进一步测量来确定这里看到的结果模式是否也适用于其他框架。
• 应用程序程序的特征（包括内存局部性、任务局部性、全局同步的使用）通常对可扩展性和绝对性能的影响比框架、JVM 或底层操作系统的特征更大。例如，非正式测试表明，deque 中仔细避免同步（在第 3.1 节中讨论）对任务生成速率相对较低的程序（如 LU）几乎没有影响。然而，专注于将任务管理开销保持在最低限度扩大了框架及相关设计和编程技术的适用性和实用范围。

除了增量改进外，该框架的未来工作可能包括构建有用的应用程序（而不是演示和测试）、随后在生产程序负载下进行评估、在不同 JVM 上的测量，以及为多处理器集群使用而设计的扩展开发。

6. 致谢

这项工作得到了 Sun Labs 合作研究 grant 的部分支持。感谢 Sun Labs Java Topics Group 的 Ole Agesen、David Detlefs、Christine Flood、Alex Garthwaite 和 Steve Heller 提供的建议、帮助和评论。David Holmes、Ole Agesen、Keith Randall、Kenjiro Taura 和匿名审稿人提供了有用的论文草案评论。Bill Pugh 指出了第 3.1 节中讨论的 JVM 读写限制。非常特别感谢 Dave Dice 预留时间并在 30 路 Enterprise 上执行测试运行。

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.