任务池方法在非独占式加载并行计算中的应用任务池方法在非独占式加载并行计算中的应用 张文勇，卓红斌，刘杰，胡庆丰 （国防科技大学并行与分布处理国家重点实验室，湖南长沙，410073） 摘 要：摘 要：在非独占式加载并行计算环境中，各节点上计算负载的不确定性和不均匀性会严重影响并行计算的性能。任务池方法可以对各节点的计算负载进行动态调整，是解决这一问题的有效途径。本文介绍用 MPI 实现集中式任务池的方法，并以一个用积分法计算 值的程序为例，给出了任务池并行程序的设计过程。数值实验表明，在非独占式加载并行计算环境中，与静态分配负载的并行算法相比，任务池方法可以明显提高并行计算的性能。 关键词：关键词：任务池；并行计算；非独占式加载；MPI Application of Task Pool Approach in Nonexclusive-possessing Parallel Environment Zhang Wen-yong, Zhuo Hong-bin, Liu Jie, Hu Qing-feng (National Laboratory for Parallel and Distributed Processing, NUDT, Changsha, Hunan, 410073,China) Abstract: In nonexclusive-possessing parallel environment, the uncertainty and heterogeneity of computing load on computer nodes have a bad effect on parallel efficiency. Task Pool Approach can adjust computing load between nodes dynamically. So it can be used to improve parallel performance in nonexclusive-possessing parallel environment. In this paper a MPI implementation of centralized task pool is introduced and the designing process of parallel program using task pool approach is given through an example that calculates using integral method. The numerical test results show that task pool approach can improve the parallel efficiency distinctly in nonexclusive-possessing parallel environment, compared with the parallel algorithm that distribute work to processors evenly. Key words: task pool; parallel algorithm; nonexclusive-possessing Environment; MPI 1 引言 有些并行系统 ，如很多单位的集群系统，是 非独占式加载的并行计算环境。一个并行系统为 全单位的人共享，大家都可以在上面加载程序， 且一个 CPU 上可以加载多个程序。 在这样的并行 计算环境中， 各节点上的计算任务是动态变化的。 在一个并行程序加载之前和运行过程中，都无法 预测各节点上的总计算负载。在这种情况下，静 态分配计算任务显然是不合适的。各节点总负载 的不确定性和不均匀性要求并行程序能够对计算 任务进行动态调整，从而避免某些处理器的空闲 等待，提高并行计算的性能，使计算资源得到更 充分地利用。 本文受到自然科学基金项目 10505031 的资助 任务池方法是实现动态负载平衡的有效途径 之一，它可以有效地解决不规则并行算法中的动 态负载不平衡问题1。其思想是把整个计算任务 分成很多子任务，并将未被计算的子任务放在一 个或多个数据结构中组织成任务池。子任务可以 在计算过程中动态产生。空闲的处理器从任务池 中取得任务并把新产生的任务放到任务池中，直 到任务池中没有未被计算的任务且各个处理器都 空闲时计算结束。 在异构和非独占式加载并行计算环境中，任 务池方法可以使计算能力强或正处于空闲的处理 器多计算一些任务，使计算能力差或还有其它计 算任务的处理器少计算一些任务。它不仅可以根 据处理器的计算能力和空闲状态合理分配计算任 务，而且可以根据各处理器的总负载的变化对计 算任务进行动态调整，从而可以最大程度地发挥并行系统的计算能力。所以任务池方法不仅适合 不规则并行算法，也适合在异构和非独占式加载 并行计算环境中使用。 任务池有多种类型，包括集中式、分布式、 分布式加动态任务窃取、 集中式与分布式相结合、 任务池组等等。文1给出了用 POSIX threads 实 现任务池的方法，并比较了各种任务池的并行性 能。 文23提出一种基于任务并行的 LilyTask 模 型，并用自己定义的元语加以实现。文4中提出 在 SMP 节点内部使用 POSIX threads，在节点之 间使用 MPI 的任务池组实现方法。本文采用纯 MPI 的方法，使用 Master-Slave 并行编程范例实 现集中式任务池，并比较任务池方法与静态分配 负载的并行算法在非独占式加载并行计算环境中 并行性能。 本文第二节介绍集中式任务池及其 MPI 实 现； 第三节介绍一个用积分法计算 值的并行程 序设计过程；第四节给出数值实验结果；第五节 对本文工作进行总结。 2 集中式任务池及其 MPI 实现 2.1 集中式任务池简介集中式任务池简介 集中式任务池是指所有子任务都放在同一个 任务池中，各处理器从任务池中取出任务执行并 把产生的新任务加入到任务池中，当任务池中没 有计算任务且各处理器都空闲时计算结束。其基 本思想可以用图 1 描述。 图 1 集中式任务池 在图 1 中， 左边的椭圆中是划分好了的 n 个 子任务，分别用 T1, T2, , Tn表示；右边的方框 中是并行计算时使用的 m 个处理器，分别用 P0,P1,Pm-1表示， 并且子任务数n处理器数m。在初始任务分配时，可以将 T1分给 P0, T2分给 P1, , Tm分给 Pm-1。当某个处理器将分配给它的 任务计算完成后，再从任务池中取下一个尚未分 配的任务。这样一直到所有任务都被算完为止。 有些计算的总任务数是固定的且可以事先预测， 如在本文将要介绍的例子中；还有些计算的总任 务数随着计算的进行动态变化且无法事先预测， 如在有些自适应细化的非规则并行算法中。 2.2 集中式任务池的集中式任务池的 MPI 实现实现 任务池方法要求动态地分配任务和收集计算 结果，所以进程之间的信息交换是动态变化的。 一般认为，任务池方法比较适合用共享存储和单 边通信的编程方式实现。 但利用 MPI1.1 的非阻塞 发送、非阻塞查询和非阻塞通信完成函数5，也可以实现任务池并行。 在此，我们采用 master-slave 的并行方式。 master 进程负责任务的管理和结果的收集； slave 进程从 master 得到任务并把结果返回给 master。其实现过程如下图所示： 图 2 集中式任务池的 Master-Slave 实现 计算中有两类点对点通信，一类是 master 进程把新任务分给空闲的进程；另一类是 slave 进程将计算完的结果发送给 master 进程。 master 和 slave 的计算和通信过程如图 3 所示。master 进程需要不断地检测是否有结果返回，以便接收 计算结果并分配新的任务给已经空闲的 slave 进 程。其实现过程如下： step1：调用 MPI_IPROBE 检查是否有结果返回； step2：如果有就用 MPI_RECV 接收； step3： 调用 MPI_ISEND 把新任务分配给已经计算完成的 slave 进程。 slave 进程要从 master 接收任务并进行计算， 计算完成后把计算结果返回给master进程然后再 Ti Tn T4 T5 T3 T2 Pm-1 . . . P1 P0 T1 slave master返 回 结 果取 任 务计算任务 任务池任务池 . . . Pm-1P1P0. . 从 master 接收新任务。其实现过程如下： step1：调用 MPI_RECV 接收来自 master 的子任务； step2：计算子任务； step3： 调用 MPI_ISEND 将计算结果发送给 master。 当任务池为空时， master 进程不能马上结束， 还要等待所有 slave 进程把任务算完并把结果返 回然后才能结束。 此时要调用 MPI 的非阻塞通信 完成函数 MPI_WAITALL。 为了避免处理器的空闲，master 需要不断地 检测是否有计算结果返回，如果有就用阻塞式接 收函数 MPI_RECV 接收计算结果， 并把新任务发 送给已经计算完毕的进程。由于一个 slave 进程 算完之后肯定要向 master 请求新的任务，所以在 接收任务时使用的是阻塞式接收函数。 图 3 集中式任务池的 Master-Slave 实现流程 另外，master 进程不只是管理任务池，还要 参与计算，否则让一个处理器只作任务管理不参 与计算对计算资源是一种浪费，尤其是当计算使 用的处理器数较少时，浪费的比例更大。所以， 进行任务管理的master进程同时也是参与计算的 slave 进程。 使用 MPI 实现任务池一方面可以避免访问 冲突，不必显式地使用锁机制；另一方面使程序 有更好的可移植性。 3 算例描述和并行程序设计 值可以用下面的定积分+=10214 xdx)5 . 0求得。数值计算时将区间0,1分成 n 等份，将间隔h=1.0/n 视为 dx，令( =ihxi，将计算出的 =+niixh1214 =+=niixhI1214作为 的近似值。 3.1 平均分配负载的并行算法平均分配负载的并行算法 用 P 个处理器进行并行计算，最直接的方法 是将计算任务平均分配到各个处理器上，程序的 流程图如下： 等待接收结果YN N Y 结束 结束 接收返回结果 新任务？ 任务池空？ 发送结果 接收返回结果 检查结果返回 任务计算 任务请求 任务分配 slave master 图 4 平均分配计算任务的并行程序流程图 图 4 中间虚框中的循环体完成=+niix1214累加和计算。由于 i=i+numprocs，循环的间隔为总 的进程数，所以上面的计算将计算任务平均分配 到各个进程。这是最一般的并行计算方法，在独 占式加载的同构并行系统中，这种并行算法可以 取得很好的并行效率。 3.2 任务池方法任务池方法 在上面的例子中，总的间隔数是 n。现在我 们把总计算任务平均分成 ntask 个子任务，每个 子任务的间隔数为 npart=n/ntask。这就相当于把 0,1区间平均分成 ntask 个小区间， 且第 j 个区间 （j=1,2,.,ntask）的限为(j-1)*npart*h,j*npart*h。 这样，积分计算就可以表示为： =+=+=ntaskjhnpartjhnpartjxdx xdx1*)1(210214 14 从而近似值 =+=+=ntaskjnpartjnpartjiixhI1*1*)1(214式中，=h*(j-1)*npart+i-0.5。这种划分可以用图 5 形象地表示。