改进Fork/Join阈值选取公式的建议

阈值的选择是影响Fork/Join并行框架充分发挥并行性能的关键因素之一。若阈值过小，则递归分割的子任务总数过多，增加管理消耗；若阈值过大，无法划分足够的子任务，易导致线程处于空闲状态。以PDDDP三个方案为例，且每次递归把任务分割为两个规模相等的子任务，则PDDDP三个方案的任务递归分割方式见图B.1。另外，表B.1以及图B.2描述了PDDDP三个方案在不同阈值测试条件下的平均计算耗时，测试环境为配置1超线程状态关闭。

表B.1　配置1中PDDDP三个方案不同阈值测试条件下计算耗时

在表B.1以及图B.1中，不同阈值的设置在PDDDP方法中展现了不同的并行性能。以方案3为例，当阈值设置为100×104，阈值大于计算任务规模590976，计算任务不进行子任务分割。因此，在2核和4核环境下仅1个逻辑线程运行PDDDP，计算耗时与串行计算近似相同，并未发挥并行算法优势。当阈值设置为30×104，计算任务进行了1次子任务分割即划分为2个子任务，因此，在2核环境下2个逻辑线程得到充分利用，发挥了并行计算的效果，但是，在4核环境下仍有2个逻辑线程处于闲置状态，并未充分发挥并行性能，仅当阈值小于等于15×104时，4核环境下的所有逻辑线程均得到充分利用。然而，在逻辑线程充分利用的基础上，当阈值设置为500时，由于阈值过小导致划分的子任务过多，导致计算耗时比其他阈值设置情况下有所增加。此外，在2核和4核环境下，展现最优并行性能的阈值设置分别为5×104和10×104。因此，在不同并行环境下，展现最优并行性能的阈值需要测试得到。

图B.1　PDDDP三个测试方案任务递归分割

本书所提的阈值选取公式均采用式（3.1）的设置方式，父任务分割的子任务数量等于应用配置的逻辑线程数。但是，根据本书所提多种方法的并行结果分析，对于核数较多的配置（如配置2），最优并行性能不一定出现在多核资源满负荷利用环境下（比如PDDDP方案二和方案三的最优并行核数分别是8核和16核），当核数超过最优并行核数时，并行性能出现“瓶颈”，继续增加并行核数会导致加速比逐渐下降。因此，建议在阈值设置式（3.1）基础上，通过改进式（B.1）来调整父任务划分的子任务数目，使并行算法在最优核数环境下执行运算，充分发挥并行性能，即(www.xing528.com)

式中：k表示递归增减系数，为整数。

当k＝0时，即为本书采用测试的阈值计算公式；当k＞0时，表示在式（3.1）划分的子任务数基础上，递归减少任务数。比如k＝1，在配置2中32核超线程关闭环境下，PDDDP方法可把父任务划分为16个子任务，即在32核环境下，也只能调用16核进行计算，则根据8.4.3节中图8.8计算结果，PDDDP方案三可获得最优并行性能。以此类推，当k＝2时，父任务划分为8个子任务，仅可利用8核实现并行，则PDDDP方案二可获得最优并行性能；当k＜0时，表示在式（3.1）划分的子任务数基础上，递归增加任务数。比如当k＝-1时，在配置1中4核超线程关闭环境下，PDDDP方法将把父任务划分为8个子任务，即每个逻辑线程计算2个子任务，则根据图B.2计算结果，PDDDP方案二将获得阈值设置为β＝1×104（同样划分8个子任务）时的并行性能，优于阈值设置式（3.1）测试结果。

图B.2　配置1中PDDDP不同阈值测试耗时

总之，阈值的设置对Fork/Join并行算法的影响非常明显，且设置方式较为灵活。采用改进的阈值选取式（B.1）设置并行方法的阈值是一种可供选择的途径。通过测试结果的分析，在已有多核配置的前提下，当配置的核数较少时，建议设置k＝0，可保证并行算法在获得较好并行性能的基础上，自适应规模不同的计算任务，充分利用多核资源；当配置的核数较多时，尤其对于规模较小的计算任务，需要对参数k进行调试，测试最优并行核数，避免在核数较多环境下无法有效发挥并行算法的优势。