基于有向无环图的成本-时间优化调度算法

网格计算环境下,基于有向无环图(DAG)的成本-时间优化调度算法运用经济规律把网格用户的任务映射到网格资源中运行.OGS算法考虑了任务间的优先关系,使得任务完成时间最小,但没考虑到在网格环境中所需的成本.Nimrod/G模型中提出基于时间和成本限制下的优化调度算法(DBC)考虑了时间和成本,但没考虑任务问的优先关系.本文综合考虑了成本-时间因素以及任务间的优先关系,在不增加完成时间的基础上,把任务映射到价格便宜的机器上,提出了基于有向无环图的成本-时间优化调度算法.通过仿真表明,相对OGS算法,该算法减少了所需成本.     

经济模式下基于有向无环图的优化调度算法设计

Buyya提出的费用-时间优化算法运用经济规律把网格用户的任务映射到网格资源,但没有考虑任务间的优先关系。本文综合考虑时间、费用以及任务间的优先关系等诸多QoS需求,提出了基于有向无环图的优化调度算法。通过仿真实例,论证了该算法的优越性。     

基于有向无环图网格独立任务调度算法*

提出了基于有向无环图多约束网格环境下独立任务的调度模型,为其建立多约束线性规划模型,通过求解模型节点的优先级,获得网格各计算节点最优任务调度数;然后基于多约束最优任务调度方案,提出多约束带宽优先启发式算法(MCOPBHATS)和多约束计算速度优先启发式算法(MCOPCHATS)。实验结果表明,在多约束异构的网格环境下实现大量独立任务调度时, MCOPBHATS和MCOPCHATS算法的性能优于基于多约束最优任务调度方案的MinMin 算法。     

基于有向无环图的两层网格监测系统

资源监测系统是网格实现中的重要一环，Global Grid Forum已提出用网格监测体系结构（grid monitoring architecture,GMA）来解决这些问题，在此基础上，提出一种基于有向无环图的两层资源监测系统（DTGMS）。该系统使用有向无环图来描述资源间的依赖关系，把它作为该系统的逻辑基础，总体结构分为维护层和工作层同，维护层存储管理监测元数据和控制工作层的运行，工作层依据维护层提供的元数据，负责实际的数据采集、处理、输出等与被监测动态数据直接相关的工作。工作层的监测代理实现为控制核心和扩展模块两部分，有利于实现功能动态扩展。还比较详细地介绍了系统各模块间的交互协议与通信优化。征收GMA相比，新系统更好地满足了网格监测的需求，以较低的系统开销获得较多的功能。     

云计算环境下多有向无环图工作流的节能调度算法

针对多有向无环图(DAG)工作流节能调度算法中存在的节能效果不佳、适用范围较窄和无法兼顾性能优化等问题,提出了一种新的多DAG工作流节能调度方法--MREO。MREO在对计算密集型和通信密集型任务特点进行分析的基础上,通过整合独立任务,减少了处理器的数量,并利用回溯和分支限界算法对任务整合路径进行动态的优化选择,有效降低了整合算法的复杂度。实验结果证明,MREO在保证多DAG工作流性能的前提下,能够有效降低系统的计算和通信能量开销,获得了良好的节能效果。     

基于遗传算法的有向无环图画图算法

在研究了现有画有向无环图的主要方法的基础上提出一种基于遗传算法的有向无环图画图算法,将一般有向无环图的画图问题转换为函数优化问题,用遗传算法求目标函数最优解的近似值。实验表明此算法具有算法统一、方法简单、容易实现、易于修改,并且具有自适应、自学习和易于并行化的特点。     

有向无环图的高效归约算法

将一个应用程序部署到给定的片上网络上执行时,需要将应用程序中的每一个子任务都指派给片上网络中的一个节点执行。该问题一般被建模成一组子任务作为顶点的有向无环图,任务在片上网络上的部署过程就等同于一个有向无环图的顶点向一个片上网络拓扑映射的过程。而随着应用程序和片上网络规模的增大,计算一个最优的映射方案是典型的难解问题。为了加速有向无环图到片上网络拓扑的映射过程,提出了有向无环图的归约算法,使归约后的图中的顶点数量尽可能地与给定片上网络中的节点数量相同。提出的图归约算法可以有效地识别出所有可归约子图,这些可归约子图可被归约为单一顶点。新算法的适用范围从嵌套图扩展到了任意图,并且拥有与原算法相同的复杂度量级。还提出了一种并行化的算法思想来加速可归约子图的搜索过程。     

基于有向无环图的互联网域内节能路由算法

互联网在快速发展的过程中面临新的挑战,其中网络能耗问题尤为突出。学术界提出了大量用于 解决网络能耗问题 的方案,然而这些方案都考虑了网络中的实时流量数据,计算复杂度较高,不利于实际部署。对此,提出一种基于有向无环图的互联网域内节能路由算法(Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph,EEBDAG),该方法 利用有向无环图来解决因链路关闭造成的路由环路和网络性能下降等问题, 仅须考虑网络拓扑结构,不需要考虑网络中的实时流量数据 。实验结果表明,EEBDAG不仅具有较低的节能比率,而且具有较低的链路利用率,为ISP解决互联网节能问题提供了一种全新的方案。     

支持有向有环图的微调度方法

指令调度是编译器中的重要优化阶段．如何充分利用处理器结构相关的资源,发掘程序并行性,以提高编译优化性能和增强代码可适应性,一直是指令调度的研究难点之一．目前微调度已经取得了一定的效果,但对软件流水产生的有向有环图则未能提供支持．在ORC中提出并实现了一种基于IA-64体系结构的支持有向有环图的微调度方法,有效地减少了程序执行周期和流水线停顿,取得了较为满意的编译优化性能．     

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

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

有向无环图最小度生成树问题的一种近似算法

计算具有较小度的生成树是算法与复杂性研究的一个基本问题,同时在网络设计等领域具有重要应用.给定具有n个顶点的有向无环图G=(V,E)和根顶点r∈ V,最小度生成树问题欲求一棵以r为根的生成树T,使得在G的所有以r为根的生成树中T的最大度最小.给出该问题的一种迭代的多项式时间近似算法.该算法所求树的度不超过△*+1,其中△*为某一最优树的度.算法的时间复杂度为O(n2logn),其中n为顶点数目.算法没有运用过多的枚举,其实际运行时间要快得多.     

一种基于分簇复制的DAG任务图调度算法

并行任务调度是影响机群计算效率的关键因素之一，机群环境DAG(Directed Acyclic Graph)任务图调度是一个NP完全问题，只能寻求启发式算法。已有的研究中，图解重构算法在允许任务复制的条件下，通过对DAG图递归分解与子图重构，初步实现了一个可行的调度方案。该文在此基础上，提出了以调度长度增量为依据的任务复制策略，利用该策略调整受制约节点的同簇前驱，解决了任务簇间的时间制约问题，缩短了调度长度；通过合理地选择任务簇进行合并，增大任务簇的粒度，提高了处理器的利用率。提出的以任务簇扩展-合并为特征、以分簇复制为手段的DAG图调度算法，改进和拓展了图解重构方法。实例分析表明本算法复杂度与TDS (Task Duplication Scheduling)相同，但性能更优。     

基于有向图模型的委托研究

委托是常见的一种安全策略形式,委托可以用带标识的有向图对其严格地形式化建模,称为委托图。给出了委托图的定义,存储,委托图中实现委托的算法,委托图无环性判定算法,并进行了分析,讨论了委托图的性质。     

时间依赖有向无环网最小时间路径算法

经典模型及算法可解决固定弧权条件下的最短路问题,然而实际应用中孤权往往是动态的,即弧权依赖时间变化。本文提出一种特殊最短路径算法,即在有向无环网络中最小时间路径算法的一种实现。该算法是一种改进的扩散法,克服了扩散法的一些显著缺点。文中证明了该理论的正确性,最后列举了一个传统算法不能解决的实例,证明了该算算：法的正确性。     

基于串归约的网格工作流费用优化方法

针对截止期限约束下有向无环图DAG(directed acyclic graph)表示的工作流费用优化问题,提出两个新的费用优化算法:时间约束的前向串归约算法FSRD(forward serial reduction within deadline)和时间约束的后向串归约算法BSRD(backward serial reduction within deadline).算法利用DAG图中串行活动特征给出串归约概念;基于分层算法对串归约组的时间窗口重定义,并提出动态规划的求解策略实现组内费用的最优化.两种归约算法综合考虑DAG图中活动的串并特征,改变分层算法中仅对单一活动的费用优化策略,实现了串归约组的时间收集和最优利用.模拟实验结果表明: BSRD和FSRD能够显著改进相应分层算法的平均性能,且BSRD优于FSRD.     

基于结点优化的决策导向无环图支持向量机及其在故障诊断中的应用

支持向量机(Support vector machine, SVM)是利用离在线数据自动建立故障诊断模型的智能方法,它在多故障诊断时, 必须先进行多分类扩展. 决策导向无环图(Decision directed acyclic graph, DDAG)法是一种性能优秀的多分类扩展策略, 但该方法的决策结果与结点的排部密切相关, 而其结点的排部却是主观的, 影响了诊断的正确率. 本文提出一种根据故障数据的空间分布来优化结点排部的方法, 它能够提高支持向量机诊断的正确率. 采用该方法扩展的多分类支持向量机在变压器故障诊断中获得良好效果.     

有向图并行计算中的多目标剖分算法

在以离散网格为基础的某些数值模拟中,网格间的数据依赖关系可以抽象为有向图．如何剖分这些有向图成多个子图,将各子图对应的数值模拟任务映射到不同的处理机,是该类数值模拟并行计算的基础．剖分算法中,需要综合考虑连通性、并行度、负载平衡、通信开销四个目标．文章在传统有向图剖分算法的基础上,提出了一个权衡这四个目标的有向图多目标剖分区域分解算法．应用于二维非结构网格上的柱对称中子输运并行计算中,通量扫描并行算法在该区域剖分算法上获得的并行效率比原来的无向图区域剖分算法高50％以上．