并行计算调度算法模型的研究.pdf

并行计算调度算法模型的研究，
韩建枫
(天津大学系统工程研究所天津300072)

摘要并行计算中的调度问题为典型的NP完全问题，很多调度算法的优异性能均以对调度问题的诸多
限制条件为前提。因此，如何针对调度问题建立一个系统模型用以表示各种调度方法的诸多限制条件，成
为一个重要问题。本文首先给出了处理机模型、任务模型，并在此基础上提出了调度算法模型，同时给出
了墓J几该模型的常见约束条件。

关健词调度算法，模型，并行计算

1引言

由于并行计算的调度问题为典型的NP完全问题P1，所以目前研究出的调度算法多为各式
启发性算法和包含各类约束条件的近似算法。它们大多呈现出以下特点:①约束条件多元化。
基于不同的信息了解程度(如处理器速度、内存特征等)研制不同的调度算法，事先为调度
算法规定了各种约束条件，增加或改变一种约束条件就派生出一种调度算法。这类调度算法
往往具有很强的针对性和很好的应用效果，但同时针对性越强，其可移植性就越差。如果不
能精确满足这些约束条件，这类算法的性能通常会急剧下降甚至失效。②调度目标多元化。
不同调度算法在调度的过程中，追求不同的调度目标。例如:追求设备利用率的负载平衡目
标;追求单作业最快运行时间的最小调度长度目标[21;追求最小价值调度目标[31等。
考虑一个实际应用场合，它们在不同时间会执行不同类型的应用，各阶段的系统条件和
约束条件各不相同。而设备提供商与计算客户之间也会在提高设备利用率、缩短作业运行时
间、减少计算代价等多个目标上折中选择。因此，在一个开放的并行计算环境中，迫切需要
一个可以清晰描述各种应用约束条件的调度算法模型。它不但应反映出保证某调度算法执行
效率的诸多约束条件，同时也可量化出某调度算法在执行中追求的调度目标。
本文首先给出了处理机模型、任务模型，并在此基础上定义了调度算法模型，同时给出
了基于该模型的常见约束条件。

T处理机、任务模型

一个完整的并行计算环境可抽象为处理机模型和运行在其上的任务模型[41表示。
1)处理机模型可抽象为五元组PG=(P,L,S,1,R)表示。其中:P={p[i];iE[1,M])表示所有处理
机的集合，M代表有效处理机数目;L={1[i,j];i,jE[1,M],1[i,j]E{0,1]]表示p[i]到p[j]是否

‘本文研究受国家自然科学基金项目资助(No.69974026)韩建枫，男1970年生，博士研究生，主要研究方向为并行计算和并行
调度算法

刀
汤刃
份了
具有直接连接;S={S[i];i〔[1,M]}表示凤i]运算速度;I={a[i],iE[1,M]}表示p[i]进行数据
通讯时启动工/0设备的时间开销;R={r[i,j];i,jE[1,M]]表示p[il到p[jl的数据传输速率。
2)任务模型可抽象为任务属性和有向无环图DAG。任务属性刻画了建立DAG任务划分之前的基
本假设，例如SPMD通常要求数据可划分性，MPSD通常反映任务的程序粗粒度可划分性等，
一些静态调度算法和执行时刻进行编译的实现机制(如JAVA,SQL嵌入等)经常参考该属性，
如将负载的可任意划分性作为算法前提条件[".DAG以四元组TG=(V,E,A,D)表示，其中
V={v[i];iE[1,N]}为所有任务的集合，N为任务总数;E={e[i,j];i,je[1,N],e[i,j]E{0,1)}表
示V[i]到V[j]是否存在偏序关系;A={a[i];i司1,Nl)表示第，川个任务的计算量:
D={d[i,j];i,jE[1,N]}表示d[i]到d[j]间需要传递的通讯量。由于不同任务粒度的主要区别
在于D，因此，该模型的三元组形式TG=(V,E,A)也可用来描述多作业模型。
在动态调度情况下，要得到上述模型的全部参量较为困难，因此不同动态调度算法通过
系统监测、估算、预测、经验和各类启发信息得到上述模型中的部分非精确参数。

3调度算法模型及其约束条件

一种任务调度算法等价于建立TG到PG映射的一种策略。调度结果则表示为一个带时序
的TG到PG映射子集。由于调度问题属NP完全问题，且TG到PG存在巨大的映射空间，因
此各调度算法为追求其在某一目标下的效率和实例化，往往通过各种约束条件对完整的映射
空间进行约束，然后在上面实现各自的调度算法。这类约束通常表现为如下形式的组合:
1)对PG进行约束。常见的约束形式有:
.针对机群系统，可对PG模型进行如下约束:①机群调度为非拓扑结构调度问题，即
1[i,j)二1(i,jE[1,M]);②通讯过程由1/0设备独立控制，可与计算过程重叠，a[i]是
通讯与运算间唯一需要串行的部分;③由于机群网络传输速度相对较慢，具体到一个作
业调度时，往往a[i]《机群网络传输时间，有时甚至可忽略不计。因此，在如上假