云计算中一种多DAG工作流可抢占式调度策略

为解决多用户工作流调度过程中的公平性问题,提高资源利用率,满足不同用户DAG工作流的不同QoS需求,提出了抢占式多DAG工作流动态调度模型。该算法将DAG工作流按照QoS需求进行优先级划分,采用高优先级作业优先占有资源的原则调度作业。相同优先级DAG工作流的任务依据带有启发性信息的slowdown进行资源抢占,进一步提高了作业调度的公平性;对于不同优先级的作业调度,提出了基于阈值的回填算法,该算法在保证作业调度公平的同时提高了资源利用率。     

基于EDA多任务流的调度算法研究

针对高性能计算环境下的多个电子设计自动化（EDA）任务流调度问题,提出一种启发式公平调度算法L-Fairness。在准备队列选择待调度任务时,L-Fairness算法结合任务滞后度、完成度和剩余完成时间确定任务优先级,保证多个任务流中任务的公平调度,同时将license数量及其类型作为处理器选择的依据,满足EDA多任务流的调度需求。仿真结果表明,与经典Fairness算法相比,L-Fairness算法的平均资源利用率提高6.7%,不公平度和平均完成时间分别降低46.2%和14.9%,保证了用户服务质量及调度公平性。     

兼顾费用与公平的带通信开销的多有向无环图调度

针对云环境下多有向无环图(DAG)工作流的调度算法应考虑执行时间、费用开销、通信开销、公平性等多个指标的问题,在模型带通信开销的DAG(CA-DAG)的基础上结合公平性算法提出一种优化完成时间的后向求异(BD)原则与兼顾费用和公平的多DAG调度策略CAFS.CAFS调度策略分为两个阶段:预调度阶段利用带通信开销的工作流费用优化(CACO)算法在考虑通信开销的同时求解所有任务的最优服务并优化费用,采用fairness算法得到较公平的调度顺序;调度阶段采用BD原则,根据在预调度阶段得出的调度顺序进一步优化整体的完成时间并执行调度.实验结果表明,CAFS调度算法具有较好的公平性,在不提高费用的基础上时间减少19.82%.     

异构分布式环境下多DAG工作流的混合调度策略

关于多个DAG工作流在异构分布式环境下调度的研究近来有了新的进展,也解决了一些问题,但现阶段还没有考虑和解决根据不同类型DAG的需求按优先级进行分类,以及对不同时间到达的多个不同优先级DAG进行调度的问题.为解决这些问题,针对各用户对DAG工作流的QoS需求的不同,在对不同用户的DAG工作流进行优先级划分的基础上,首先提出了一种新的调度模型,并改进了已有的公平调度算法,解决在不同时间上被提交的具有相同优先级的多个DAG工作流之间调度的公平性问题.为了提高资源利用率和高优先级DAG尽可能小地受低优先级DAG的影响,又提出了一种适用于多个不同优先级DAG之间调度的Backfill算法.在新的系统模型和这两种算法的基础上,提出了一种混合调度策略.实验结果表明,这种混合调策略能够兼顾不同时间到达的多个不同类型DAG调度需求和资源利用率的改善.另外,通过实验发现了关于两个DAG调度所特有的"拖尾"规律,具有进一步研究和应用的价值.     

基于最小化传输和完成时间的多DAG调度

针对云计算环境下多个有向无环图(DAG)工作流的调度问题,提出一种基于最小化数据传输时间和任务完成时间(LTCT)的算法,用于处理具有相同优先级的多个DAG工作流之间的调度问题。在多个DAG优先级各不相同时的情况下,给出多优先级多DAG的混合调度算法。实验结果表明,LTCT算法较E-Fairness算法在保证多DAG调度公平性的基础上,能避免额外的数据传输开销,有利于缩短整个工作流的执行Makespan,提高资源的利用率。     

有期限约束的多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调度的资源分配进化算法

现有多DAG调度研究主要在多个DAG共享资源调度的时间最小化、公平性最大化、吞吐量最大化等问题方面提出了相关的解决方案,然而,现有的方法还不能很好地解决云计算环境下多DAG共享资源调度的资源分配优化问题.为此,首先分析讨论了一组多DAG共享云计算资源调度中的多DAG数量、属性结构分布特点与资源需求量之间的关系,并在此基础上提出了基于资源需求强度预测变异方法的进化算法EFRD,有效地解决了云计算环境下多DAG共享资源调度的资源分配优化问题,既保证了多DAG的调度执行时间最小化,也避免了资源的浪费.实验表明,EFRD算法能够有效地收敛到最优解.     

一种基于流公平性的退避算法

在无线自组织网络中,合理的退避机制能够有效地利用网络资源,解决多个节点同时抢占共享信道的问题,提高网络带宽利用率。通过建立模型深入分析了由于隐藏终端产生的流不公平问题,给出了一种吞吐量变化率和流不公平度的度量,并提出了一种通过调整退避窗口最小值来改善流公平性的退避算法——BFF(Back-off based on Flow Fairness)算法。通过仿真分析表明算法能够很好地提高公平性,解决BEB算法在实际运用中的流不公平问题。     

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

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

Ad Hoc无线网络公平调度算法研究

随着个人通信的日益增长，支持诸如移动会议、移动网络以及自然灾难营救的ad hoc无线网络逐渐从军用扩大到商用等诸多领域。商用ad hoc无线同使用一种称为“付贾使用”(pay—for—use)的模式，于是在用户间定义合理的公平机制则变得非常重要。公平机制的核心问题是公平调度算法问题。但是在ad hoc无线网中，公平分配带宽和最大化利用资源本质上是冲突的，这为公平调度算法的设计带来了巨大的挑战。本文系统地研究了著名的公平性标准以及两类公平调度机制。通过模拟和分析，我们讨论了这两类公平调度机制中存在的问题。此外，我们提出了一种新的公平调度模型并给出了模拟结果。模拟结果表明，该算法在公平性和带宽利用率之间实现了理想的平衡。