Java并发编程

Java并发编程 - Fork/Join框架

2019-05-22  本文已影响0人  HRocky

原文地址:http://gee.cs.oswego.edu/dl/papers/fj.pdf

摘要

本文描述了一个支持并行编程风格的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程序来说太重量级了。但是,由于线程也构成了许多其他并发和并行编程风格的基础,为了支持这种风格,删除开销或调整线程本身的调度是不可能的(或者至少是不切实际的)。

虽然这些想法肯定有一个较长的heritage,第一个发表的框架,为这些问题提供系统的解决方案是Cilk。Cilk和其他轻量级可执行框架层,在操作系统的基本线程或进程机制之上,提供特殊用途的fork/join支持。本策略同样适用于Java,即使Java线程又反过来分层到更低级别的操作系统功能上。创建这种Java轻量级执行框架的主要优点是使fork/join程序能够以更便携的方式编写,并在支持JVM的各种系统上运行。

fj-1.png

FJTask框架基于Cilk中使用的设计的一个变体。在Hood[4]、Filaments[[8]、stackthreads[[10]以及依赖轻量级可执行任务的相关系统中也可以看到其他变体。所有这些框架将任务映射到线程,其方式与操作系统将线程映射到CPU的方式相同,但是,在执行映射时,要利用fork/join程序的简单性、规律性和约束。虽然所有这些框架都可以(以不同的程度)容纳以不同样式编写的并行程序,但它们针对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程序的内在可移植性的同时做到了这一点。程序员通常只关注两个调整参数:

2.1 工作-窃取

fork/join框架的核心在于它的轻量级调度机制。FJTask采用Cilk工作窃取调度程序中开创的基本策略:

fj-2.png

正如[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]中采取的策略的改编提供了一种基于以下观察结果的解决方案:

将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.

上一篇 下一篇

猜你喜欢

热点阅读