论文研究-网格计算中基于信任机制的层次任务调度模型.pdf

所需积分/C币:5 2019-09-08 15:40:42 600KB .PDF
收藏 收藏
举报

提出了一种分布式层次任务调度模型,该模型将任务调度分两层进行,并且将信任机制引入其中以提高网格的服务质量及运行效率。提出了适应该模型的调度算法,算法同时考虑了网格实体间的信任关系、预测执行时间、QoS需求和价格因素,并动态调整它们在交易中所占的比重,从而较好地适应不同用户的需求。分析和仿真表明,该调度模型增强了网格环境的安全性和适用性,提高了执行效率,并降低了交易失败率。
胡艳华,王志斌,李健军:网格计算中基于信任机制的层次任务调度模型 2012,48(16)119 主要包括网络信息管理系统MDS和分布式监控系调度算法,将在下文中详细介绍 统NWS两个组成部分。它的任务主要是监控网格 至此,第一层调度已经结束,第一层调度完成 中的空闲资源,发现其中的可用资源,记录存储资源后,应及时更新资源节点的信任值。 的信息,同时任务执行完毕后应及时地更新资源信 步骤7最后个步骤,就是对子任务进行第二 息。当有任务申请资源时,网格资源信息中心会把层调度。第二层调度是在本地调度器上执行,而通 这些信息提供给它。另外,它在该模型中不仅可以常情况下认为是在集群上执行,所以这里还需要将 管理资源信息,还可以与QoS査询模块进行交互,然子任务再次划分,并将这些子任务分配到各个计算 后反馈到Qos控制模块,从而可以根据用户提供的资源站点上并行执行。对于并行执行的具体过程, QoS需求,尽可能地为用户选择满意的资源 本文借鉴现有的各种并行算法,限于篇幅不再详细 上述分布式层次模型的具体调度过程可以分为介绍。 7个步骤: 步骤1将用户提交的大型任务和用户的Q需3层次任务调度模型策略 求提交给任务提交中心模块,继而由它转交给任务 层次调度模型在第一层调度中主要完成的任务 解析器处理模块,经过这两个模块的处理,一个大型是为每一个子任务选择满足要求的大型计算资源, 的计算任务将被划分成若干个相互独立且服务类型然后调度到各个计算资源站点。如果把一棵站点资 不同的子任务集合,这些集合是根据提供的服务种源子树看作一个大型的计算资源,其中资源子树从 类进行划分的,且被保存在任务队列中 上到下分别为网格层、站点层(集群)、节点层(单处 步骤2(1)经任务解析器处理后的子任务,需通理器、多处理器、并行多处理机)和处理器层四层圳 寸αoS杳询模块。(2)oS杳询模块处理子任务的具么就是在不同层次的站点中选择合适的节点。该模 体过程为:首先根据需要到网格资源信息中心模块型调度策略考虑到资源的信任度、任务QoS需求、执 人查询空闲的资源信息链表,从中提取满足QoS需求行任务的时间和价格因素等性能参数 的一些可用资源的信息,若查询成功,返回到QoS查 该模型中资源选择模块和网格调度器是第·层 洵模块,并设置返囯值fag-l1;若上述査询失败,也就调度的核心模块,因此相应的调度算法也是模型调 是说空闲资源中不存在满足QoS要求的可用资源或度策略中的关键部分。本文把模型中的调度算法称 者就是服务的类型根本就不满足子任务的要求,返为计算资源选择一调度算法。该算法实现过程中, 回到QoS查询模块,此时设置返回值nag=0。在这两将根据不同用户的需要,并考虑到述性能参数,为 种情况下,都把子任务转交给QoS控制模块去处理 每个子任务选择合适的资源,并进行子任务调度,然 步骤3QS控制模块根据步骤2中nag的返回后才能转向第一层调度。 值进行处理,如果nag=0,则QoS控制模块重新去网 本文中任务调度模型的最终目的是在尽可能短 格资源信息中心模块中查询,同步骤2中(2)过程,直 的总执行时间内、以尽可能低的价格选取信任度较 高的资源。在任务执行时,数据传输需要消耗存储 到找到可用的资源信息,也就是直到返回值fag1 如果fag=1,则QoS控制模块根据步骤2中返回的叮 °资源和通信资源,而任务计算时还需要消耗计算资 用资源信息,对资源进行初步筛选,获得满足用户 源。为了更好地描述下文中的算法,这里把任务的 执行细分为数据传输和任务计算两个部分。 Qos需求条件的资源子集。 步骤4将步骤3得到的资源子集,转向信任机制 本文假设要将T={t1t2…,tn}(表示m个任务) 模块处理,计算各个资源节点的信任值。其中信任用合适的方式调度到C={1,c2,…,cn}(n个计算节点 机制模块,根据文献「1任值计算公式计算每个上去。该过程的相关参数定义如下: 资源节点的信任值。 (1)T={t,t2,…,tm}为任务集合,由任务解析器 步骤5资源选择模块根据步骤4的结果,为每一处理后获得,其中m为子任务数目。 个子任务选择满足要求的大型计算站点资源 (2)t(=1,2,…,m):第i个任务,该任务经过资 步骤6资源选择模块再转向网格调度器,也就源过滤器处理后,可得到一个计算资源站点集 是子任务调度。其屮资源选择模块和网格调度器模 i1i27 n},且这个集合符合基本执行条件 块是第一层调度的核心,在子任务资源选择和调度(其中n表示满足子任务t的资源站点数目)。 时,有具体的算法来实现,本文称为计算资源选择一 (3)预测执行时间ETC(,指的是将子任务t( 1202012,48(16) Computer Engineering and Applications计算机工程与应用 1,2,…,m)发送给计算资源站点π(矿=ⅱ,i2,…,讥)源R中的每个资源站点r相对应的衡量指标向量 上的可能执行时间。 MTR. j=(MCT(i, i). Pi i (4)其中4个任务在r计算资源单元上的预测 (2)对于任务t1,引入信任机制计算出预测最小 最小完成时间记为MCT(,,它包括预测执行时完成时间。其公式为 间、计算站点最早可用时间、数据在存储系统上的最 Trust-MT(i,i=McT(i, ii)/Trust(i, ii) 早可取时间、传输时间。其计算计算公式为: 其中Tzst(i,是节点t1对计算节点r;的信任度。 MCT(i, ij=ETC(i, in+ CS(r )+DS(t )+TR(, in)(1) (3)对于T中每个子任务t,根据下面公式(3) 其中CS(a)即r最早可用时间,DS()即运行时计算与其对应的每个可用计算资源r的综合衡量函数: 所需数据在存储系统上的最早可取时间,TRQG,即 Fn=aX7st-M7(,0)+(1-0)10≤a≤D(3) 把t所需的数据从存储系统传输到上的传输时其中,n为子任务在资源站点r上执行的价格; 间,且它们由MDS和NWS获得。 a是权重系数,其值为0,1,a的值可由用户任意指 (5)每个资源站点按照不同标准给出完成子任定。它可用于调节预测执行时间、信任值和价格三 务的总价格本文用P表示子任务在资源站点7个日标在函数中所占的比重。当a取值为0时,公 上执行的价格。 式(3)中相当丁考虑价格单方面因素;当a取值为1 (6)对每个t,满足基本执行条件的可用资源集R,时,公式(3)相当于考虑预测执行时间和信任值两个 中的每个;都有个对的指标向量MTR.=(MC,.因素。在资源的选择过程中,将根据子任务的预测 P)(其中MC7,和P分别表示预测最短完成执行时间、信任值、价格因素三个因素所占的比重, 时间和最小执行价格)。 动态调整a的取值。在公式(3)中,F,a的值越小, 网格环境中,由于不同的资源节点可以提供不说明计算资源r越能综合满足执行时间、信任值和 中同的Qs,所以不同任务对于QoS的要求也不同。例价格目标将使得总执行时间尽可能短、价格尽可能 如:有些任务只能在提供高的QoS的资源节点上执低、信任值尽可能高。 行,而另一些任务则无QoS要求。根据计算能力和 对于每个子任务t,从上述综合衡量函数值集合 带宽需求的高低,本文将任务区分为:Q(hh)、中选择满足下列目标的计算资源r(ke(1,2,…,n) Qos(h)os(h)和Qs(),其中h代表高代表低。Fmn=min{F,,F,2…,F,} 该模型的调度策略按照上述顺序依次进行调度,从 而避免了QoS需求低的任务占用高带宽的资源。 当有多个计算资源的F,值均等于Fmn时,则 根捃α的值从中选择资源 4层次任务调度模型算法 当0≤a≤12时,在综合衡量函数值等于F几 在对资源站点进行选择时,本文提出的算法称个计算资源中,选择一个价格P,最小的资源r 为计算资源选择一调度算法,且综合考虑总预测执 当1/2≤a≤1时,在综合衡量函数值等于F的 行时间和价格因素。它将根据用户的需要动态选择几个计算资源中,选择一个执行时间 Trust-MT较小 总执行时间尽可能小、信任值尽可能高的、价格尽可且信任度较高的资源a 能低的资源站点 (4)经过上述步骤,最后得到一个与子任务集合 该算法简要描述如下 T={t,t2…,t一一对应的目标计算资源集合 对于大型任务,经任务解析器之后获得的任务t1,n…,m}。n(k∈(1,2,…,n)是子任务t所 子集={2…,tn}。根据任务QoS的要求,按照调 选择的计算资源站点。 度策略中划分成四类任务,本文首先选择任务集合 (5)更新信任值和权值信息,并将子任务发送给 Qos(h)中任务子集T=(,2…,k≤m。接下来相应的计算资源站点,再进行第二层调度,并将其放 再依次对QoS(h)、QoS(h)和QoS()中任务子集进到各个执行节点去并行执行 行如下五个基本操作,直到所有任务子集T都综合 由QoS(hl)QoS(h)以及QoS()构成的r任务 选择适当的资源集合。 集,经过上述五个步骤的反复调度,便完成了整个算 (1)对于每个任务4,收集并计算出其可用资法的调度过程。 胡艳华,王志斌,李健军:网格计算中基于信任机制的层次任务调度模型 2012,48(16)121 本文算法在将信任关系融入任务调度的同时 表3子任务t计算资源选择结果 兼顾了任务的QoS需求和价格因素,从而改进了网 0=0.8a=0.6c=0.40=0.2ax 格系统的有效性,大大提高任务的执行效率,更好地 c(50,35)8333373.6667645433334.66735 满足了用户的需求。 e(32,56)47.058848.847150.635352423554211856 g(28,53 50 50.6512 51.8 52.453 选中的资源ee 5层次任务调度模型的示例及仿真分析 本文采用Gidm网络仿真工具对分层任务调有考虑价格因素的影响;当a=0,计算资源选择只考 度模型进行验证和分析。 本文将模拟一个简单示例说明上述提出的层次(0,1)之间变化时,计算资源选择一调度算法综合考 任务调度模型中的计算资源选择一调度算法。假设虑了预测执行时间、信任值和价格的因素,并改变a 个大型计算任务T已经被解析器分成6个相互独的值来确定它们之间所占的比重。 立的子任务{,t,t,t,t,t}。根据任务QoS需求 在对层次任务调度模型进行仿真分析时,本文 QoS(hh)=ti, ts)QoS(h1)=t2)QoS(1h)=te FHQoS(11) 假定网格系统中18个资源,且设定它们的速率均在 {t,l}。首先选择任务集合QoS(h)中任务子集T 400-850(MIPS),初始信任值设为0.3。 (t,l3)进行计算资源选择。本文以T=(t,t)集合为 为了说明对本文提出的层次任务调度模型的优 越性,本文首先将任务调度中的经典算法Min-Min算 例来详细描述计算资源选择一调度的算法,其他三 个集合将不再一一阐述。 法应用到该模型,并与文献[7]模型也选取Min-Min 算法进行调度。实验中对提交的任务数为20、60、 对于俨=(t,ts),资源选择模块也就是资源过滤 100、180和220这些情况进行多次跟踪记录其执行完 器的筛选,每个子任务都获得了一个满足基本执行成时间,其仿真结果如图2所示。 条件的可用计算资源站点集。收集并计算出每个计 算资源站点对于各个子任务的指标向量MTR,= 00 1800·本文模型使用 Min-Min算法 (MCT(,P.)。貝体数据如表1所示。 600 改进模型前使用MmMm算法 表1子任务的可用计算资源及指标向量集 1400 1200-+-+ 子任计算资源集:计算资源对应指标向量计算资源对节点的 务 t. ri,…,a}集:(MCT(,P,)}信任值Tust,i 1000 (30,15),(35,50),{(0.65),(0.81) 800 fa,d, f, m) (25,25),(20.35)}(0.69),(062)} 600 {(50,35),(32,56) {(06),(0.68) 400 )} (0.56)} 200 根据上述计算资源选择一调度算法,指标向量 导8房月导 提交的任务数 计算相应的综合衡量函数值F;=a×1st-MTG,)+ 图2模型比较任务的执行时间 (1-ω)×O≤α≤1),并选择预测执行时间、信任度、 2000 价格综合最优的计算资源,结果如表2所示。 1800 Min-Min算法 l600 New算法 表2子任务n计算资源选择结果 1400 =1a=0.80=0.6a=0.4a=0.2a=0 1200 a(30,15)46.153839923033.692327.461521.230815 81000 d1(35,50)43.209944.567945925947.2839486419850 800 f(25.25)36.231833.985531.739129492727.246325 600 m(20,35)32.258132.806533.354833.903234451635 选中的资源 r mm f a 400 a 200 由表2和表3计算结果中可以看出,当a=1时, 所选中的计算资源是由预测执行时间和信任值所决 提交的任务数 定,即预测时间尽可能短和信任值较高的节点,而没 图3算法比较任务的执行时间 1222012,48(16) Computer Engineering and Applications计算机工程与应用 另外,本文的分层任务调度模型在执行的过程 由图4知,本文的算法明显减低了执行失败的概 中,计算资源选择一调度算法在第一层调度是先对率;由图5知,New算法在资源利用方面明显高于传 资源进行预选择,而当使用 Min-min算法时,不考虑统算法Min-Min算法。 其资源的预选择问题,用 Min-Min进行直接调度。由 从上述的仿真结果可以很容易的看出,本文提 图2结果可以看出,使用同样的调度算法,本文提出出基丁信任机制的层次任务调度与已有模型相比具 的层次任务调度模型的执行完成时间也明显变短,有更好的优越性。该模型中的计算资源选择调度 故新糢型明显优于中调度模型在一定程度上缩短算法降低了任务执行失败的概率,提高了任务执行 了任务的执行时间。 的效率,且提高了资源利用率。 接下来,对本文中的选择一调度算法(New算法) 和Min-Min算法在执行时间、任务提交执行的失败率 和资源利用率进行对比分析,验证各算法的性能。 6结论 由图3得知,本文提出的选择一调度算法执行时 本文针对树格中资源繁多、动态性和自治性等 间明显低于Min-Min算法执行时间。所以New算法特点,提出了一种分布式的层次任务调度模型和适 缩短了任务执行的时问,提高了执行效率。 用该模型的计算资源选择一调度算法。新的任务调 实验过程中分别对任务数20、60、100、140、180度模型将信任机制融入到网格任务调度中,且在调 和220中提交的任务交易失败的次数进行统计(取50度的过程中考虑到性能参数和网格实体的行为特 次实验记录),然后取它们执行失败次数的平均值,征,在网格实体交易时,可以很好地将任务分配到信 图4表示两种算法的任务执行失败率。同样方法,实任度较高的节点上执行,从而降低了应用任务执行 验中还对18种资源进行统计,分别在任务数20、60、失败的概率,提高网格环境的安全性和执行效率;计 100、140、180和220的情况下,考察资源的利用情况, 算资源选择一调度算法允诈用户通过设置相关参数 图5表示两种算法的任务执行的利用率。 来动态调整响应时间、信任值和价格在其日标中所 100 占的比重,从而比较符合现实生活中的情形。因而, 90 Min-Min算法 用户可以根据自己的需要动态选择总执行时间尽可 New算法 能小、信任值尽可能高、价格尽可能低的资源站点进 70 行调度,具有良好的适应性。由于网格任务调度中 引入信任机制,信任度计算受环境要求限制,上述的 预测最小执行时间的计算并不好于实际或理论计 算,本文工作只是·个起步,下·步研究工作可以综 合考虑更多目标,使资源的选择更加灵活和最优。 参考文献 提交的任务数 [I Wu Min- You, Shu Wei, Zhang Hong Segmented Min-Min: 图4任务执行的大败率图 a static mapping algorithm for meta-tasks on heteroge Min-Min算法 neous computing systems[C]//Proceedings of the 9th New算法 IEEE Heterogeneous Computer Workshop, 2000: 375-385 [2] Braun T D, Siegel H J.A comparison study of st mapping heuristics for a class of meta-tasks on hetero- geneous computing systems[]/Proceedings of the &th IEEE Heterogeneous Computing Workshop. IEEE Com puter Society Press, 1999: 15-29 30 [3] Braun T D, Siegel H J, Beck N, et al.A comparison of 20 eleven static heuristics for mapping a class of indepen dent tasks onto heterogeneous distributes computing[J] 导8员量品员 Journal of Parallel and Distributed Computing, 2001, 61 提交的任务数 (6):810-837 图5任务执行的利用率 (下转156页)

...展开详情
试读 6P 论文研究-网格计算中基于信任机制的层次任务调度模型.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    weixin_38744435 欢迎大家使用并留下宝贵意见
    2019-09-08
    img
    • 至尊王者

      成功上传501个资源即可获取

    关注 私信 TA的资源

    上传资源赚积分,得勋章
    最新推荐
    论文研究-网格计算中基于信任机制的层次任务调度模型.pdf 5积分/C币 立即下载
    1/6
    论文研究-网格计算中基于信任机制的层次任务调度模型.pdf第1页
    论文研究-网格计算中基于信任机制的层次任务调度模型.pdf第2页

    试读已结束,剩余4页未读...

    5积分/C币 立即下载 >