一种优化多任务间通信能耗的作业调度方法

摘要

本发明涉及一种优化多任务间通信能耗的作业调度方法：一：将用户提交的作业划分为具有依赖关系的多个独立任务，形成标准DAG图模型；二：根据DAG图获知任务的前驱、后继信息，为每个任务设置一个信息表和一个通信队列；三：当系统中某任务A运行完成时，如任务A没有后继任务表示该作业运行完毕；否则将其后继任务的信息表中任务A的运行完成标识位置1，同时将该任务A插入其后继任务的通信队列中；四：对于某任务B，若当前通信链路空闲，从通信队列中依次调度任务B的前驱任务与任务B进行通信；通信完成后将任务B的信息表中相应前驱任务通信完成标识位置1；五：当某任务的信息表中所有通信完成标志位均为1时，开始运行该任务。

权利要求

1.一种优化多任务间通信能耗的作业调度方法，调度步骤为：步骤一：将用户提交的作业划分为具有依赖关系的多个独立任务，即形成标准DAG图模型；

步骤二：根据DAG图获知任务的前驱、后继信息，为每个任务设置一个信息表和一个通信队列；信息表包括该任务的前驱任务、后继任务、前驱任务运行完成标识位和前驱任务与该任务通信完成标识位；通信队列中存放等待与该任务通信的前驱任务；两项标识位均初始化为0；

步骤三：当系统中某任务A运行完成时，如任务A没有后继任务表示该作业运行完毕；

否则将其后继任务的信息表中任务A的运行完成标识位置1，同时将该任务A插入其后继任务的通信队列中；

步骤四：对于某任务B，若当前通信链路空闲，从通信队列中依次调度任务B的前驱任务与任务B进行通信；通信完成后将任务B的信息表中相应前驱任务通信完成标识位置1；

步骤五：当某任务的信息表中所有通信完成标志位均为1时，开始运行该任务。

说明书

一种优化多任务间通信能耗的作业调度方法

技术领域

[0001] 本发明涉及一种计算机机群中多任务调度系统，特别是对具有依赖关系的任务间通信进行管理，具体是指一种优化多任务间通信能耗的作业调度方法。属于计算机机群系统领域。

背景技术

[0002] 机群(cluster)系统是互相连接的多个独立计算机的集合，这些计算机可以是单机或多处理器系统(PC、工作站或SMP)，每个结点都有自己的存储器、I/0设备和操作系统。机群对用户和应用来说是一个单一的系统，它可以提供低价高效的高性能环境和快速可靠的服务。机群以其卓越的性能价格比和良好的扩展性成为了当今高性能计算的主流体系结构。

[0003] 作业调度系统将机群计算环境中的计算资源整合起来，合理调度作业，充分利用机群计算资源，提高系统的利用率。因此成为机群计算环境的核心和灵魂。近几年来，有关作业调度系统的研究主要集中在提高性能和降低能耗两个方面。机群中作业运行耗能主要包括作业运行在处理器上的计算耗能和处理期间作业通信耗能。对于通信密集型作业，后者占据了相当大的比重。

[0004] 目前，大部分的以降能耗为目的的作业调度方法集中在如何降低作业运行过程中的处理器耗能，而忽略了作业间的通信耗能。鉴于此，本发明设计并实现了一种计算机机群中多任务调度系统，特别是对具有依赖关系的多任务间通信进行管理。

发明内容

[0005] 本发明的目的是提供一种优化多任务间通信能耗的作业调度方法，具体而言是一种在计算机机群系统中，对具有多任务间通信特征的作业进行调度的方法，用于解决具有依赖关系的多任务间通信因不能完全并发而进行通信资源争夺，进而使得并行应用程序调度周期增加，系统能耗增大的问题。

[0006] 首先定义如下：

[0007] 定义1：在DAG(Directed Acyclic Graph，即有向无环图)图中，如果某项任务的运行依赖于另外一项任务的计算结果，则称该另外一项任务为该某项任务的前驱任务，该某项任务为该另外一项任务的后继任务。没有前驱任务的任务称为源点(source)任务，没有后继任务的任务称为汇点(sink)任务。

[0008] 因此一个任务可以有0或1或多个前驱任务；同样，一个任务可以有0或1或多个后继任务。标准的DAG图有且仅有一个源点任务和一个汇点任务。

[0009] 根据上述目的，本发明的技术方案如下：

[0010] 将用户提交的并行应用程序(作业)划分为若干个独立的子任务，分配到机群的不同节点上。位于不同节点上的任务间通信遵循下述调度方法。

[0011] 本发明的调度步骤为：

[0012] 步骤一：将用户提交的作业划分为具有依赖关系的多个独立任务，即形成标准DAG图模型。

[0013] 步骤二：根据DAG图获知任务的前驱、后继信息，为每个任务设置一个信息表和一个通信队列。信息表包括该任务的前驱任务、后继任务、前驱任务运行完成标识位和前驱任务与该任务通信完成标识位。通信队列中存放等待与该任务通信的前驱任务。

[0014] 步骤三：当系统中某任务A运行完成时，如任务A没有后继任务表示该作业运行完毕。否则将其后继任务的信息表中任务A的运行完成标识位置1，同时将该任务A插入其后继任务的通信队列中。

[0015] 步骤四：对于某任务B，若当前通信链路空闲，从通信队列中依次调度任务B的前驱任务与任务B进行通信。通信完成后将任务B的信息表中相应前驱任务通信完成标识位置1。

[0016] 步骤五：当某任务的信息表中所有通信完成标志位均为1时，开始运行该任务。

[0017] 本发明一种优化多任务间通信能耗的作业调度方法，其优势在于：(1)目前大部分以降功耗为目的的作业调度方法，只考虑任务在处理器上运行产生的能耗，而忽视了分配到不同处理器上的任务间通信产生的能耗。本发明中的方法弥补了这一不足。(2)本发明中提出的通信队列使得任务间有序通信，保证了最小的作业调度长度(schedule length)，从而达到低功耗的目的。

附图说明

[0018] 图1是用户提交的作业划分后形成的标准DAG图。

[0019] 图2是本发明流程图。

具体实施方式

[0020] 为了使本发明所述方法更加清晰，以下举实例并参照附图，对本发明进行进一步详细说明。

[0021] 步骤一，将用户提交的作业进行划分，形成标准DAG型任务关系图。如图1所示，每个任务可以有多个前驱任务和多个后继任务。其中A1是源点(source)任务，E1是汇点(sink)任务。

[0022] 步骤二，根据DAG图获知任务的前驱、后继信息，为每个任务设置一张信息表。如表1所示，任务的信息表中包含四项信息。图中“-”表示任务的前驱任务和后继任务，由DAG图得到。两项标识位均初始化为0。信息表长度由任务的实际前驱(或后继)任务个数决定。

[0023]

[0024] 表1

[0025] 以C2为例，信息表如表2所示：

[0026] C2的后继任务是D1和E1。C2的前驱任务是B1和B2。相应的前驱任务完成标识位均为1，表示B1和B2均运行结束。B1对应的通信完成标识位为1，表示B1已完成和C2的通信。B2对应的通信完成标识位为初始化状态，表示B2尚未与C2通信。

[0027]C2的后继任务 D1 E1
C2的前驱任务 B1 B2
前驱任务完成标识位 1 1
通信完成标识位 1 0

[0028] 表2

[0029] 其中前驱任务完成标识位和通信完成标识位均初始化为0。

[0030] 通信队列保证先执行完的前驱任务先通信，避免多个任务争夺通信资源。

[0031] 步骤三，假设目前任务B1运行完毕，则根据B1信息表获知其后继任务是C1和C2。修改C1和C2信息表中，前驱任务B1所对应的前驱任务完成标识位为1，并将B1插入C1和C2的通信队列中等待通信。

[0032] 步骤四，待B1和C1通信完成后修改C1信息表中B1所对应的通信完成标识位为1。同样地，待B1和C2通信完成后修改C2信息表中B1所对应的通信完成标识位为1。

[0033] 步骤五，若C2信息表中所有前驱任务的通信标识位均为1时，C2便开始执行。

[0034] 图2所示为本发明流程图，完整的表达了从步骤一到步骤五的全过程。