带通信开销的DAG工作流费用优化模型与算法

通信开销在云环境中无法忽略,但现有DAG(directed acyclic graph)工作流费用优化模型大都未考虑任务之间的通信开销,难以在实际云环境中应用.为此,提出带通信开销的工作流费用优化模型CA-DAG(communication aware-DAG),并在分层算法的基础上提出针对CA-DAG模型的调度算法CACO(communication aware cost optimization).CACO使用前向一致规则(forward consistent,FC)求解工作流的最小完工时间;根据逆向分层策略将任务分层,使费用优化问题从全局转化到局部;采用动态规划方法收集任务在选择服务时产生的零散"时间碎片",增加任务的费用优化空间,改善费用优化效果.仿真实验结果表明,在考虑通信开销时,CACO费用优化效果较DTL(deadline top level),DBL(deadline bottom level),TCDBL(temporal consistency deadline bottom level)都有显著提高.

有期限约束的多DAG共享资源的调度及公平费用优化方法

随着网格和云计算工作流技术的发展,近来关于多DAG(Directed Acyclic Graph)共享资源调度的研究取得了一些进展,然而,关于具有最晚完成期限约束的多DAG共享一组有限异构资源的调度及其费用最低化等问题还有待进一步研究和解决.针对这些问题,文中首先提出了衡量DAG期限紧急水平的"相对严格程度"的新方法,并在此基础上提出了基于相对严格程度的调度算法MDRS(Scheduling for Multi-DAGs with Deadline based on Relative Stritness).该算法不仅能够合理处理多个DAG之间调度的紧急水平关系,也能对由于DAG期限过于严格而可能产生的"过饱和"情况进行探测和处理.一旦遇到"过饱和"情况,则采用"堆栈"与"调度回溯"相结合的机制尽可能少地丢弃其中的DAG,从而达到DAG吞吐量最大化调度目标.在MDRS算法的基础上,为了满足各DAG期限内完成约束条件,并尽可能公平地降低多个DAG执行的费用,又提出了基于单位相对严格程度变化量的费用降低率最大化方法的费用优化算法CDVRS(Cost Decrease based on Variance of the Relative Strictness).实验表明:这些方法及算法能够达到较好的性能.

动态多DAG调度的改进算法

工作流调度问题通常可以描述为一个活动与数据传输约束组成的有向无环图(directed acyclic graph,DAG),基于Planner-guided算法框架,采用新的基于多有向无环图节点合并的优先级计算方案改进原有算法,改善了系统中已存在未执行的DAG结点优先级过小而被滞后的问题,从而使得任务在机器上排布相对比较密集,提升了多个DAG结点间调度公平性。结果表明,提出的改进算法优先级计算更加合理,在资源利用率和执行时间上优于Planner-guided算法,调度整体性能得到一定提升。

DAG分割模型下的云工作流调度策略

为了优化云工作流调度的经济代价和执行效率,提出一种基于有向无环图(DAG)分割的工作流调度算法PBWS。以工作流调度效率与代价同步优化为目标,算法将调度求解过程划分为三个阶段进行:工作流DAG结构分割、分割结构调整及资源分配。工作流DAG结构分割阶段在确保任务间执行顺序依赖的同时求解初始的任务分割图;分割结构调整阶段以降低执行跨度为目标,在不同分割间对任务进行重分配;资源分配阶段旨在选择代价最高效的任务与资源映射关系,确保资源的总空闲时间最小。利用五种科学工作流DAG模型对算法进行了仿真实验。结果表明,PBWS算法仅以较小的执行跨度为开销,极大降低了工作流执行代价,实现了调度效率与调度代价的同步优化,其综合性能是优于同类型算法的。

DAG多级相关节点聚类的多目标工作流调度

针对科学工作流的为多目标调度问题,将成本、时间和数据传输量作为基本优化目标,提出基于有向无环图(Directed Acyclic Graph,DAG)模型的多级相关节点聚类(Multi-level correlated Nodes Clustering,MNC)方法。首先,针对在连续级别上直接连接的Peer-to-Peer群集组对等任务,将多个依赖节点打包到不同层次的DAG工作流中,并将具有父节点和子节点关系的两个节点分成同组。然后,针对MNC科学工作流调度模型,采用遗传算法进行模型的染色体数据表示、调度译码算法以及极值解的求解方法设计等,建立了科学工作流调度的多目标优化模型;最后,通过在随机生成工作流数据上模拟实验显示,所提算法在网络运行成本、计算时间和数据传输量等指标上的性能优势,验证了算法有效性。

基于混合云技术的媒体融合系统设计

为满足融媒体中心对高效、低成本、高可靠性的媒体融合服务需求,设计一个基于混合云技术的媒体融合系统。首先,通过公有云和私有云搭建混合架构,包括用户、混合云管理、混合云三个多源信息合成模块。其次,根据混合云环境的特点和用户需求,设计资源混合模型,包括数据层、特征层和决策层三个层次,并基于证据组合规则、DAG工作流模型对三个层次进行优化。最后,测试系统性能(即所用时间和成本)并与其他方案进行比较。结果表明,所设计的融合任务的通过率保持在100%,在时间和成本上的花费低于其他算法50%以上,系统稳定性较高。提出的媒体融合系统可被实际推广应用。

基于BPEL的Web服务快速组合框架

针对当前Web服务组合语言以及Web服务组合过程的复杂性,提出基于业务流程执行语言(BPEL)的Web服务快速组合框架。该框架用有向无环图(DAG)表示服务组合逻辑,通过对DAG解析自动生成发布工作流所需要的各种文档。对原型系统的验证结果表明,该框架能将BPEL的复杂性隐藏起来,达到Web服务快速组合的目的。

面向对象的流程工业系统有向无环图建模

提出流程工业系统中有向无环图的面向对象的建模方法。介绍使用面向对象的技术对流程工业系统模进行建模的关键要素的技巧,定义描述流程工业系统中有向无环图模型的建模机制,扩展流程工业系统模型所具有的特性。以流程工业系统出现异常时的诊断实例说明系统模型解决问题的有效性。

QoS约束的云工作流调度算法

将云计算和工作流两者结合起来,并根据用户关心的QoS中执行时间和执行费用问题,针对工作流调度策略在云环境下调度实例密集型工作流时效率不高的问题优化资源调度策略,给出云工作流调度模型,提出一种基于QoS约束的云工作流调度算法MSCWQ(modified scheduling algorithm for cloud workflow based on QoS).该算法利用DAG(directed acyclic graph)进行建模,优化资源策略,保证在最晚结束时间内使整个工作流实例的执行费用尽可能小.实验结果表明,在调度实例密集型云工作流时,该算法能有效提升科学工作流的执行效率,并能减少资源的使用费用.

基于优先级规则的网格工作流调度

网格资源需求的不断增长使价格成为资源进行竞争的有效手段,有向无环图DAG(Directed Acyclic Graph)表示的工作流时间费用优化问题是网格环境下一个重要问题.通常情况下,DAG应用调度属于NP-Hard问题.通过分析活动间的时序特征,给出时间耦合强度TCS(Time-dependent Coupling Strength)的定义,用于标识一个活动最大的时间耦合活动个数;将其作为优先级规则的一个重要信息和BF规则(BestFit)结合,设计出时间耦合强度最适规则BFTCS(Best Fit with Time-dependent Coupling Strength),用于启发式算法的改进阶段,逐步提高初始可行解的性能.模拟实验结果表明,相对现有的启发式算法,基于BFTCS规则的启发算法能获得最好的性能和较快的运行效率;最后讨论了问题参数对算法性能和效率的影响.

多目标服务工作流混合粒子群调度算法

针对NP难的服务工作流时间-费用优化问题,提出多目标混合粒子群算法(HMOPSO)来优化工作流调度问题.HMOPSO算法包括:初始种群生成、适应值分配、种群多样性保持、外部种群和极值选择.通过分析服务工作流的特征,构建有效的粒子结构使之离散化;通过设定单目标最优初始解,优化初始种群;通过引入外部种群和基于小生境技术的网格方法,获得分布均匀的Pareto最优解集.实验结果表明,HMOPSO具有更快的收敛速度和更好的寻优能力,并且在不同特征的问题实例上获得了数量众多、分布均匀、有较高质量的Pareto最优解集.

基于排队论时间预测的网格工作流调度算法

针对时间限制严格的DAG(有向无环图)类型网格工作流提出了一种新的基于排队论时间预测模型的网格工作流调度算法。按照用户提交的工作流执行时间的要求,利用Little公式计算任务在各候选资源上执行时间超过规定时间概率的大小,然后选择最佳的候选资源执行工作流任务。仿真结果证明了该算法的有效性。

基于免疫遗传算法的网格工作流服务选择

随着OGSA(open grid service architecture)的提出,在网格环境中,如何进行服务的选择是一个热点问题.对于DAG(directed acyclic gragh)描述的网格工作流模型,考虑时间和费用两个Qos(quality of service)参数,即满足用户截止期的前提下,为工作流选择尽可能便宜的服务.对于一般遗传算法的求解问题时出现的早熟和退化现象,采用了免疫算子和遗传算子相结合的免疫遗传算法来进行搜索全局解,并且加入了自适应遗传交叉算子和疫苗提取来提高搜索能力.仿真试验证明文章的算法具有较好的解空间搜索性能.

军事网格工作流调度算法研究

针对军事网格应用及工作流的特点,提出一种基于网格工作流分割的调度算法。采用基于有向无环图的工作流建模方法,对网格工作流的相关概念进行形式化定义。在确定基本工作流之间的复合关系后,对网格工作流中的任务实施调度。实例结果表明,该算法能减少网格工作流的任务执行时间,具有较好的调度性能。

配电站云机器人任务流的调度策略

针对云架构下配电站智能巡检机器人应用场景,以缩短该场景下云机器人任务流的完成时间为目标,研究建立一种云机器人任务流调度策略。首先,根据任务耗时与虚拟机算力是否相关以及作业任务是否占用云端虛拟机资源,将配电房值守作业任务划分为时间依赖型、计算依赖型以及空载型等三种类型,并对云机器人部分类型工作进行耗时预测。其次,建立云机器人任务流的DAG模型。最后,基于配电站应用场景,设计改进的HEFT静态算法对云机器人的任务流调度进行全局优化。依据配电站具体应用工况,在Cloudsim仿真平台上对算法有效性展开仿真分析与结果验证,并与传统的动态调度方法展开对比研究。