计算机研究与发展
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999　Vol.36　No.7　P.805-812



总线互连机群系统上的静态任务调度
章军　冯秀山　韩冀中　韩承德
摘　要：与大规模并行处理(MPP)系统相比，基于总线互连的机群(cluster)系统是一种较为廉价的并行计算环境.文中提出了一个基于总线互连机群系统上的静态任务调度算法.该算法具有3个主要特点：(1)由于不同处理机之间的通信都必须通过共享总线，故在调度时将总线与处理机一样看成是资源加以分配；(2)针对总线适合于广播的特点，在调度中考虑了广播，对于某些应用而言可以大大减少通信次数；(3)在确定任务在某个处理机上的开始执行时间以及消息占用总线的开始时间时，选用了最早空闲时间空隙.最后，分别给出了Gauss-Jordan消去法与LU分解的任务图及其调度结果.
关键词：静态任务调度，机群，有向无环图，任务优先级表，空闲时间空隙
分类号：TP301.6
STATIC TASK SCHEDULING FOR CLUSTERS
INTERCONNECTED BY BUS
ZHANG Jun
(Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080)
FENG Xiu-Shan
(Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080)
HAN Ji-Zhong
(Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080)
HAN Cheng-De
(Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080)
Abstract：Compared with massively parallel processing(MPP) systems, a cluster, which consists of several computers interconnected by a bus, is a very cheap parallel computing environment. This paper proposes a novel scheduling algorithm for clusters interconnected by bus. In general, the algorithm has three main features: (1) Shared bus is treated as a resource being allocated to messages just like processors to tasks； (2) Broadcast is considered which can decrease communication times greatly in some cases, and (3) The earliest idle time slot is exploited when determining the start time of a task on a processor and that of a message on the bus. Finally, the schedule results of the Gauss-Jordan elimination method and LU decomposition are given and analyzed.
Key words：static task schedule, cluster, DAG, task priority list, idle time slot▲
1　引言
　　随着微处理器性能以及网络通信带宽的显著提高，基于总线互连的机群系统正成为适合于某些应用的较为廉价的并行计算环境.
　　为了使并行程序在机群系统上能得到高效地执行，必须采用合理的调度技术将不同的任务在适当的时刻分配给处理机去执行.对于静态任务调度而言，处理机分配给任务是在程序执行之前完成的.有关任务的计算量、任务之间的依赖关系及通信情况、每个处理机的处理能力以及它们之间的互连拓扑在编译时假定是已知的.另外，任务一旦分配给某个处理机，便只能在该处理机上执行，即任务的执行是非抢占式的(nonpreemptive).一般说来，静态调度的主要目标是最小化整个应用程序的执行时间.
　　近年来，机群计算(cluster computing)正成为网络并行计算研究的热点，主要原因有如下几点：(1)只需两个或多个工作站(PC机)经网络互连便可形成机群系统，几乎无需额外投资.机群系统为并行计算研究提供了廉价的计算环境，而这种计算环境以前只有在昂贵的并行机上才具备；(2)稳健/可靠的机群软件容易获取，如MPICH与PVM等；(3)已经出现了一些用于互连多个计算机的快速网络，如ATM/Sonet,HiPPi,Token Ring或FDDI等.
　　本文的工作给出了基于总线互连机群系统上的静态任务调度.内容的介绍分3个部分，第一部分介绍了调度系统模型.第二部分首先讨论了调度算法中的几个关键问题的解决方案，然后给出了调度算法；第三部分分别给出了Gauss-Jordan消去法与LU分解任务图及其调度结果.
2　调度系统模型
　　调度系统模型包含任务模型与处理机模型.本节还将给出基于此处理机模型的静态任务调度问题的形式化描述.
2.1　任务模型
　　通常，任务依赖图是经程序划分后获得的，可用图理论中的有向无环图(directed acyclic graph，DAG)来表示，任一有向无环图可用四元组TG=(V,E,A,D)来定义.其中，
　　(1) V=［vi］表示任务图中结点①的集合，vi表示第i个任务，|V|表示图中结点数目；
　　(2) E=［ei,j］表示任务图中边②的集合，ei,j表示由vi指向vj的有向边，|E|表示图中边的数目；
　　(3) A=［ai］表示任务的计算量集合，ai表示任务vi的计算量；
　　(4) D=［di,j］表示任务之间通信的数据量集合，di,j表示任务vi发送给任务vj的数据的大小.
　　在图1(a)中，对于任意结点，上面的记号表示该结点的名称，下面的数值表示该结点的计算量大小，任务与任务之间的通信关系用有向边来表示，有向边上的数值表示通信的数据量大小.另外，图中的bcst1表示任务v1向任务v2,v3,v4,v5广播数据，bcst2与bcst3的含义类推.

　　　　
图1　调度系统模型
　　为了表示任务之间的互相依赖情况，下面定义图TG上的两个优先(precedence)关系及：
　　定义1. 在图TG上，如果vi是vj的父结点(或vj是vi的子结点)，则有vivj；如果vi是vj的祖先结点(或vj是vi的子孙结点)，则有vivj.
　　由以上定义可知，关系具有传递性，而关系不具有传递性.ei,j∈E等价于vivj.在图1(a)中，有v1v2，v1v6等满足上述两个关系.
　　在下文中，由任务vi的父结点和祖先结点构成的集合分别记为PARENT(vi)与PRED(vi)，而由任务vi的子结点和子孙结点构成的集合分别记为CHILD(vi)与SUCC(vi).
　　定义2. 在任务图TG中，某两个任务vi与vj是相互独立的(independent)，当且仅当viPRED(vj)且viSUCC(vj)；否则vi与vj是相互依赖的(dependent).
　　在任务图TG中，如果两个任务是相互独立的,则它们可以并行地执行,否则,只能串行地执行.
　　定义3. 对于任务vi，若PARENT(vi)=,则vi称之为入结点(entry node),记集合ENTRY=｛vi| PARENT(vi)=｝；若CHILD(vi)=,则vi称之为出结点(exit node), 记集合EXIT=｛vi| CHILD(vi)=｝.
　　在图1(a)中，ENTRY=｛v1｝,EXIT=｛v11｝.
　　这种任务执行模型又称之为编译时的宏数据流模型(compile time macro data flow model)［1，2］.在该模型中，每个任务只有在它所需要的数据到齐后，才可以开始执行，即任务的开始执行是以它所需要的数据的到齐驱动的，每个任务的执行都是非抢占式的，任务执行完后，立即将其后代所需要的数据发送给它们.
2.2　处理机模型
　　本文中假定所有的处理机均同构.对于任一以总线互连的机群系统，其中，
　　(1) P=［pi］表示所有处理机的集合，pi表示第i个处理机，|P|表示处理机的数目；
　　(2) bus为连接多个处理机的共享总线.
　　在图1(b)中，给出了一个由3个处理机通过同一条总线互连而成的机群系统.
　　在本文中，假定每个处理机的运算速度为s，则任务图TG中任务vi的计算时间.在不存在总线争用(bus contention)的情况下，若任务vi向任务vj发送数据量的大小为di,j，通信延迟可用式 来计算，其中，α，β分别表示通信时的启动开销、总线的数据传输率.
　　本文中，假定总线是半双工的(half duplex)，即在总线上，一次只能允许一个通信事务(communication transaction)的发生.并且，在总线上发生的通信是可靠无差错的.另外，每个处理单元都带有专门的硬件来支持通信，这样的部件称为I/O处理机.这种I/O处理机允许任务的通信与计算重叠(overlapping)地进行，即一个主处理机向另一个主处理机发送消息时，该主处理机只需向其相应的I/O处理机发出发送消息的请求，然后立即开始下一个任务的计算工作，而不是在确认消息已经被接收后，再开始下一个任务的计算，具体消息的发送是由I/O处理机完成的.另外，当主处理机在运行时，由I/O处理机负责接收来自其它处理机发送来的消息.
2.3　调度问题的形式化描述
　　在以总线互连的机群系统上，调度的含义有两个方面，一方面是将任务分配给处理机去执行，另一方面是将总线分配给消息去使用.形式地，某个调度可用函数f来表示，该函数的定义域为V∪E，值域为P×［0,∞)∪［0,∞).对于某个任务vi∈V，如果f(vi)=(pj,t)，我们便称之为，任务vi被调度到处理机pj上，并在t时刻开始执行；对于某个消息ei,j,如果f(ei,j)=t，则表示在t时刻总线可以分配给该消息ei,j使用.
　　对于以总线互连的机群系统，总线是有限的资源，很有可能出现不同的消息同时争用共享总线的情况.因此，如果将总线也作为资源来静态地加以分配，在程序运行时，便不再需要考虑总线争用问题的出现.
　　衡量调度性能的最主要的指标是调度长度(schedule length，文献［1］、［2］中又称之为Parallel Time,简称PT)，调度f的调度长度PT(f)=max｛t+τi｝，其中f(vi)=(pj,t)，且τi=ai/s.辅助指标有算法的复杂度及需要使用的处理机的个数等.
　　定义4. 在由无限数目的处理机构成的完全互连同构系统上，若将任务图TG中不同的任务映射到不同的处理机上，任务图TG中的静态关键路径(static gritical path,记作SCP)定义为从入结点到出结点中最长的路径(包含任务之间的通信时间).任一结点vx的top level(记作tlevel)定义为从入结点到该结点(不包含该结点的权)的最长路径的长度(记作tlevel(vx)).任一结点的bottom level(记作blevel)定义为从该结点到出结点(包含该结点的权)的最长路径的长度(记作blevel(vx)).
　　在下文中，由静态关键路径上的结点构成的集合记为SCPN.对于图1(a)，在处理机个数等于11的全互连同构系统上，当不同的任务被映射到不同的处理机上时，若s=1,α=0,β=1,则该任务图中的静态关键路径为v1v4v7v9v11，即图1(a)中的粗黑线,SCPN=｛v1,v4,v7,v9,v11｝.
　　在由无限数目的处理机构成的完全互连同构系统上，若将任务图TG中不同的任务映射到不同的处理机上，SCP的长度为maxvx∈V｛tlevel(vx)+blevel(vx)｝，任意结点vi的tlevel与blevel的计算方法如下:

　　直观地，一个结点的tlevel值越小，则说明该结点越有可能先被调度；一个结点的blevel值越大，则说明该结点越应先被调度.
3　调度算法介绍
　　就作者们所知，在目前发表的为数不多的基于非完全互连系统上的静态任务调度文章［3，4］中,尚没有一篇文章讨论基于总线互连机群系统上的静态任务调度问题.本文中所讨论的基于总线互连的机群系统上的静态任务调度算法至少有两点不同于其他非完全互连系统上的静态任务调度算法.第一，由于总线适合于广播，在调度中考虑了广播问题③，对于某些应用而言可以大大减少通信次数；第二，在确定消息占用总线的开始时间时，选用了最早空闲时间空隙.
　　在下文给出的调度算法中，直接将实际的处理机与总线看成是资源，任务与消息看成是消费者，同时考虑如何将处理机分配给任务以及如何将总线分配给消息.
　　基于总线互连机群系统的静态任务调度中要解决的问题有3个：如何顺序选择参与调度的任务；如何将总线的空闲时间空隙分配给消息；以及如何将处理机分配给任务.下面将讨论这3个问题的解决方案，最后给出调度算法.
　　(1) 如何顺序选择参与调度的任务
　　本文中总是优先调度关键路径上的任务.在确定关键路径时，有些算法采用的是静态关键路径，而有些算法采用的是动态关键路径.通常，后一类算法产生的调度长度短于前一类算法产生的调度长度，但前一类算法的复杂度低于后一类算法的复杂度.在本文中，为了降低算法的复杂度，采用的是静态关键路径.对于非关键路径上的任务总是优先考虑slevel=blevel-tlevel值越大的任务.在任务调度中，任务的选择总是按拓扑顺序进行的.在下面的算法中给出了一个建立任务优先级表的算法.在算法的实现中，需增加两个虚结点，通过第一个虚结点(即下面算法中的v0)可以访问所有的入结点，通过第二个虚结点可以访问所有的出结点.
　　算法1. 创建任务优先级表
　　① 从集合｛vi|v0vi∧vi∈SCPN｝中选择任一结点ve，使之成为任务优先级表中第一个任务.
　　② 从结点ve的子结点中选择一个位于静态关键路径上的结点作为下一个候选结点vi，如果有多个这样的子结点，则选择与结点ve有最大通信的子结点.
　　③ if结点vi 的所有父结点都在任务优先级表中then
　　④ 将结点vi置于任务优先级表的表尾.
　　⑤ else
　　⑥ 假定vj 是结点vi的那些不在任务优先级表中的父结点之一且vj在这些父结点中具有最大的slevel值.如果有多个这样的父结点，则选择与结点vi有最大通信的结点.如果vj的父结点都在任务优先级表中,则将结点vj置于任务优先级表的表尾.否则递归地将vj的所有父结点放入到任务优先级表中.
　　⑦ 重复第⑥步直到vi的所有父结点都在任务优先级表中，再将vi置于任务优先级表的表尾.
　　⑧ end if
　　⑨ 从结点vi的子结点中选择一个位于静态关键路径上的结点作为下一个候选结点vi，如果有多个这样的子结点，则选择与结点vi有最大通信的子结点.
　　⑩ 重复③～⑨步，直到所有的结点进入任务优先级表.
　　很容易证明，由以上算法建立的任务优先级表总是满足拓扑顺序的，因为每个任务只有在它所有的父任务入表后，才入表.对于图1(a),在s=1,α=0,β=1时,建立的任务优先级表为v1,v4,v2,v7,v3,v6,v9,v5,v8,v10,v11.
　　(2) 如何将总线的空闲时间空隙分配给消息
　　在本文中，消息使用总线服从先来先服务的排队原则.在确定消息使用总线时，选用的是最早空闲时间空隙.
　　下面给出消息ei,j可以使用总线的最早时间ST(ei,j)的计算方法.假定任务vi被调度到处理机pm上执行，而任务vj被调度到处理机pn上执行且pm≠pn，FT(vi,pm)为任务vi在处理机pm上的完成时间.另外，此前已有δ个消息｛msg1,msg2,…,msgδ｝要求使用总线，它们所占用的时间空隙ITS(bus)=［η1,ζ1］∪［η2,ζ2］∪…∪［ηδ，ζδ］.因为存在一些k满足下式，
　　(1)
其中，k=0,…,δ，ζ0=0，ηδ+1=∞.
　　可知,至少k=δ是满足不等式(1)的，假定l是所有k中满足上述不等式的最小值，则
ST(ei,j)＝max｛ζl,FT(vi,pm)+α｝　　(2)
　　则消息ei,j到达处理机pn的时间
　　(3) 如何将处理机分配给任务
　　本文中主要考虑选择使任务最早开始执行的处理机.
　　下面给出任务vi在处理机pm上的最早开始执行时间ST(vi,pm)的计算方法.定义LDAT(vi,pm)为任务vi被调度到处理机pm上时，消息集合｛ex,i|vxvi｝中最晚到达处理机pm的消息到达的时间.假定在任务vi分配给处理机pm时已有δ个任务｛vm1,vm2,…,vmδ｝要求顺序使用处理机pm.因为存在一些k满足下式，
　　(3)
其中，k=0,…,δ，ST(vm0,pm)=0，ST(vmδ+1,pm)=∞.
　　可知,至少k=δ是满足不等式(3)的，假定l是所有k中满足上述不等式的最小值，则
ST(vi,pm)=max｛ST（vml,pm）+τml,LDAT(vi,pm)｝　　　(4)
　　在图2中，假定已有任务v1,v2,v3,v4调度到处理机p上，若将任务v5调度到处理机p上时，任务v5所需要的数据最晚到达处理机p的时刻为1.3.现在，任务v5的执行时间为0.5，而处理机p上存在的空闲时间空隙为［1.7,1.9］,［2.5,3.1］及［5.1,∞］，则任务v5在处理机p上的最早开始时刻为2.5.在下文中，记处理机p上的空闲时间空隙集合为ITS(p)，记P(vi)为分配给任务vi的处理机.


图2　任务如何占用处理机上的最早空闲时间空隙
　　其实，将总线上的最早空闲时间空隙分配给消息的思想与将处理机上的最早空闲时间空隙分配给任务的思想是类似的.
　　在解决了以上3个问题后，下面给出调度算法的描述.
　　算法2. 调度算法
　　(1) 初始化.
　　　　① vi∈V,计算 tlevel(vi), blevel(vi), slevel(vi)；
　　　　② 计算任务图的串行计算时间；
　　　　③ pi∈P，赋ITS(pi)为［0,∞］；
　　　　④ 对于总线，赋ITS(bus)为［0,∞］.
　　(2) 创建任务优先级表.
　　(3) 从任务优先级表中取第一个任务，假定它为vj并将被调度到处理机pn上,vi∈V∧vivj, 计算ST(ei,j)与RT(ei,j).具体分3种情况来考虑：
　　　　① 若pn=P(vi)，则RT(ei,j)=ST(ei,j)=FT(vi,P(vi)).
　　　　② 若ei,j是广播消息.如果消息ei,j已被广播，则RT(ei,j),ST(ei,j)已被计算；否则广播消息ei,j，并根据式(1)、(2)计算ST(ei,j)，从而算得RT(ei,j).
　　　　③ 直接根据式(1)、(2)计算ST(ei,j)，从而算得RT(ei,j).
　　(4) 根据所有的RT(ei,j)，计算LDAT(vj,pn)=maxvivj｛RT(ei,j)｝，再根据式(3)、(4)计算ST(vj,pn).
　　(5) pn∈P，根据(3)～(4)步计算ST(vj,pn).设ST(vj,pc)=minpn∈PST(vj,pn).如果有多个处理机满足此条件，则任选其中一个处理机作为pc.
　　(6) 计算任务vj在处理机pc上的完成时间FT(vj,pc) ，如果 FT(vj,pc)超出了程序的串行时间，则将所有的任务调度到一个处理机上去执行并退出调度.
　　(7) ①修改 ITS(pc)；
　　　　② 修改 ITS(bus)；
　　　　③ 从任务优先级表中将任务vj删除.
　　(8) 重复(3)～(8)步，直到所有的任务都调度完毕.
　　在图1中，将(a)图的任务图调度到(b)图中的以总线互连的机群系统上时，根据以上调度算法产生的实际调度结果见图(c)，在该图中，分别给出了处理机与总线的使用情况.例如，任务v3在1时刻被调度到处理机p2上执行，消息e8,10在时间［5,5.4］使用总线.由调度结果可知，该任务图的串行执行时间为22，不考虑任务之间通信时间的最大路径长度④为11.5，本算法产生的调度长度为13.值得指出的是，任务v5被插到任务v4与任务v7之间并紧随任务v4之后执行，另外，消息e5,8被插到bcst2之前使用总线.
　　在上述算法中，最主要的时间花在(3)～(7)步.对于每个任务，都要计算该任务在每个处理机上的最晚消息的到达时间以及寻找相应的最早空闲时间空隙.故该算法的复杂度为O(｜V‖E‖P｜).
4　模拟试验
　　Gauss-Jordan消去法与LU分解是两种较为常见的数值计算方法.在以下试验中，假定处理机的运算速度为50Mflops，浮点加减与乘除均花费一个时钟周期.另外，通信时的启动开销为0.5ms，总线的数据传输率为每秒100,000个浮点数.下面给出它们的任务图及调度结果.
4.1　Gauss-Jordan消去法
　　图3(a)是在不考虑选主元情况下Gauss-Jordan消去法的DAG图.假定该矩阵大小为10000×10000，分块矩阵的大小为200×200，故在该任务图中共有1327个任务.图中每个任务的计算量大小以及任务之间通信量的大小可由手工分析得出，计算获得任务图的串行执行时间为 18835.06s ，由入结点到出结点中不考虑任务之间通信时间的最大路径长度为768.68s.在图3(b)中，任务vi+1i向所有的任务vji+1(其中，0≤i≤49,i+1<j≤51)广播相同的数据.如能利用广播，在最好可能情况下，节省的通信次数可为1225次.在图4(a)中，给出了运行调度程序获得的加速比与处理机个数的关系图，其中加速比等于串行时间除以调度长度.总的来说，由于利用了广播，节省了通信次数，随着处理机个数的增加，加速比呈线性增长的趋势并逐渐减慢.如果不利用广播，在处理机个数为2时调度获得的加速比最大，仅为1.48.此后，即使增加处理机个数，加速比也不能增加，因为总线已成为通信的瓶颈.


图3　Gauss-Jordan消去法的任务图(a)与LU分解的任务图(b)


图4　Gauss-Jordan消去法的调度结果(a)与LU分解的任务图(b)
4.2　LU分解
　　图3(b)是在不考虑选主元情况下LU分解［5］的DAG图.假定该矩阵大小为10000×10000，分块矩阵的大小为200×200，故在该任务图中共有1275个任务.图中每个任务的计算量大小以及任务之间通信量的大小可由手工分析得出，计算获得任务图的串行执行时间为13337.62s，由入结点到出结点中不考虑任务之间通信时间的最大路径长度为606.41s.在图3中，任务vii向所有的任务vji(其中，1≤i≤49,i+1 ≤j ≤50)广播相同的数据.如能利用广播，在最好可能情况下，节省的通信次数可为1176次.在图4中，给出了运行调度程序获得的加速比与处理机个数的关系图.总的来说，随着处理机个数的增加，加速比呈线性增大的趋势并逐渐减慢.另外，图中还出现了波动现象.经分析，这是因为在处理机个数较多时，一开始任务便分散到不同的处理机上去，导致以后调度产生的通信开销较大.如果不利用广播，在处理机个数为2时调度获得的加速比最大，仅为1.64.
5　结束语
　　任务调度问题是经典的NP问题.本文首次给出了一个基于总线互连机群系统上的静态任务调度算法并首次在任务调度中考虑了广播问题.文章的最后分别给出了Gauss-Jordan消去法与LU分解的任务图及相应的调度结果.通过模拟试验表明，虽然总线在并行计算中往往容易成为通信的瓶颈，但如能充分利用总线的广播特性，对于像Gauss-Jordn消去法及LU分解这样的算法，仍能取得满意的性能.■
①任务图中的结点即指任务，故在本文中有时结点与任务混用
②任务图中的边即指消息，故在本文中有时边与消息混用
③文献［2］在代码生成阶段考虑广播问题，而本文是在调度阶段考虑广播问题的.
④这是调度的极限，即使最优调度长度也不能小于此值.
基金项目：本课题得到国家自然科学资金(项目编号 69896250)与“九五”中国科学院基础性　　　　　　研究重大项目(项目编号 KJ-951-B1-703)的资助.
作者简介：章军，男，1971年3月生，博士研究生,主要研究方向为并行计算、并行任务调度、　　　　　　计算机体系结构等.
　　　　　冯秀山，男，1973年11月生，硕士研究生,主要研究方向为数字信号处理、计算机　　　　　　体系结构等.
　　　　　韩冀中，男，1972年7月生，博士研究生,主要研究方向为数字信号处理、计算机体　　　　　　系结构等.
　　　　　韩承德, 男，1940年4月生，研究员, 博士生导师,主要研究方向为计算机体系结　　　　　　构、计算机并行处理、多媒体技术等.
作者单位：章军(中国科学院计算技术研究所　北京　100080)
　　　　　冯秀山(中国科学院计算技术研究所　北京　100080)
　　　　　韩冀中(中国科学院计算技术研究所　北京　100080)
　　　　　韩承德(中国科学院计算技术研究所　北京　100080)
参考文献：
［1］Hwang J J et al. Scheduling precedence graphs in systems with interprocessor communication times, SIAM J Comput, 1989, 18(2): 244～257
［2］Yang T et al. PYRROS: Static scheduling and code generation for message passing multiprocessors. In: Proc 6th ACM Int Conf SC '92, 1992. 428～437
［3］Hesham El-Rewini et al. Scheduling parallel program tasks onto arbitrary target machines. Journal of Parallel and Distributed Computing, 1990, 9: 138～153
［4］Yu-Kwong Kwok et al. Bubble scheduling: A quasi dynamic algorithm for static allocation of tasks to parallel architectures. In: IEEE Symposium on Parallel and Distributed Processing, 1995. http://www.cs.ust.hk
［5］Dongarra J J, Walker D W. Constructing numerical software libraries for high performance computer environments. In: Albert Y H Zomaya ed. Parallel & Distributed Computing Handbook. New York: McGraw-Hill. 1996: 917～954
收稿日期：1998-10-27
修稿日期：1999-03-29
