面向Fork/Join框架的软件重构及性能分析
开篇：润墨网以专业的文秘视角，为您筛选了一篇面向Fork/Join框架的软件重构及性能分析范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：针对目前对于Fork/Join框架应用和性能分析的相关工作还不多的现状，以JGF基准测试程序套件为基础，对其中的series、crypt、sparsematmult和sor等程序使用Fork/Join框架进行重构，并以series程序为例，详细地说明了重构的过程。在实验中，首先，测试了每个程序在不同阈值下使用Fork/Join框架分别递归1、2、3次执行程序的时间，进而选择相对较好的阈值；然后，对每个程序使用Fork/Join框架和使用Thread的执行时间进行了对比；此外，测试了重构后的程序在执行过程中任务窃取的情况。实验结果表明，Fork/Join框架执行时间与多线程执行时间相比，平均降低了14.2%；对于series程序，当数据大小为sizeC且线程个数为2时，Fork/Join框架执行时间比多线程执行时间降低高达40%，可见，在多核处理器平台上应用Fork/Join框架比使用多线程将获得更好的性能。
关键词：Fork/Join框架；软件重构；工作窃取；性能分析
中图分类号： TP311
文献标志码：A
0引言
随着多核处理器的普及和众核处理器的发展，面向多核的并行编程已经成为了高性能计算领域的研究热点。与传统的串行程序设计相比，并行编程不仅可以缩短任务执行的时间，而且能更加充分地利用多核处理器资源，提高任务执行的效率[1]。因此，越来越多的人开始关注并行编程，并在多核平台使用并行程序设计技术。
JDK1.7中提出的fork/join框架是并行编程中一个经典的编程框架，它可以适应多核时代并行编程的要求。Fork/Join框架的思想是分而治之，即将所要执行的任务分解为多个子任务并行执行。该框架的核心是工作窃取，当一个线程将自身任务队列中全部任务执行完毕后，会从其他未执行完毕的线程任务队列中窃取任务执行，从而帮助其他线程尽快地执行完毕，这样既可以缩短程序执行的时间，又能够充分发挥多核计算机的资源优势。
目前，国内外针对Fork/Join框架的研究很多。文献[2]中对JDK1.7中Fork/Join框架的基本原理、设计方法和实现机制进行了详细的介绍。文献[3]中通过典型案例详细的介绍了Fork/Join框架的应用，例如，如何应用Fork/Join框架建立ForkJoinPool、加入任务等。在国内，Wang等[4]对多处理器系统下Fork/Join程序的响应时间进行了研究。刘振英等[5]针对Fork/Join任务图，提出了一个基于任务复制的静态调度算法TSA_FJ。虽然目前对于Fork/Join框架已有了一些研究，但对于Fork/Join框架的应用及性能分析的相关研究还有待于进一步研究。
针对这一问题，本文应用Fork/Join框架对JGF基准测试程序[6]中的series、crypt、sparsematmult和sor等程序进行了重构，将程序中单线程顺序执行的代码重构为Fork/Join框架并行执行的代码。在实验中，测试并分析了阈值大小对Fork/Join框架执行程序的影响，并在两种实验环境下测试了每个程序使用Fork/Join框架和多线程的执行时间。此外，测试了重构后的程序在执行过程中任务窃取的情况。
1相关工作
Dig等[7]提出了一个软件并行化重构工具CONCURRENCER，该工具可以将串行的Java代码重构为并行的Java代码， 通过使用java.util.concurrent 并发库将线程操作转换为使用Fork/Join框架。Luján等[8]对Fork/Join框架的扩展版本DIFOJO框架的应用、实现与性能进行了深入的研究，通过对比Fork/Join框架的性能，对DIFOJO的性能进行了评估。Ojail等[9]针对多核嵌入式系统中更细粒度的并行任务的调度问题，提出了一种轻量级的Fork/Join框架――ATAM， 并通过实验证明，ATAM框架的应用可以取得更加理想的加速比，明显优于本领域的其他技术方法。Lui等[10]通过对多重处理环境下Fork/Join并行程序的计算时间的界限进行研究，提出了一种算法来获取预期执行时间的上限与下限。Nelissen等[11]通过研究提出了一种调度Fork/Join并行实时任务的新算法。Gao等[12]提出了一种静态的、平均的案例分析方法，该方法被称之为MOQA法，可以对Fork/Join框架执行的程序进行分析，以并行快速排序程序为例，验证了该分析方法准确性更高。
杨峰等[13]针对广义Fork/Join任务图提出了基于遗传算法的调度算法，该算法将遗传算法和任务复制相结合，有效地缩短了得到最优结果的时间。梁珊珊等[14]提出了一种带通信限制的Fork/Join图调度算法CCTD，通过实验表明， CCTD算法是一种适应性强的、高效的Fork/Join图调度算法； 杨斌等[15]通过对Fork/Join任务图的研究，提出了一个能产生最优调度的新的贪心调度算法，该算法具有很高的加速比和总体效率。
2Fork/Join框架的编程模式
在使用Fork/Join框架时，首先对问题的规模进行度量，在问题规模较小的情况下，采用直接执行的方式；在问题规模较大的情况下，将任务分解为多个子任务，并将子任务交给多个线程并行执行。值得说明的是，当Fork/Join框架完成一次任务分解后，如果子任务的规模还不够小，则可以对子任务进行递归分解，直到所有子任务都适合在目标平台求解为止。其编程模式的伪代码如下：
程序前
if（问题规模小于阈值）{
直接执行任务；
}else{
将任务分解为多个子任务；
并行执行子任务；
等待所有子任务完成；
汇总子任务结果；
}
程序后
Fork/Join框架的编程模式主要基于Fork和Join两种操作： Fork操作主要负责创建新的分支任务，该方法决定了任务的异步执行； Join操作用于阻塞当前任务，直到其子任务完成并返回结果。在使用Fork/Join框架编程时，可以通过设定阈值改变任务执行的粒度，阈值的设定是决定Fork/Join框架执行时间的关键因素，其大小一般根据经验或者详细的实验分析设定，设置过大或过小都影响加速效果。
3重构
本章对JGF基准测试程序套件[6]中的几个测试程序进行了重构，这些测试程序包括series、crypt、sparsematmult和sor。以series基准测试程序为例，对如何应用Fork/Join框架进行重构作了详细介绍。crypt、sparsematmult和sor等程序的重构方法与series类似，不再赘述。
series程序用来计算函数的前n项傅里叶系数。程序主要围绕两个数组进行计算，其中一维数组array_rows决定了程序中执行的数据大小，二维数组TestArray用来存放计算得出的傅里叶系数。为了使series程序更适合Fork/Join框架的编程模式，本文采用数据划分的方式对series程序的数据进行分解，在每一次递归分解中，将根据硬件线程数对数据区间进行等量划分，并将其交由线程执行。
在使用Fork/Join框架进行重构时，需要建立可以被Fork/Join框架执行的任务类SeriesTask，该类通过继承类RecursiveAction得到，在该类中，重写compute（）方法，如下面代码所示。重构时，用iupper和ilow两个变量来表示每个子任务数据区间的最大最小值。
程序前
protected void compute（） {
if（（iupper-ilow）
Do（）；
}else {
int a=ilow；
int b=iupper；
int slice=（b-a+JGFSeriesBench.nthreads）/
JGFSeriesBench.nthreads；
SeriesTask[] tasks=
new SeriesTask[JGFSeriesBench.nthreads]；
for （int id=0； id < JGFSeriesBench.nthreads； id++）{
ilow=id * slice+a；
if （id==0）
ilow=id * slice+a；
iupper=（id+1） * slice+a；
if （iupper > b）
iupper=b；
tasks[id]=new SeriesTask（ilow，iupper）；
}
invokeAll（tasks）；
}
}
程序后
在compute（）方法中，首先要比较程序中执行的数据规模与阈值的大小，series程序中用iupper与ilow的差值来表示程序中执行数据的规模： 如果差值小于阈值或者程序中执行任务的线程个数为1，则顺序执行程序； 如果差值大于阈值，则对任务进行第一次分解。为完成series中数据的分解，建立一个大小为线程个数的SeriesTask任务数组用于存放每个任务，并且设定4个变量：slice、id、a、b，在分解过程中，通过计算每段数据的上下界来完成数据的划分。经过第一次任务分解后，子任务个数等于程序中执行任务的线程个数，并且每一个子任务都有相互独立、各不相同的数据区间。第一次数据分解完成后，程序会再次进行判定，如果经过数据划分后的iupper与ilow的差值仍旧大于阈值，则对分解后的任务进行递归分解，直到满足条件为止。
其次，当类SeriesTask建好之后，对series程序的类SeriesTest进行重构。SeriesTest类主要完成以下几个功能：首先，建立ForkJoinPool，ForkJoinPool可以通过它的无参构造方法创建；然后，要将单线程顺序执行的任务区间的上下界传递给SeriesTask类中的iupper和ilow；最后，将SeriesTask任务放到ForkJoinPool中执行，等待执行完毕后关闭线程池。此外，为了得到ForkJoinPool中的线程的执行状态，通过getStealCount（）和getParallelism（）方法对ForkJoinPool进行了监听。
4实验
4.1测试程序的数据大小
JGF基准测试套件[6]中的series、crypt、sparsematmult和sor程序均有sizeA、sizeB、sizeC三组大小不同的数据作为输入，如表1所示。
4.2实验环境
实验采用两种不同的实验环境，具体配置如下：
实验环境1硬件上，使用英特尔 Core i3 M380处理器，主频为2.53GHz，该处理器有两个处理核，均支持超线程技术，内存为3GB。软件上，使用Windows7 64位操作系统，使用Eclipse 4.4.1作为重构平台，JDK版本是1.7.0_76。
实验环境2硬件上，使用英特尔Xeon E52620处理器，主频为2.1GHz，该处理器有12个处理核，均支持超线程技术，硬件线程数为24，内存为8GB。软件上，使用Linux 3.13操作系统，使用Eclipse 4.4.2作为重构平台，JDK版本是1.8.0_25。
4.3实验结果
本节主要分为三部分：第一部分以series和crypt程序为例，给出了不同阈值下Fork/Join框架执行程序的时间，并通过对实验结果进行分析得出每个程序执行时间最短时阈值的大小； 第二部分在得到较好阈值的情况下，对每个程序使用Fork/Join框架和使用Thread的执行时间进行对比； 第三部分测试了程序在使用Fork/Join框架执行过程中的任务窃取情况。实验中所有程序的测试结果都是在运行五次测试结果基础上取平均值。
4.3.1不同阈值下Fork/Join框架执行程序的测试结果
对Fork/Join框架分别递归1、2、3执行任务的情况进行了测试。以series和crypt程序在双核处理器平台上的测试结果为例，详细介绍了不同的阈值下Fork/Join框架执行程序的性能。最后给出了Fork/Join框架执行每个测试程序较好的阈值。图中的fj（1）、fj（2）和fj（3）分别代表Fork/Join框架递归1、2、3次执行程序。
图1给出了双核处理器实验环境下，改变阈值后Fork/Join框架分别递归1、2、3次执行series程序得到的测试结果。如图1（a）所示，线程数为2时，Fork/Join递归3次执行程序时间最短，但当线程数为8和16，Fork/Join框架递归多次的执行时间要长。出现这种情况的原因可能在于当线程数为8和16时Fork/Join递归2次建立的子任务数分别为64和256，而递归3次建立的子任务数分别为512和4096，程序在子任务的建立与管理方面耗费很多时间，使整体时间变长。在图1（c）中，当线程数为2时，Fork/Join框架递归1次执行任务需要535.198s，递归2次执行任务需要325.479s，递归3次执行任务的时间是321.811s。可见，当任务数据量很大时，Fork/Join递归多次执行任务有很好的加速效果，而当数据量较小时，Fork/Join递归1次执行程序时间较短。根据图1中执行数据的大小与线程个数可以得到Fork/Join框架执行series程序时间最短的点，求出该点对应的阈值大小。
图2给出了双核处理器的实验环境下，改变阈值后Fork/Join框架分别递归1、2、3次执行crypt程序的测试结果。线程数为2和4时（如图2（a）和图2（b）所示），Fork/Join递归多次比递归1次执行任务时间短；而当线程数为8和16时，Fork/Join递归多次执行任务耗费的时间长。这是因为当线程个数多时，Fork/Join框架递归分解的子任务数过多，从而在子任务的管理上消耗时间，使整体时间延长。
从以上实验可以看出，使用Fork/Join框架时，程序的执行时间由线程个数和阈值共同决定。一般情况下，当执行数据较大的程序时，线程数量多，任务执行会很快；当程序数据量较小时，单线程执行程序时间较短，随着线程数增多，在线程管理方面耗费的时间也会增多，执行时间可能比单线程执行时间长。Fork/Join框架的阈值决定了任务的切分粒度。如果任务的切分粒度设置过大，程序的加速效果有限；如果任务切分粒度太小，消耗在任务管理的成本占了主要部分，加速效果不明显，甚至会超过单线程执行任务的时间。因此，在应用Fork/Join框架执行任务时，要根据具体情况设定恰当的阈值，从而决定Fork/Join框架执行任务的递归次数，分配恰当的任务粒度。
4.3.2使用Fork/Join框架与使用多线程执行程序时间对比
图3～6给出了实验环境1下Fork/Join框架重构（fj）与多线程重构程序（thread）的测试结果。在Fork/Join框架执行程序时，阈值设定如表2。
从图3可以看出，随着线程个数增多，程序执行时间明显减少。当线程个数达到4时，系统硬件线程数与程序软件线程数达到一致，此时程序执行时间最短。随着软件线程数超过硬件线程数，程序执行时间保持稳定。在图3（c）中，当软件线程数超过硬件线程数时，不论是使用Fork/Join框架还是使用多线程，均出现了超加速比的现象，这可能是由于数据大小的划分比较适合程序执行造成的。从图3可以明显看出，Fork/Join框架执行程序测试时间更加理想。当线程个数为2、4和8时，Fork/Join框架执行程序时间明显低于多线程执行时间。当线程个数为16时，图3（a）中Fork/Join框架执行时间为1.2s，多线程执行时间为1.217s；图3（b）中Fork/Join框架执行时间为11.145s，多线程执行时间为11.164s；图3（c）中Fork/Join框架执行时间为258.496s，多线程执行时间为276.199s，通过数据可以得出线程数为16时，Fork/Join框架执行时间略低于多线程执行时间。
图4给出了crypt程序分别使用Fork/Join框架执行和多线程执行的测试结果。在图4中，Fork/Join框架和多线程执行程序的时间随着线程个数的增多而减少，在线程数大于等于4时，趋于稳定。在图4（a）中，当线程个数为16时，Fork/Join框架执行程序时间高于多线程执行时间，造成这一点的原因可能在于子任务数量过多而执行数据小，耗费在子任务管理方面的时间在整体时间中所占比重较大，延长了任务执行的整体时间。其他情况下，Fork/Join框架执行程序的时间均小于多线程执行时间。例如，在图4（a）中，在2个线程的情况下，使用Fork/Join框架执行程序花费0.119s，而使用多线程执行花费0.153s；图4（b）中，当线程个数为2时，Fork/Join框架执行程序时间是0.496s，多线程执行程序时间是0.749s。
图5给出了Fork/Join框架重构和多线程重构的sparsematmult程序的测试结果。从图中可以明显看出，Fork/Join框架执行程序的时间更加理想，明显低于多线程执行时间。在图5（b）和5（c）中，当软件线程数超过硬件线程数时，同样出现了超加速比的情况，这可能是由于数据大小的划分比较适合sparsematmult程序执行造成的。
图6测试了Fork/Join框架重构和多线程重构后sor程序的执行时间。当线程个数增加时，程序执行时间逐渐变短，但当线程个数达到8或16时，任务执行时间会有一个明显的增加，这主要是由于该测试程序本身造成的，在我们之前的研究中也发现过类似的现象[16]。而当线程数为2和4时，使用Fork/Join框架程序执行时间低于使用多线程执行时间。
图7～10给出了实验环境2下Fork/Join框架重构与多线程重构程序的测试结果。阈值设定见表3。
图7给出了分别使用Fork/Join框架和多线程执行series程序的时间。从图7中可以明显看出，当线程个数小于24时，Fork/Join框架执行时间低于多线程执行时间，当软件线程数等于或者超过硬件线程数（24）时，两种框架执行时间比较接近，造成时间接近的原因可能是由于当线程数为24和48时，使用表3中的阈值会使Fork/Join框架递归分解的子任务个数分别为576和2304，过多的线程数会使程序在子任务的建立和管理时浪费时间，导致Fork/Join框架执行程序时间与多线程执行时间接近。
图8给出了crypt程序经过Fork/Join框架重构和多线程重构后程序的测试结果。从图8中可以看出，由于crypt程序执行时间整体较短，所以使用Fork/Join框架与多线程执行程序的时间曲线几乎重合，Fork/Join框架执行时间略低于多线程的执行时间。
图9给出了sparsematmult程序经过Fork/Join框架和多线程重构后的执行时间。从图9（a）和9（b）中可以明显看出，当线程个数为48时，Fork/Join执行时间大于多线程执行时间，原因可能是当线程数为48时，图9（a）和9（b）中阈值大小分别为110和220，Fork/Join执行任务时递归划分的子任务个数都为2304，子任务数过多导致花费在子任务创建与管理上的时间较长，并且在整体时间中所占比重较大，所以会出现Fork/Join框架比多线程执行时间长的情况。其他情况下，Fork/Join框架执行时间均短于多线程执行时间。
图10测试了sor程序分别使用Fork/Join框架和多线程执行的时间。当线程数为1、2、4、8和12时，程序执行时间逐渐变短，且Fork/Join框架执行程序取得的实验结果更加理想。但当线程个数达到24和48时，任务执行时间会明显的增加，这主要是由于该测试程序本身造成的，在我们之前的研究中也发现过类似的现象[16]。
图片
图10实验环境2下sor程序的测试结果
4.3.3基准测试程序中的任务窃取情况
Fork/Join框架的核心是任务窃取，工作窃取可以充分利用多线程进行并行计算，减少线程之间的竞争。表3给出了双核处理器实验环境下，线程数为4时，使用Fork/Join框架递归2次执行JGF基准测试程序时的任务窃取情况。
表格（有表名）
表4执行重构后程序时的任务窃取情况
JGFBenchmarksizeAsizeBsizeC
series222
crypt122
sparsematmult112
sor011
5结语
本文基于Fork/Join框架对JGF基准测试程序进行了重构， 将series、crypt、sparsematmult和sor等程序重构为可以使用Fork/Join框架并行执行的程序，并对多线程重构和Fork/Join重构后程序的执行时间进行了测试。实验结果表明：Fork/Join框架可以充分发挥多核计算机的资源优势，其执行任务所需时间低于多线程执行时间。此外，Fork/Join框架使用起来方便快捷，对于线程创建、线程调度等复杂问题，可以交由框架本身来完成，极大地简化了编写并行程序的琐碎工作，既可以有效地降低开发人员的工作量，又可以最大化地利用计算资源。
参考文献：
[1]WANG L， CUI H， CHEN L， et al. Research on task parallel programming model[J]. Journal of Software， 2013， 24（1）：77-90.（王蕾，崔慧敏，陈莉，等.任务并行编程模型研究与进展[J].软件学报，2013，24（1）：77-90.）
[2]LEA D. A Java Fork/Join framework[C]// Proceedings of the 2000 ACM Conference on Java Grande. New York： ACM， 2000： 36-43.
[3]GONZLEZ J F. Java 7 concurrency cookbook[M]. Birmingham： Packt Publishing， 2012：171-205.
[4]WANG Y， ZHAO Q， ZHENG D. ForkJoin program response time on multiprocessors with exchangeable join[J]. Journal of Zhejiang University Science A： Applied Physics and Engineering， 2006， 7（6）： 927-936.
[5]LIU Z， FANG B， JIANG Y， et al. A new algorithm for scheduling ForkJoin task graph[J]. Journal of Software， 2002， 13（4）： 693-697. （刘振英，方滨兴，姜誉，等.一个调度ForkJoin任务图的新算法[J].软件学报，2002，13（4）：693-697.）
[6]SMITH L A， BULL J M， OBDRIZALEK J. A parallel Java grande benchmark suite[C]// Proceedings of the 2001 ACM/IEEE Conference on Supercomputing. New York： ACM， 2001： 6-15.
[7]DIG D， MARRERO J， ERNST M D. Refactoring sequential Java code for concurrency via concurrent libraries[C]// Proceedings of the 31st International Conference on Software Engineering. Washington， DC： IEEE Computer Society， 2009： 397-407.
[8]LUJN M， MUKARAKATE G， GURD J R， et al. DIFOJO： a Java fork/join framework for heterogeneous networks[C]// Proceedings of the 13th Euromicro Conference on Parallel， Distributed and Networkbased Processing. Piscataway： IEEE， 2005：297-304.
[9]OJAIL M， DAVID R， LHUILLIER Y， et al. ARTM： a lightweight ForkJoin framework for manycore embedded systems[C]// Proceedings of the 2013 Conference on Design， Automation and Test in Europe. San Jose： EDA Consortium， 2013：1510-1515.
[10]LUI J C S， MUNTZ R R， TOWSLEY D. Computing performance bounds of ForkJoin parallel programs under a multiprocessing environment[J]. IEEE Transactions on Parallel and Distributed Systems， 1998， 9（3）：295-311.
[11]GARIBAYMARTINEZ R， NELISSEN G， FERREIRA L L， et al. On the scheduling of ForkJoin parallel/distributed realtime tasks[C]// Proceedings of the 2014 9th IEEE International Symposium on Industrial Embedded Systems. Piscataway： IEEE， 2014：31-40.
[12]GAO A， RRA K， SCHELLEKENS M. Static average case analysis ForkJoin framework programs based on MOQA method[C]// Proceedings of the 6th International Symposium on Parallel Computing in Electrical Engineering. Washington， DC： IEEE Computer Society， 2011：1-6.
[13]YANG F， ZHANG J. Research of generalized ForkJoin task graph scheduling[J]. Ordnance Industry Automation， 2009， 28（12）： 37-40. （杨峰，张建军.广义ForkJoin任务图的调度问题研究[J].兵工自动化，2009，28（12）：37-40.）
[14]LIANG S， WU J， ZHANG J. CCTD： a scheduling algorithm under communication constraints for ForkJoin task graphs[J]. Computer Science， 2009， 36（6）： 282-285. （梁珊珊，吴佳骏，张军超. CCTD：一种通信限制下的ForkJoin任务调度算法[J].计算机科学，2009，36（6）：282-285.）
[15]
YANG B， ZHANG J， YANG F. Greedy algorithm for scheduling ForkJoin task graphs[J]. Computer Engineering and Design， 2008， 29（15）： 3864-3866. （杨斌，张建军，杨峰.调度ForkJoin任务图的贪心算法[J].计算机工程与设计，2008，29（15）：3864-3866.）
[16]ZHANG Y， JI W. A scalable methodlevel parallel library and its improvement[J]. The Journal of Supercomputing， 2012， 61（3）： 1154-1167.