Java Fork Join 框架(四)性能

原文 http://gee.cs.oswego.edu/dl/papers/fj.pdf   作者:Doug Lea   译者:萧欢

4性能

如今,随着编译器与Java虚拟机性能的不断提升,性能测试结果也仅仅只能适用一时。但是,本节中所提到的测试结果数据却能揭示Fork/join框架的基本特性。

下面表格中简单介绍了在下文将会用到的一组fork/join测试程序。这些程序是从util.concurrent包里的示例代码改编而来,用来展示fork/join框架在解决不同类型的问题模型时所表现的差异,同时得到该框架在一些常见的并行测试程序上的测试结果。

程序(Program 描述(Description
Fib(菲波那契数列) 如第2节所描述的Fibonnaci程序,其中参数值为47阀值为13
Integrate(求积分) 使用递归高斯求积对公式**-4748的积分,i15之间的偶数。
Micro 对一种棋盘游戏寻找最好的移动策略,每次计算出后面四次移动。
Sort(排序) 使用合并/快速排序算法对1亿数字进行排序(基于Cilk算法)
MM(矩阵相乘) 2048*2048double类型的矩阵进行相乘
LU(矩阵分解) 4096*4096double类型的矩阵进行分解
Jacobi(雅克比迭代法) 对一个4096*4096double矩阵使用迭代方法进行矩阵松弛,迭代次数上限为100

下文提到的主要的测试,其测试程序都是运行在Sun Enterprise 10000服务器上,该服务器拥有30CPU,操作系统为Solaris7系统,运行Solaris商业版1.2 JVM2.2.2_05发布版本的一个早期版本)。同时,Java虚拟机的关于线程映射的环境参数选择为“bound threads(译者注:XX:+UseBoundThreads,绑定用户级别的线程到内核线程,只与solaris有关),而关于虚拟机的内存参数设置在4.2章节讨论。另外,需要注意的是下文提到的部分测试则是运行在拥有4CPUSun Enterprise450服务器上。

为了降低定时器粒度以及Java虚拟机启动因素对测试结果的影响,测试程序都使用了数量巨大的输入参数。而其它一些启动因素我们通过在启动定时器之前先运行初始化任务来进行屏蔽。所得到的测试结果数据,大部分都是在三次测试结果的中间值,然而一些测试数据仅仅来自一次运行结果(包括4.2~4.4章节很多测试),因此这些测试结果会有噪音表现。

加速比(Speedups

通过使用不同数目(1~30)的工作线程对同一问题集进行测试,用来得到框架的扩展性测试结果。虽然我们无法保证Java虚拟机是否总是能够将每一个线程映射到不同的空闲CPU上,同时,我们也没有证据来证明这点。有可能映射一个新的线程到CPU的延迟会随着线程数目的增加而变大,也可能会随不同的系统以及不同的测试程序而变化。但是,所得到的测试结果的确显示出增加线程的数目确实能够增加使用的CPU的数目。

加速比通常表示为“Time n/Time1.如上图所示,其中求积分的程序表现出最好的加速比(30个线程的加速比为28.2),表现最差的是矩阵分解程序(30线程是加速比只有15.35

另一种衡量扩展性的依据是:任务执行率,及执行一个单独任务(这里的任务有可能是递归分解节点任务也可能是根节点任务)所开销的平均时间。下面的数据显示出一次性执行各个程序所得到的任务执行率数据。很明显,单位时间内执行的任务数目应该是固定常量。然而事实上,随着线程数目增加,所得到的数据会表现出轻微的降低,这也表现出其一定的扩展性限制。这里需要说明的是,之所以任务执行率在各个程序上表现的巨大差异,是因其任务粒度的不同造成的。任务执行率最小的程序是Fib(菲波那契数列),其阀值设置为13,在30个线程的情况下总共完成了280万个单元任务。

导致这些程序的任务完成率没有表现为水平直线的因素有四个。其中三个对所有的并发框架来说都是普遍原因,所以,我们就从对FJTask框架(相对于Cilk等框架)所特有的因素说起,即垃圾回收。

4.2垃圾回收

总的来说,现在的垃圾回收机制的性能是能够与fork/join框架所匹配的:fork/join程序在运行时会产生巨大数量的任务单元,然而这些任务在被执行之后又会很快转变为内存垃圾。相比较于顺序执行的单线程程序,在任何时候,其对应的fork/join程序需要最多p倍的内存空间(其中p为线程数目)。基于分代的半空间拷贝垃圾回收器(也就是本文中测试程序所使用的Java虚拟机所应用的垃圾回收器)能够很好的处理这种情况,因为这种垃圾回收机制在进行内存回收的时候仅仅拷贝非垃圾内存单元。这样做,就避免了在手工并发内存管理上的一个复杂的问题,即跟踪那些被一个线程分配却在另一个线程中使用的内存单元。这种垃圾回收机制并不需要知道内存分配的源头,因此也就无需处理这个棘手的问题。

这种垃圾回收机制优势的一个典型体现:使用这种垃圾回收机制,四个线程运行的Fib程序耗时仅为5.1秒钟,而如果在Java虚拟机设置关闭代拷贝回收(这种情况下使用的就是标记清除垃圾回收机制了),耗时需要9.1秒钟。

然而,只有内存使用率只有达到一个很高的值的情况下,垃圾回收机制才会成为影响扩展性的一个因素,因为这种情况下,虚拟机必须经常停止其他线程来进行垃圾回收。以下的数据显示出在三种不同的内存设置下(Java虚拟机支持通过额外的参数来设置内存参数),加速比所表现出的差异:默认的4M半空间,64M半空间,另外根据线程数目按照公式(2+2pM设置半空间。使用较小的半空间,在额外线程导致垃圾回收率攀高的情况下,停止其他线程并进行垃圾回收的开销开始影响加封。

鉴于上面的结果,我们使用64M半空间作为其他测试的运行标准。其实设置内存大小的一个更好的策略就是根据每次测试的实际线程数目来确定。(正如上面的测试数据,我们发现这种情况下,加速比会表现的更为平滑)。相对的另一方面,程序所设定的任务粒度的阀值也应该随着线程数目成比例的增长。

4.3 内存分配和字宽

在上文提到的测试程序中,有四个程序会创建并操作数量巨大的共享数组和矩阵:数字排序,矩阵相乘/分解以及松弛。其中,排序算法应该是对数据移动操作(将内存数据移动到CPU缓存)以及系统总内存带宽,最为敏感的。为了确定这些影响因素的性质,我们将排序算法Sort改写为四个版本,分别对Byte字节数据,short型数据,int型数据以及long型数据进行排序。这些程序所操作的数据都在0~255之间,以确保这些对比测试之间的平等性。理论上,操作数据的字宽越大,内存操作压力也相应越大。

测试结果显示,内存操作压力的增加会导致加速比的降低,虽然我们无法提供明确的证据来证明这是引起这种表现的唯一原因。但数据的字宽的确是影响程序的性能的。比如,使用一个线程,排序字节Byte数据需要耗时122.5秒,然而排序long数据则需要耗时242.5秒。

4.4 任务同步

正如3.2章节所讨论的,任务窃取模型经常会在处理任务的同步上遇到问题,如果工作线程获取任务的时候,但相应的队列已经没有任务可供获取,这样就会产生竞争。在FJTask框架中,这种情况有时会导致线程强制睡眠。

Jacobi程序中我们可以看到这类问题。Jacobi程序运行100步,每一步的操作,相应矩阵点周围的单元都会进行刷新。程序中有一个全局的屏障分隔。为了明确这种同步操作的影响大小。我们在一个程序中每10步操作进行一次同步。如图中表现出的扩展性的差异说明了这种并发策略的影响。也暗示着我们在这个框架后续的版本中应该增加额外的方法以供程序员来重写,以调整框架在不同的场景中达到最大的效率。(注意,这种图可能对同步因素的影响略有夸大,因为10步同步的版本很可能需要管理更多的任务局部性)

4.5 任务局部性

FJTask,或者说其他的fork/join框架在任务分配上都是做了优化的,尽可能多的使工作线程处理自己分解产生的任务。因为如果不这样做,程序的性能会受到影响,原因有二:

从其他队列窃取任务的开销要比在自己队列执行pop操作的开销大。

在大多数程序中,任务操作操作的是一个共享的数据单元,如果只运行自己部分的任务可以获得更好的局部数据访问。

如上图所示,在大多数程序中,窃取任务的相对数据都最多维持在很低的百分比。然后其中LUMM程序随着线程数目的增加,会在工作负载上产生更大的不平衡性(相对的产生了更多的任务窃取)。通过调整算法我们可以降低这种影响以获得更好的加速比。

4.6 与其他框架比较

与其他不同语言的框架相比较,不太可能会得到什么明确的或者说有意义的比较结果。但是,通过这种方法,最起码可以知道FJTask在与其他语言(这里主要指的是CC++)所编写的相近框架比较所表现的优势和限制。下面这个表格展示了几种相似框架(Cilk,Hood ,Stackthreads,以及Filaments)所测试的性能数据。涉及到的测试都是在4CPUSun Enterprise450服务器运行4个线程进行的。为了避免在不同的框架或者程序上进行重新配置,所有的测试程序运行的问题集都比上面的测试稍小些。得到的数据也是取三次测试中的最优值,以确保编译器或者说是运行时配置都提供了最好的性能。其中Fib程序没有指定任务粒度的阀值,也就是说默认的1.(这个设置在Filaments版的Fib程序中设置为1024,这样程序会表现的和其它版本更为一致)。

在加速比的测试中,不同框架在不同程序上所得到的测试结果非常接近,线程数目1~4,加速比表现在(3.0~4.0之间)。因此下图也就只聚焦在不同框架表现的不同的绝对性能上,然而因为在多线程方面,所有的框架都是非常快的,大多数的差异更多的是有代码本身的质量,编译器的不同,优化配置项或者设置参数造成的。实际应用中,根据实际需要选择不同的框架以弥补不同框架之间表现的巨大差异。

FJTask在处理浮点数组和矩阵的计算上性能表现的比较差。即使Java虚拟机性能不断的提升,但是相比于那些CC++语言所使用的强大的后端优化器,其竞争力还是不够的。虽然在上面的图表中没有显示,但FJTask版本的所有程序都要比那些没有进行编译优化的框架还是运行的快的。以及一些非正式的测试也表明,测试所得的大多数差异都是由于数组边界检查,运行时义务造成的。这也是Java虚拟机以及编译器开发者一直以来关注并持续解决的问题。

相比较,计算敏感型程序因为编码质量所引起的性能差异却是很少的。

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: Java Fork Join 框架(四)性能

Latest posts by 叶落无痕 (see all)

FavoriteLoading添加本文到我的收藏
  • Trackback are closed
  • Comments (3)
    • sqtds
    • 02/23. 2014 5:20pm

    翻译的很好,就是怎么把论文所有的图片都去掉了。。。

  1. 对 没有图怎么看?

    • 冰红茶盖
    • 08/17. 2017 2:15pm

    能看啊,再开个窗口就好了。感谢ifeve和译者,目前我在Java多线程方面ifeve最值得感谢!

You must be logged in to post a comment.

return top