3　Fork/Join多核并行框架

3.1　Fork/Join基本原理

多核处理器是现今计算机硬件技术发展的主流，无论个人计算机还是工作站或服务器，多核处理器配置已十分普及。因此，多核并行技术的发展和应用已成为必然趋势。目前，多核并行技术已在许多科学研究领域广泛应用，且有较多成熟的并行框架可供选择。常见的多核并行框架有MPI、Open MP、Fork/Join等。选择合适的框架对于编程人员实现并行计算非常重要，主要依赖于系统平台兼容性、任务应用途径、源码支持类型等因素。本书所提算法均采用Java语言实现，而常用框架中Fork/Join是一款由Java语言编写的多核并行框架，特别适合并行Java语言编写的算法。因此，本书采用Fork/Join并行框架实现所提算法的并行计算。

Fork/Join并行框架最早在2000年由学者Lea[236]提出。通过不断的改进和测试，Fork/Join已作为标准的并行框架集成到Java 7中。该框架的主要特点包括以下五个方面。

（1）核心方法采用“分治法”实现（图3.1），即将父任务递归分解成若干个规模较小的子任务，各子任务互相独立且与父任务相同；然后，递归求解这些子任务，再将各个子任务的解合并得到父任务的解。

图3.1　分治法示意图

（2）设计了独特的线程池技术，当程序开始执行时，默认创建与可用的处理器数目相同的活动线程数，便于线程的维护和管理，减小了系统资源消耗，尤其适合在单机多核配置上部署多线程程序。

（3）在“分治法”执行过程中，定义了一个可自由设置的控制子问题规模大小的阈值作为子问题规模的上限值，即当子问题规模小于或等于阈值时，“分治法”执行结束，各子问题被平均分配到不同线程中开始并行计算。图3.2为阈值控制方式示意图。

图3.2　阈值控制方式示意图

α—任务规模；v—递归次数；β—阈值

（4）在子问题并行计算过程中，Fork/Join设计了独特的双端队列排序模式，并采用了“工作窃取”算法，即当一个线程的队列计算任务为空时，将从其他处于工作状态的线程队列尾部“窃取”计算任务，避免了线程处于闲置状态，可提高线程的利用效率，图3.3为“工作窃取”算法示意图。

图3.3　“工作窃取”算法示意图

（5）Fork/Join提供了固定的程序接口，使算法并行化的实现更加简便，详细可见附录A中提供的数组排序并行化的实现代码。