版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
基于任务复制的动态关键移除调度算法
1同构同构的应用以最小完成时间为基础的文档任务是并行分布系统的一个重要问题。相关任务可以表示大量的数值计算、公式推导、工作流项目、算术方法等。例如,如快速傅立叶变换和高斯估计的计算。即使资源是相同的结构和完整的,任务也可以重复使用,这可以显著提高执行效率。同构问题是研究异构问题的基础,在解决问题其他单模项目的资源方面具有参考价值,因此得到了广泛的研究。本文研究同构问题的一个典型模型,即已知一组有优先关系约束的任务和一组相同数量的同构资源,求一种调度方案,满足以下约束:(1)任务限制(2)限制运行(3)任务调度tdb目标为如何将任务分配到资源,并给出任务在资源上的开始时间,使任务集的最早开始时间与最晚完成时间之间的差尽可能的小,即最小化调度长度(makespan).此类问题的一个典型应用为分布式内存机器中的任务调度问题.一般用加权的有向无回路图(DirectedAcyclicGraph,DAG)G(V,E,μ,λ)来表示相互依赖的任务集,如图2(a)所示,顶点集V={1,2,…,n-1,n}为任务集,顶点的权μi表示相应任务的执行时间,有向边集E={eij:i,j∈V;i→j}表示任务间的优先关系,边的权λij表示前后两任务不在同一资源上执行时的传输延迟.目前代表性的调度方法为启发式算法[1,2,3,4,5,6,7,8,9,10],主要包括基于任务复制的调度、基于优先级列表的调度和基于簇的调度三类.基于任务复制(Task-Duplication-Based,TDB)的调度算法通常要优于基于优先级列表和基于簇的调度算法.TDB算法的理论基础是采取以空间换时间的策略,通过冗余分配任务到多个资源以减少通信开销,从而减少总的调度长度,因此可生成更小的调度长度.如何准确地确定应被复制的重要任务是获得较短调度的关键,各种TDB算法的主要区别也正在于此.近年来发表的TDB算法包括DSH、BTDH、LCTD、LWB、PY、MJD、CPFD、TDS、ETDS、PPA、IREA等.PY和MJD是其中理论上最优的,它们对任意DAG给出了性能保证,而其它仅部分算法对某些特定DAG生成了优化调度.对任意DAG,PY调度的调度长度最多为最优调度的2倍,MJD调度的调度长度最多为最优调度的1+ε′倍(0<ε′≤1).MJD算法的主要思想是以拓朴顺序计算每个任务v的开始时间下界ev及其对应簇Cv,然后反拓扑顺序访问DAG中的任务并构造调度.在ev的计算过程中,数据到达时间c的计算未到任务v,而是进入簇Cv的第一个任务,可能错失更小调度的机会;且未考虑其祖先得到e值的对应簇信息,导致对任务的实际最早可能开始时间的估计不够准确.本文提出一种基于任务复制的动态关键前驱(DynamicCriticalPredecessor,DCP)调度算法,并证明对任意DAG,DCP调度的调度长度最多为最优调度的1+ε倍(0<ε≤1且ε≤ε′).针对实际应用中处理机数目受限的情况,算法在不增加调度长度的同时,尽可能减少占用的资源数目.实验表明DCP算法的求解质量很高.2sv的初始计算针对MJD算法的不足,DCP算法主要做了以下改进:(1)计算数据最早到达时间时,不是计算到入簇的第一个任务的时间,而是计算v的最早可能开始时间Sv.(2)放宽加入任务的条件,只要加入该任务不会使Sv增加,则可以加入簇Cv.(3)计算Sv时,其祖先任务含相关的分簇历史信息,即在考虑跨簇的任务时,不仅以任务为粒度,也以簇为粒度,从而更准确,并加快了计算过程.2.1任务的sv及对应簇cv首先按拓扑顺序访问图G中的任务v∈V,并计算其最早可能开始时间Sv及对应簇Cv.对任务v,设其祖先的S值及对应簇已求出,欲求Sv及对应簇Cv,只需找到一个包含v及其部分祖先的簇就足够了,因为如果某任务不是v的祖先,则从簇中移除该任务,不会使Sv增加,只可能使其减小.设Cv是一个含任务v及其部分祖先W={w1,w2,…,wl}的簇,U={u1,u2,…,uk}为跨簇Cv的任务.W和U中任务的S及对应簇C已经求出.将Si作为任务i的释放时间,按就绪任务释放时间的先后顺序对集合W∪U∪{v}进行贪心调度,得到v的最早可能开始时间Sv,并记下造成Sv不能再下降的关键任务u,称u为Cv的关键前驱cpred(Cv).然后寻找使Sv尽可能小的簇Cv,从只含任务v的簇开始,每次向簇中并入v的部分祖先集,并检查Sv是否减小.部分祖先集的选择,考虑了Cv的关键前驱u及其对应簇Cu,具体过程见图1.算法1为任务的Sv及对应簇Cv的计算过程,其中C.s和C.cpred表示当前格局贪心调度后的Sv和簇C的关键前驱,v.s和v.C表示终止格局时的Sv和Cv,w表示最后并入簇C的任务.算法1.COMPUTE_S_VALUE(v,G).2.2任务2.分簇.进行控制得到每个任务v∈V的最早可能开始时间Sv及对应簇Cv后,反拓扑顺序访问G中的任务并进行分簇.算法2.CLUSTERING(G).分簇完成后,将ϕ(G)中的每个簇分配到不同的资源上,它们之间用跨簇的边集关联,然后按任务的最早可能开始时间非降序排列进行贪心调度,得到最终结果.3结果3.1算例2.2算法复杂度EZ算例是DAG调度的经典算例,如图2(a)所示,其最优调度的调度长度一直被认为是8.5.图2(b)为DCP的调度结果,调度长度为8,使用了3个资源.图2(c)为每个任务的S值及其对应簇,图2(d)为任务T6的S和C的计算过程.DCP与相关算法的结果比较见表1,其中EZ、DSC、TDS算法的结果参见文献,DCP的算法复杂度说明参见文献.下面证明EZ算例的最优调度的调度长度为8.事实1.EZ算例的最优调度的调度长度为8.证明.因任务仅当其前驱任务均已完成才可能执行,所以在DCP的调度结果中,任务T1,T2,T3,T4,T5均已在其绝对最早可能开始时间被调度.由于T1→T2→T7为不考虑边的权时的最长路径,所以T7的最早开始时间不小于6,完成时间不小于7.若T1与T2不在同一簇中,则T2的最早完成时间为11,故T7的最早完成时间为12,不可能为优化调度.故优化调度中,T1与T2必在同一簇中.若T7与T2不在同一簇中,则完成时间不小于9,故优化调度中,T7一定与T2在同一簇中.考虑任务T6,只有两种可能:(1)与T2,T7在一个簇中,则T6的最早可能开始时间为6,T7的最早可能完成时间为8;(2)与T2,T7不在一个簇中,则T6的最早可能开始时间为5.5,T7的最早可能完成时间为8.5.可见EZ算例最优调度的调度长度为8.证毕.3.2算例来源及其它tdb算法的计算结果DCP算法与相关的6个TDB算法比较的结果见表2,其中算例来源及其它TDB算法的计算结果参见文献.可见DCP的解至少与其它TDB算法的最好解一样好,且若干算例得到了更优的解.4标识任务v1+本节从理论上分析DCP算法的性能,改进粒度的定义,并证明DCP对任意DAG可得到优于MJD的性能下界.粒度是分析DAG调度算法性能的一个重要参数.对任务v∈V,定义g1(v)=min{μu|(u,v)∈E}max{λuv|(u,v)∈E}‚g2(v)=min{μw|(v,w)∈E}max{λvw|(v,w)∈E}‚g1(v)=min{μu|(u,v)∈E}max{λuv|(u,v)∈E}‚g2(v)=min{μw|(v,w)∈E}max{λvw|(v,w)∈E}‚则v的粒度g0(v)=min{g1(v),g2(v)},图G的粒度g0(G)=min{g0(v)|v∈V}.本文改进了粒度的定义:(1)只考虑前驱及输入边,不考虑后继及输出边;(2)取前驱及相应输入边的比值中的最小值,而不取最小前驱与最大输入边的比值.对任务v∈V,定义v的粒度为g(v)=min{μu/λuv,(u,v)∈E},图G的粒度为g(G)=min{g(v)|v∈V}.例如对EZ算例,g(G)=g0(G)=0.2;若修改T1的计算时间为4,则g0(G′)=0.2,g(G′)=0.25.引理1.对任意DAG图G(V,E,μ,λ),存在0<ε≤1满足g(G)=(1-ε)/ε.证明.因μ,λ中元素均为有理数,由粒度的定义,g(G)为有理数运算得到,由有理数四则运算的封闭性,g(G)也为一有理数,故一定可写为一个分数,设g(G)=a/b,其中a,b∈N={0,1,2,…},且b>0,则0≤g(G)<∞.定义ε=b/(a+b),可推出0<ε≤1,且g(G)=(1-ε)/ε.引理得证.证毕.引理2.设v为一标识任务,且其对应簇Cv映射到同一资源,则存在0<ε≤1满足g(G)=(1-ε)/ε,使stv≤(1+ε)stopt(v).其中stv为v的开始时间,stopt(v)为v在最优调度时的开始时间.证明.由引理1,存在0<ε≤1满足g(G)=(1-ε)/ε.下面证明stv≤(1+ε)stopt(v),以标识任务v的深度为递推值,进行数学归纳证明:(1)若v为开始任务,stv=stopt(v)=0,命题成立;(2)设命题对v的祖先中的标识任务均成立.设另一个簇的标识任务u为任务w∈Cv和簇Cv的关键任务,则u为w的所有前驱中数据到达最晚的前驱,所以stw=stu+μu+λuw;由于祖先任务u为一标识任务,由假设stu≤(1+ε)stopt(u),所以stw≤(1+ε)stopt(u)+μu+λuw.因w为u的后继,stopt(w)≥stopt(u)+μu.因此,stw≤stopt(u)+μu+ε·stopt(u)+λuw,stw≤stopt(w)+ε·stopt(u)+λuw(1)由粒度定义和引理1,μu/λuw≥g(w)≥g(G)=(1-ε)/ε,ε(μu+λuw)≥λuw(2)由式(1)、式(2)得stw≤stopt(w)+ε(stopt(u)+μu+λuw),而stopt(v)≥stopt(u)+μu+λuw,可推出stw≤stopt(w)+εstopt(v)(3)式(3)对任意属于Cv的任务成立,所以stv≤(1+ε)stopt(v).引理得证.证毕.定理1.对任意DAG图G(V,E,μ,λ),存在0<ε≤1满足g(G)=(1-ε)/ε,且DCP调度结果最多为最优调度的1+ε倍.证明.设Mopt为G的最优调度结果,对G中所有无后继的点v,Mopt≥max(stopt(v)+μv).因每个无后继的点均为标识任务,由引理2:makespan(G)≤max{(1+ε)stopt(v)+μv}≤max{(1+ε)[stopt(v)+μv]}≤(1+ε)max{stopt(v)+μv}≤(1+ε)Mopt.调度结果最多为最优调度的1+ε倍.证毕.定理2.对任意DAG,DCP算法的性能下界优于MJD算法的性能下界.证明.由min{μuλ(u,v),(u,v)∈E}≥min{μu|(u,v)∈E}max{λ(u,v)|(u,v)∈E}min{μuλ(u,v),(u,v)∈E}≥min{μu|(u,v)∈E}max{λ(u,v)|(u,v)∈E},得出g(v)≥g1(v),而g1(v)≥g0(v),故g(v)≥g0(v),因此g(G)≥g0(G).由引理1,存在0<ε≤1满足g(G)=(1-ε)/ε;由文献,存在0<ε′≤1满足g0(G)≥(1-ε′)/ε′;可推出(1-ε)/ε≥(1-ε′)/ε′,即ε≤ε′.对任意DAG图G(V,E,μ,λ),由定理1,DCP算法的makespan(G)≤(1+ε)Mopt;由文献,MJD算法的makespan(G)≤(1+ε′)Mopt.而ε≤ε′,故DCP算法的性能下界优于MJD算法的性能下界.因此命题成立.证毕.5不允许复制时的调度在实际应用中,某些任务不允许被复制,如银行取款任务,而典型的DAG图Out-tree和In-tree应用非常广泛,如分而治之(divide-and-conquer)算法、常见的数值计算等.本节讨论不允许复制时DAG的特点,并证明存在多项式时间的算法,对Out-tree和In-tree的调度结果最多为最优调度的1+ε倍且0<ε≤1.定义1(In-tree).除了唯一的结束任务,每个任务只有一个子任务的DAG.定义2(Out-tree).除了唯一的开始任务,每个任务只有一个父任务的DAG.定义3(补图G′).对任意给定的DAG图G,其补图G′与G的唯一不同为G′中每条边的方向与G中对应边u→w的方向正好相反,为w→u.引理3.不允许复制时,对任意给定的DAG图G及其补图G′,设S′为G′的一个调度,可得到G的一个调度S:S中每个任务v的匹配资源与S′一致,且开始时间为stv(S)=makespan(S′)-ctv(S′),则G的调度S为一合理的调度,且与其补图G′的调度S′有相同的调度长度.证明.首先证明S为一合理的调度.设G′开始任务为v1,结束任务为vn,在调度S′中的开始时间与结束时间为st′1,ct′1,st′n和ct′n.设任意w∈V在G′的调度S′中的开始时间和结束时间分别为st′w和ct′w.则在G的调度S中:stn=makespan(S′)-ct′n=ct′n-ct′n=0,ctn=stn+μn=μn,stw-stn=stw=makespan(S′)-ct′w=ct′n-ct′w,ctw-stn=ctw=stw+μw=ct′n-(ct′w-μw)=ct′n-st′w.可见在S中对w的调度满足约束关系,为一合理的调度.st1=makespan(S′)-ct′1=ct′n-ct′1,makespan(S)=ct1=st1+μ1=ct′n-(ct′1-μ1)=ct′n-st′1=makespan(S′).G的调度S与补图G′的调度S′有相同的调度长度.引理得证.证毕.定理3.不允许复制时,存在一多项式时间的算法对Out-tree和In-tree的调度结果最多为最优调度的1+ε倍且0<ε≤1.证明.(1)由定理1,算法DCP可对In-tree生成最多为最优调度的1+ε倍的解.而In-tree的每个任务最多只有一个子任务,由DCP算法,实际上没有任务被复制.故不允许复制时,DCP对In-tree的DAG可生成1+ε优度的解.(2)任意Out-tree的补图为In-tree,对补图G′调度得到解S′,并定义原图G的调度为stv(S)=makespan(S′)-ctv
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 小学六年级英语教学设计:动词专题复习的分层推进与思维可视化策略
- 八年级生物遗传与进化中考分类集训教学设计
- 小学六年级信息技术教学设计:第五单元活动4创意游戏设计程序实现与优化
- 初中体育与健康八年级短跑起跑技术教学设计
- 小学六年级语文《宇宙生命之谜》首课时教学设计
- 初中七年级英语冀教版上册Unit 2 Lesson 2 Amazing English教学设计
- 初二生物教学设计:微生物的特点与主要类型第一课时(北师大版)
- 初中八年级美术《映日荷花》教学设计
- 新版2026-2027学年教科版六年级上册小学综合实践活动教学设计(全册)p99
- CN119538199A 石化管道全生命周期检测评估方法及设备 (太科技术有限公司)
- (2026年)国网35条严重违章及其释义课件
- 压力管道安全管理规定培训课件
- 金鲳鱼行业分析报告
- 彝族舞曲《快乐的啰嗦》欣赏与表现-小学音乐二年级上册教学设计
- 上海市浦东新区部分学校(五四制)2025-2026学年六年级上学期1月期末考试道德与法治试卷(含答案)
- CNAS实验室内审员培训资料
- 2026届安徽省芜湖市镜湖区师范大学附中化学高一上期中检测试题含解析
- 2025年上海市高考英语试卷及参考答案(完整版)
- 保安证考试新手必看试题及2025年答案
- 2069-3-3101-002WKB产品判定准则-外发
- (高清版)DZT 0216-2020 煤层气储量估算规范
评论
0/150
提交评论