共查询到16条相似文献,搜索用时 62 毫秒
1.
基于逆向分层的网格工作流调度算法 总被引:10,自引:0,他引:10
有向无环图DAG(Directed Acrylic Graph)描述的工作流时间费用优化问题是计算网格下一个基本的且难以求解的问题.通过分析DAG图中活动的并行和同步完成特征,采取由后向前方法将活动逆向分层(BottomLevel,BL),将工作流截止期转化为层截止时间,提出截止期约束的逆向分层费用优化算法DBL(Deadline BottomLevel).算法中同层活动的开始时间不同于DTL(Deadline Top Level)算法中设置相同的策略,而是分别由其前驱活动确定,时间浮差被平均分配到各分层,以尽量增大活动的费用优化区间.通过大量模拟实验将DBL和MCP(mini mumCritical Path)、DTL两算法比较,结果表明DTL将MCP的平均费用降低15.62%,而DBL将MCP的平均费用降低24.74%.最后讨论了截止期和分组参数对算法性能的影响. 相似文献
2.
基于串归约的网格工作流费用优化方法 总被引:3,自引:1,他引:2
针对截止期限约束下有向无环图DAG(directed acyclic graph)表示的工作流费用优化问题,提出两个新的费用优化算法:时间约束的前向串归约算法FSRD(forward serial reduction within deadline)和时间约束的后向串归约算法BSRD(backward serial reduction within deadline).算法利用DAG图中串行活动特征给出串归约概念;基于分层算法对串归约组的时间窗口重定义,并提出动态规划的求解策略实现组内费用的最优化.两种归约算法综合考虑DAG图中活动的串并特征,改变分层算法中仅对单一活动的费用优化策略,实现了串归约组的时间收集和最优利用.模拟实验结果表明: BSRD和FSRD能够显著改进相应分层算法的平均性能,且BSRD优于FSRD. 相似文献
3.
虚拟网格服务工作流的调度算法研究 总被引:1,自引:0,他引:1
对虚拟网格服务工作流的调度算法进行了研究,提出了最小计算时间(MCT)、最小传输时间(MTT)、最小执行时间(MET)3种虚拟网格服务工作流的调度算法.在满足给定假设的情况下,MCT、MTT、MET的调度分别能保证目标工作流获得最小计算时间、最小传输时间、最小执行时间.在描述了调度算法之后,证明了算法调度的正确性.对几种算法的调度性能进行实验模拟,并分析和比较了它们的实现代价和时间、空间复杂度,从而给出各算法的适用情况. 相似文献
4.
如何在动态性极强的网格环境中有效调度工作流应用并满足用户的QoS需求是一个难题.传统的基于资源静态特征的启发式调度算法或预留策略缺乏对资源动态服务能力的有效评估而无法保证工作流应用的截止时间约束.本文采用随机服务模型建模网格资源的动态性能并考虑资源内处理单元失效的情况.利用生灭过程描述资源节点中处理单元数目的变化情况并给出了资源节点在任务截止时间内的可靠性评估方法.在此基础上,提出一种可靠性增强的网格工作流调度算法RSA_TC.实验结果表明RSA_TC算法相对于DSESAW和PFAS算法,能有效保证用户截止时间的要求,对动态网格环境有较好的自适应性. 相似文献
5.
6.
一种基于BPEL的网格工作流引擎 总被引:1,自引:0,他引:1
随着网格应用复杂性的不断增加,需要将多个网格服务编排成为一个网格服务工作流模型,然后由工作流引擎执行对网格服务的调用.为此,我们设计并实现了一个基于BPEL的网格服务工作流引擎BPEL FlowEngine.考虑到网格环境的各种特征,该引擎采用分级处理机制,可以同时调用Web服务、网格服务以及网格调度器.本文将介绍该引擎的结构和具体实现技术,并且与GWES引擎的性能进行比较,最后描述了该引擎在生物信息学计算中的示范应用. 相似文献
7.
针对效用网格下截止期约束的工作流费用优化问题,提出了路径平衡(path balance,简称 PB)算法,对工作流中各路径长度进行调整,并提出基于路径平衡的费用优化(path balance based cost optimization,简称PBCO)算法。 PBCO 基于 PB 的计算结果设置初始约束时间,充分利用了工作流的费用优化空间。同时,采用逆向分层策略对任务进行分层,并根据各层任务数按比例分配冗余时间,有效地增大了多数任务的费用优化空间,进一步改善了工作流的费用优化效果。实验结果表明,PBCO比另外几种著名算法(如DET,DBL等)改进了约35%。 相似文献
8.
QoS约束下基于双向分层的网格工作流调度算法 总被引:1,自引:0,他引:1
为使网格工作流的执行满足用户QoS要求,应用有向无环图描述工作流,并分析其中的关键活动,把用户对工作流的整体QoS约束分割为对单个任务的QoS约束.以此为基础,提出了一种基于双向分层的网格工作流调度算法Q-TWS.该算法通过对工作流正向分层和逆向分层,可以方便并准确找到任务之间的并行关系.Q-TWS可最大程度放松对任务执行时间的约束,在增加调度灵活性的同时又满足用户的QoS要求.实验表明,Q-TWS算法与TL算法相比,在同样的截止时间约束下,工作流执行时间较短,且工作流执行费用较小. 相似文献
9.
10.
11.
李纪彬 《数字社区&智能家居》2009,(9)
将用户定义的具体网格工作流抽象为DAG图,在DAG图中找到其关键路径,根据关键路径和用户的类型来计算任务的预测执行时间,确定任务的优先级,再比较若干候选资源,选择性价比较高的资源进行任务分配调度算法。 相似文献
12.
基于时序一致的工作流费用优化方法 总被引:1,自引:0,他引:1
针对效用网格下的工作流时间约束-费用优化问题,分层算法将工作流进行分层并逐层进行优化调度,取得了良好效果.然而,这类分层算法由于缺乏更有效的截止时间确定策略来保证时间约束而使得算法的适用性受限.在已有算法截止期约束的逆向分层算法(deadline bottom level,DBL)的基础上,研究工作流的时序特征,并基于任务的一致性状态对费用进行优化,提出了基于时序一致的截止期约束逆向分层算法(temporal consistency based deadline bottom level,TCDBL).TCDBL通过一致性时间点来保证时间约束,解决了DBL的适用性受限问题;同时基于各层并行度分配冗余时间,基于宽松时间约束策略进行费用优化,达到了进一步减少工作流执行费用的目标.实验结果表明TCDBL的费用优化效果比DBL改进了约14%. 相似文献
13.
14.
袁芬 《计算机与数字工程》2014,(11):2137-2141
在异构网络计算问题中,网格计算方法通过引入资源共享机制,可解决复杂的计算任务。然而在网格环境中,需要对网络可获得的资源进行合理调度和协调,才可以获得良好的网络工作流,以及合适的网络性能和网络响应时间。为了提高网格计算方法的任务调度和资源分配的能力和性能,提出了一种基于非合作博弈方式的博弈模型。该模型通过设定使用户的资源分配所需时间和代价降低的解来增加代理的利润,激励资源代理使用一种优化调度算法,使资源调度的时间和代价都最小。仿真结果表明了该模型的可行性和适用性,并且基于该模型的遗传算法是最好的资源调度算法。 相似文献
15.
16.
对用于网格工作流调度的遗传模拟退火(GA-SA)算法进行改进.在GA算法部分结合了基于阈值的动态交叉和变异概率, 并通过动态的调节近邻子集的大小,提高收敛速度,有效防止种群早熟现象,通过实验验证该算法的可行性和有效性. 相似文献