摘要：网格仿真器GridSim以其灵活的使用方式和广阔的应用前景，自2002年公布之后一直备受人们关注。但是，由于其采用面向任务池（task pool）的任务建模方式，使其并不适合于仿真Dag图的调度。为了支持Dag图调度算法的研究，进一步丰富GridSim的功能，此文提出了一种改进GridSim的方法，即P2P的中间数据传输方式，并将改进后的GridSim仿真工具包叫作GridSim4Dag。当前驱子任务执行完毕之后直接将中间结果发送给后继子任务所在的资源以启动后继子任务的执行，从而减少传输时间，降低通许开销、降低通讯出错率。这同时也是一种对网格框架的调整，使得网格直接可以支持Dag任务的调度。
关键词：GridSim；Dag图调度；网格计算；网格调度仿真
中图法分类号：TP311 文献标识码：A 文章编号：1009-3044(2011)01-0077-04
GridSim4Dag: A Simulator of Dag Scheduling with GridSim Toolkit
LI Can, DENG Rong
(High Performance Computing Center, Tongji University, Shanghai 201804, China)
Abstract: Since 2002, GridSim, as a popular grid simulator, received much concern for its flexible use and wide range of apply scenarios. However with the limitation of its modeling pattern of task, it is more practical to simulate scheduling of tasks with task pool pattern than tasks of Dag with predecessor-successor relationship. In order to eich GridSim"s simulation functions to better support simulation scheduling of Dag tasks. An improved internal data transfer method P2P (peer-to-peer) is proposed and implemented in this paper and we call the improved GridSim toolkit GridSim4Dag. In the P2P-internal-data-transfer method, predecessor node direct send internal data to successor when it is finished. In this form, we can decrease transmission time, reduce communication cost and lower the transmission error rate. P2P method is not just for scheduling simulation, it can be used in real Grid architectures so that Dag scheduling can be supported better.
Key words: GridSim; Dag scheduling; Grid computing; Grid scheduling simulation
1 概述
随着P2P网格体系结构的不断成熟，越来越多的工作流系统不再使用Client-Server的方式运行，而更多的采用有向无环图（Directed Acyclic Graph，简称为Dag）的方式表示工作流系统中各种任务之间的前驱后继关系[1]。为了能在异构的网格平台中运行Workflow引擎，我们有必要对Dag图的各种调度算法进行研究，如HEFT (Heterogeneous–Earliest-Finish-Time ) 算法、CPOP (Critical-Path-on-a-Processor) 算法[1]。然而，网格[3]环境相当复杂，设施相当昂贵，普通研究者根本不可能在真实的网格环境中去研究各种调度算法，加之网格系统本身的不确定性和不可重复性[3]，研究者们普遍采用网格模拟器来研究网格的行为，网格模拟器营运而生。
开源的网格仿真器GridSim[4]以其灵活的使用方式和广阔的应用前景备受网格研究者青睐，在我国，仅2006年至今就有56篇以上的文献使用该平台进行仿真实验[5-7]。
但是，GridSim并不适合Dag的调度，原因在于其提供的任务调度建模方式，是针对任务池型任务的，即所有子任务之间相互独立，没有任何前驱后继的依赖关系。其任务调度的基本思想是： 对每一次仿真，用户代理(User Broker)将其中的各子任务顺序发送给各资源，资源运行完子任务后将中间结果发回给用户代理。然而，对有前驱后继关系的Dag图的调度来说，GridSim仍然采用以上的方式来运行，在每一个子任务运行完毕之后，都将其结果发回给用户代理，再由用户代理将中间结果发送给对应的后继子任务[4]。这样，同样的中间数据可能要在网络中传输两次或者两次以上。使用面向任务池任务的调度方式来仿真Dag图任务的运行存在诸多问题：如通讯开销大、仿真时间与调度算法计算的理论值不符、出错率高等。
基于以上分析，本文借鉴peer-to-peer网络的思想，提出并实现了基于GridSim中Dag图任务调度的P2P数据传输方式，使得Dag图任务在GridSim中的调度模拟变得更简便，减小了通讯开销，同时减少运行时间，降低通讯出错率，使得可以完全模拟调度算法中对Dag图子任务的调度。P2P数据传输方法的主要思想是：在Dag图的调度中，每个子任务都保存了其后继子任务所在的资源信息，当某个前驱子任务运行完毕时，直接将中间结果发送给其后继子任务所对应的资源，以唤醒其后继子任务的运行。直到所有的子任务都运行完毕，再将总结果发送给用户代理程序。P2P的方式减少了通讯次数和通讯数据量，从而有效地减少了通讯开销，降低运行时间，降低通讯中数据出错的几率。
本文第2节对GridSim的任务调度模型以及其对Dag图的调度方式进行了详细的剖析。第3节阐述了P2P数据传输方式的基本思想及其运行过程。第4节讲述P2P数据传输方式在GridSim平台上的设计与实现。第5节通过一个实例Dag图，分析其在原始Gridsim下和在改进的P2P传输方式下的仿真结果，证明改进的P2P数据传输方式的优越性以及实现的正确性。第6节对全文进行总结并提出更进一步研究方向。
2 GridSim任务调度方式
2.1 GridSim普通任务调度模型
在GridSim中，仿真过程如下：首先生成资源实体(Grid Resource Entity)和资源信息服务实体（Grid Information Service Entity）；当用户将任务提交给用户代理（User Broker），用户代理查询资源信息服务实体，获取当前可用资源数量及属性；用户代理再将任务的各子任务分别发送给对应资源，资源执行完子任务后，将结果返还给用户代理；待所有子任务执行完毕，用户代理分析各子任务运行结果，收集整理，产生最终结果并返回给用户[8-9]。交互过程如图1所示。
2.2 GridSim中Dag图调度模型
由于GridSim的任务调度室针对任务池任务设计的，并没有对Dag图的调度做任务特殊的处理，仍然采用普通的调度方式对其仿真。当某个子任务执行完毕之后，中间数据将传送个用户代理，再有用户代理将中间结果发送给其后继子任务所在的资源。如此，同样的中间数据在整个网络中传输了两遍，既增加了通讯量，延长了整个Dag图执行的时间（makespan）[1]，同时由于网络传送输的不可靠性，增加了由于数据传输出错而导致整个任务失败的可能性。
试举一例，对如图2所示DAG图，共有三个资源Res1、Res2和Res3，可供使用。假设，子任务T1调度到Res1上，T2调度上Res2上，T3和T4调度到Res3上。那么，它在原始GridSim中仿真的时序图如图3.(a)所示。
其中，当T1执行完毕，将结果D1和D2发送给用户代理，用户代理再将D1发送到Res2 ，D2发送到Res3以唤醒T2和T3的执行，在T2、T3 执行完之后，分别将D3和D4发送给用户代理，用户代理将D3，D4发送给Res3以唤醒T4。直到T4在Res3上运行完毕，将最终结果发送给用户代理。如此，整个任务执行完毕。以这样的方式运行，每个中间结果（D1，D2，D3，D4）在网络上都传输了两遍或，而且传输量还会随着DAG图复杂性的增长成指数级增长。与此同时，数据传输的出错率被成倍地放大了。
3 P2P数据传输模型
对具有前驱后继依赖关系的Dag图，用户只关心整个Dag图运行的最终结果，并不关心每个子任务执行产生的中间结果。基于此，P2P数据传输模型直接将中间数据传输给后继子任务所在资源。从而达到减少通讯开销，降低通讯出错率的目的。如图3（b）所示，在T1运行完毕后直接将中间数据D1和D2发送给Res2和Res3以唤醒T2和T3，当T2运行完毕后，将结果D3发送给Res3以唤醒T4，由于T3和T4同在Res3上执行，故省去D4的传输时间。从图中可知，与GridSim中原始的传输方式相比，中间数据D1，D2，D3都只传输一次，D4甚至不用传输。使用P2P的数据传输方式大大降低了通讯开销、节省了时间、同时也降低了出错率。
4 GridSim中P2P传输模型设计与实现
GridSim仿真平台包括GridResource,和Grid Information Service（GIS），Gridlet等几种基本功能元件[1]，其中GridResource 模拟网格资源。每个网格资源为一个GridResource对象，含多个同构或异构的处理单元，以时分(time shared)或空分(space shared)的方式为网格中的所有用户服务。
GIS模拟网格中的目录服务，是网格的信息中心；所有资源生成之后均需要在GIS上进行登记，供User查询Gridlet 任务。 GridSim仿真环境将任务建模为Gridlet，包含运算量、输入数据量和运行完毕后产生的输出数据量等所有任务属性。
如图4中所示，包gridsim中的类为GridSim提供的原始类，为了扩展GridSim以实现P2P的数据传输，我们扩展了GridSim提供的原始类，如包daggridsim中所示。其中Edge类对Dag图中边建模；DagGridlet 是对Gridlet的扩展，使其包含后继任务所在资源的信息；DagGridResource是对GridResource的扩展。DagSpaceShared是对AllocPolicy的扩展，子任务的发送方式的修改和中间数据的接受及挂起子任务的唤醒都是在DagSpaceShared中实现的。值得一提的是DagGridSimTags，其中只定义个标记，GRIDLET_DATATRANSEFFER，它表示向资源发送消息的类型为中间数据。
4.1 DagGridlet类
GridSim中，使用Gridlet对象对子任务建模，每个Gridlet包含有GridletLength、GridletFileSize和GridletOutputSize等几个域，分别表示子任务的计算量，输入文件大小和输出数据大小。
分析Gridsim对子任务的建模过程，可以看到其不适合DAG图调度的根源在于：Gridsim在设计gridlet数据成员时，将子任务的运行参数gridletLength_和输入输出参数gridletFileSize_、gridletOutputSize_一一对应捆绑在了一起，从而在逻辑上严格对子任务实施了如下限制：
1）每个子任务存在且仅存在唯一的前驱结点、后继结点，即用户代理（实体）。
2）不存在表示当前子任务后继节点所在的资源信息。
为了能够使Gridsim工具包能为Dag图的调度和运行构造仿真环境，特别是创建工作流应用程序的仿真环境。故而本文对Gridsim进行了较大规模的二次开发，将子任务的输入、输出参数从gridlet中剥离出来形成新类Edge，用以对Dag图中的边建模，令gridlet仅描述与计算相关的子任务属性；以达到全面仿真Dag图在分布式环境下运行过程的目的。
Edge作为Gridlet的内部对象，所包含主要属性包括：
1）destGridlet: 表示此边的后继子任务对应的Gridlet编号。
2）destGridResource: 表示此边后继子任务所在的资源号
3）size：边传输数据的大小，表示从此结点到后继结点所需传输的数据量，
由以上对边Edge的定义，我们可以对Gridlet加以改造以适应其在Gridsim中的仿真调度：改造之后的Gridlet我们称之为DagGridlet，它继承了原先Gridsim中gridlet的所有属性及行为，并添加如下主要数据成员：
1）predeceessorNum_: 表示当前子任务结点的前驱子任务任务个数
2）edgeArray_: Edge类型的数组，表示当前节点所有输出边的集合。
4.2 P2P数据传输方式下Dag图执行流程
使用Edge对子任务之间边进行建模，Dag图的执行可以分为如下步骤：
1）使用静态调度算法[10]即所谓的表调度算法，为每个子任务分配合适合适的资源，如HEFT (Heterogeneous–Earliest-Finish-Time ) 算法、CPOP ( Critical-Path-on-a-Processor ) 算法[2]。因为，在Gridlet建立时就需要为其每一条边建立好对应关系，故此处只能使用静态调度算法，在子任务传送到各资源之前，就为其分配好每一个子任务所在的资源，以便在建立Dag图各子任务前驱后继关系时能在destResource_中填入正确的资源编号。
2）使用对应的调度关系，建立DagGridlet，其中包含有此DagGridlet所对应最优资源的资源号、其与后继结点之间的边Edges、此DagGridlet在对应最优资源上的运行时间等信息；
3）将所有的DagGridlet分别发送到各自对应的资源上，我们可以将此步骤定义为部署（ployment）；
4）Dag图各子任务数据传递，当一个子任务运行完毕后，将其数据发送给后继子任务所在的资源并唤醒因等待此子任务而挂起的子任务；
5）当运行到Dag图的出口结点（可能有多个出口结点）时，子任务将最终结果传送给用户代理（User borker）。
6）用户代理根据返回的最终结果，整理产生任务的最终结果，发送个用户。
在步骤3)中，我们使用带有GRIDLET_SUBMEIT标记的消息向目标资源发送各子任务，当资源接收到子任务之后，根据其predecessorNum_ 域判断是否为入口结点（predecessorNum_为0表示无前驱，即为入口结点），否则，则将其挂起，等待其前驱子任务运行完毕后再唤醒它。
在步骤4)中，当某个子任务运行完毕之后，判断其是否为出口结点（edgeArray_域为空表示没有输出边，即为出口结点）。如果是，则使用带GRIDLET_RETURN标记的消息将结果发送给用户代理；否则，使用带有GRIDLET_DATATRANSEFFER标记的消息将结果发送给其后继子任务；而且此时，如果后继子任务不在当前资源上，则还需考虑通讯开销；否则，通讯开销为0。参见如右过程 Procedure 1 finishGridlet()。
资源通过消息标记GRIDLET_DATATRANSFER判断数据是否是前驱子任务发送的中间结果。如果是，首先获取数据，然后调用active过程唤醒相应的子任务。具体过程如下页Procedure 2伪代码片段。
唤醒子任务函数active的伪代码如Procedure 3.
5 实验与分析
考虑运行如下的Dag图，包括十个子任务，其ID分别从0到9（每个圈代表一个子任务），每条边上的数字代表两个子任务之间的通讯量：
假设三个资源分别为P1、P2和P3，各子任务在其上的执行时间如下表如图5.(b)所示：
使用HEFT算法[2]的静态调度结果顺序如下：n0,n2,n3,n1,n4,n5,n8,n6,n7,n9。各资源上运行的子任务如下：
根据HEFT算法各子任务的开始运行时间和运行结束时间如表2.(a)所示：
表2 两种方式下各子任务运行开始及结束时间表
从表中可以看出，整个Dag图运行的makespan是80（秒）。
我们再来看使用GridSim提供的原始方法调度相同的Dag图，任务使用HEFT算法，得到相同的调度方式：
各子任务的开始时间以及影响其开始执行的限制条件如表2.（b）所示
从以上调度方式的运行时间比较，我们可以看出，在原始的Gridsim中模拟Dag图的调度，并不能得到理想的结果。按照HEFT[2]算法的调度方法，图5所示Dag图的总运行时间（makespan）应为80，然而，如果使用原始的GridSim包进行模拟，得到的结果只会是123。两种方式下运行图5所示Dag图的运行时序图如图6所示。
其中，其中箭头表示子任务在不同的处理器上执行时制约起开始的条件，1号子任务在处理器P1上执行完毕的时刻是40，分配到处理器P2上的8号子任务必须等到时刻56（40+16=56,16为通讯开销）才能开始执行。（a）表示使用P2P数据传输方式的GridSim4Dag中的调度运行时序图，（b）表示使用GridSim原始的调度方式的运行时序图，从图中可以看到，由于中间结果的传送，增加了通讯开销，从而增大了整个任务的运行时间。粗箭头表示两种运行方式下个子任务之间制约条件的变化。
通过对GridSim底层的修改，实现P2P的数据传输方式，运行图5所示Dag图的makespan是80，总的周转时间为:80.01000000000022（所谓周转时间是指：任务第一个子任务开始运行到最后一个子任务运行完毕所花的时间），与HEFT算法计算出来的理论值吻合。
6 总结与前瞻
本文提出Dag图在GridSim中运行的一种新的数据传输方式，即P2P的方式，并通过对GridSim中代码的修改，实现GridSim中P2P的中间数据传输方式，并通过实验证实在在改进的GridSim4Dag上仿真Dag图运行的有效性和正确性。
本文设计实现的P2P中间数据传输方式的GridSim4Dag，不仅能扩展GridSim的功能，使其满足Dag仿真的要求，它更深层次的意义在于它符合Dag图调度的逻辑，所以可以应用到更多的真实网格系统中，如Globus，Fura等，所以以后还会进一步研究这种Dag图的调度方式在实际网格中的运行效果，以及其在真实的网格系统中的实现细节。参考文献：
[1] Z Yu and W Shi.An Adaptive Rescheduling Strategy for Grid Workflow Applications[J].Proc.of IPDPS,2007(3).
[2] Haluk Topcuoglu,Min-You Wu.Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing[J].IEEE Transactions on parallel and distributed system,2002,13(3).
[3] 卢鹏,金海,谢夏,等.关于模拟器的研究[J].高性能计算技术,2005,173(2):5-9.
[4] Forster I,Kesselman C,ed al.The Grid: Blueprint for a Future Computing Infrastructure[M].Morgan Kaufmann:San Mateo,CA,1999.
[5] Rajkumar Buyya,Manzur Murshed.GridSim: a toolkit for the modeling and simulation of distributed resource management and scheduling for Grid computing[J].CONCURRENCY AND COMPUTATION: PRACTICE AND EXPERIENCE Concurrency Computing;Pract.Exper,2002(14):1175-1220.
[6] 刘宴兵,杨茜慧,王文斌.基于GridSim ToolKits的网格仿真环境设计与实现[J].计算机科学,2008,35(6):83-85.
[7] 李炯,卢显良,董仕.基于GridSim模拟器的网格资源调度算法研究[J].计算机科学,2008,35(8):95-97.
[8] 邓蓉,陈闳中.GridSim仿真代码生成器GridSimHelper[J].计算机科学,2010(10).
[9] 董子龙.An Anatomy of GridSim[DB/OL].[2005-06-18].浙江大学CAD&CG实验室.
[10] Anthony Sulistio,Chee Shin Yeo,Rajkumar Buyya.Visual Modeler for Grid Modeling and Simulation (GridSim) Toolkit[C].by P.M.A.Sloot et al.(Eds.):ICCS 2003:1123-1132.
[11] Yu-Kong Kwok,Ishfaq Ahmad.Static Scheduling Algorithms for Allocating Directed Task Graph to Multiprocessors[J].ACM Computing Surveys,1999,31(4).
推荐访问： 仿真器 调度 GridSim4Dag GridSim Dag
